Zadanie na binsearch po wyniku - kłopot z implementacją

Question

Witam,

Ostatnio zabrałem się do zadania "Marchewki" na Szkopule. Prawie je zrobiłem, jednak mam błąd, którego nie mogę wychwycić.

link do zadania: https://szkopul.edu.pl/problemset/problem/FoB1dQnkHiTTdsnysyz41SVG/site/?key=statement 

Mój kod:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define pll pair<ll, ll>
ll m;
ll ile_punktow_kratowych(int R){
    int x = R;
    ll wynik = 0;
    for(long long y = 0;y <= R;y++){
        while(y*y + x*x > R*R && x > 0)x--;
        wynik+=x;
    }
    return wynik*4+1;
}
int binsearch(ll m){
    int a = 1;
    int b = 1e6+1;
    int R = (a+b)/2+1;
    while(b-a>1){
        if(ile_punktow_kratowych(R)<m)a = R;
        else b = R;
        R = (a+b)/2;
    }
    if(ile_punktow_kratowych(R) < m)return R+1;
    return R;
}
int main(){
    fast
    cin >> m;
    cout << binsearch(m);
}

 

Comments

A czemu zwracasz patrzysz na R w bin searchu?

---

R to długość ramienia. Ramię to zbierze tyle marchewek, ile jest punktów kratowych w kole o promieniu R.

Answer 1

Błąd masz w funkcji liczenia ile jest punktów kratowych wewnątrz okręgu o danym promieniu. Wkleiłem mój kod liczący tą funkcję i wchodzi na 100pkt. Co ciekawe, po napisaniu swojej funkcji do tego popatrzyłem na twoją i jest praktycznie bliźniacza, tylko twój błąd jest taki, że zmienne x oraz R są intem, a robisz x*x i potem R*R i Ci się wywala z int-a - WA. Wystraczy, że z int-a zmienisz na long long-a i masz 100pkt. Trzeba uważać na przepełnienia int-ów, np. częstą pomyłką jest to jak liczysz iloczyn wektorowy. Kiedyś byłem na warsztatach algorytmicznych na UJ i wykładowca mówił, że drużyna UJ kilka lat temu przez to, że nie dała long-longów tylko int-y przy liczeniu iloczynu wektorowego straciła medal na jakieś międzynarodowej olimpiadzie studentów czy czymś takim.

Teraz kilka rzeczy

Po pierwsze w linii 10 piszesz: ll m, a potem w funkcji do bin searcha przekazujesz m.(To nie psuje chyba, ale po co, prosisz się o kłopoty!)

Po co w pętli w 14 lini napisałeś long long i, skoro masz typedef ll i wcześniej piszesz ll?(nie mówię, że jest to błąd, ale po co)

Ostatnia rzecz jest taka, że paskudnie piszesz binary searcha. Moim zdaniem ładniej pisząc bin searcha środek liczyć w środku pętli, a nie przed i zwracać początek / koniec (zależy od przypadku), ale ogólnie mój sposób jest taki: jak chcę znaleźć najmniejszy pasujący, to kod do bin searcha wygląda tak:

    int poczatek = 0, koniec = 1e6+1, srodek = 0;
    while(koniec - poczatek > 1)
    {
    	srodek = (poczatek + koniec) / 2;
    	if (ile_punktow_kratowych(srodek) >= m)
            koniec = srodek;
    	else
            poczatek = srodek;
    }
    return koniec;

Idea jest taka, że jak chcesz znaleźć liczby w przedziale [1,N], to początek ustawiasz na 0, koniec na N+1, możesz zastanawiać się dlaczego na 0 i N+1, zamiast 1 i N? Odpowiedź jest prosta. Jeżeli chcę zwracać koniec i odpowiednią odpowiedzia jest koniec = 1, a dam początek = 1, to koniec nigdy tam nie dojdzie - WA, analogicznie z początkiem na N. Oczywiście można to if-ować jak ty, ale po co. Musisz być tylko uważny, kiedy zwracasz początek kiedy koniec - w zależności czy chcesz znaleźć pierwszy czy ostatni pasujący, oraz, żeby nie przesadzić np. cofając początek o 2 do tyłu, bo przy tablicy może Ci indeks spać z [0,n-1], ale jak dasz jeden wcześniej początek, i jeden dalej koniec, to środek będzie w przedziale[początek + 1, koniec - 1], więc nie będziesz miał idx-ów poza tablicą, ale jak już dasz, np początek = -3 zamiast -1, to ujemne idx-y i signal możesz dostać. Reasumując: początek jedno wcześniej, koniec jedno dalej, i elo.  Możesz zastanowić się, czy taka implementacja bin searcha Ci odpowiada, ja tak piszę ciągle.

Edit: oczywiście zamiast przekazywać zmienną R jako long long-a zamist int-a, możesz przekazać int-a i rzutować w trakcie liczenia R*R na long long-a, w sensie (ll)R * (ll)R, tu to raczej nie ma znaczenia, ale jak przekazujesz dużo zmiennych do funkcji, to przekazanie long long-a może raczej trochę opóźnić czas niż przekazanie int-a.