Rezolvarea problemei Antobroasca se reducea la a raspunde daca urmatorul sistem de ecuatii are solutii

• Zc + Xa = A
• Zc + Yb = B

cu precizarea ca sunt 3 necunoscute (a, b, c). Pentru a nu avea un sistem in care ai 3 necunoscute si 2 ecuatii vom incerca sa obtinem o a treia ecuatie scazand prima ecuatie din a doua

• Yb - Xa = B-A

Ca raspunsul sa fie afirmativ la intrebarea problemei trebuie ca fiecare din aceste 3 ecuatii sa aiba solutii in Z.

Pentru a verifica daca o ecuatie de forma ax + by = c accepta solutii in Z pentru x si y este suficient sa verifici daca c este divizibil cu cmmdc(a,b) . Aceasta este solutia oficiala a problemei.

De ce daca cele 3 ecuatii au solutii in Z, inseamna ca tot sistemul are cel putin o solutie?

ba nu se vad problemele 

Nu pe tine te intrebam

Ce ati zice daca ati raspunde si la intrebarile de aici? Unele sunt puse de peste 2 ore 

se pot autointersecta segmentele patrulaterului dat?

in momentul in care robert acrisor ajunge pe autostrada acesta trebuie sa se afle la coordonate intregi? 

se considera mutare valida daca un jucator alege o submultime in care se afla si numarul 1?

Am pus niste assert-uri in sursa si i-ul nu respecta restrictiile din enunt. 

cat de mare este T?

serios acuma ca nu mai pot trimite nici la alte probleme soluti pana nu mi-o ia pe aceasta

Avand in vedere ca evaluatorul nu mai functioneaza de la ora 12 (cred ca ai observat asta), tot ce poti face e sa astepti sa revina si apoi iti poti trimite si sursele.

PS: solutii*

[Off-topic] Eu iti inteleg bunavointa si iti apreciez cunostintele din domeniu, dar de ce ai da reply la un post de acum 7 ani jumate? 

Limita de timp nu e putin cam stransa ?

+1

A picat evaluatorul

S-a blocat evaluatorul.

Ar trebui sa mearga ceva de genul:

Cod:

for i:= 1 to n do
    for j:= 1 to n do
       if i * i + j * j = n then afisezi i si j

Sper sa fie ok ca si sintaxa, am vazut ca asa s-ar scrie secventa asta de cod (cu exceptia afisarii, care nu stiu cum se face), eu personal nu stiu pascal.

Poti face 2 foruri cu care sa fixezi a si b si vezi daca a * a + b * b = n.

da, eu am luat 100 cu dijkstra cu priority_queue.

zisesem mai devreme sa pui long long in loc de double, aparent merge mai prost, deci lasa double.

alta faza ar fi ca atunci cand ajungi la destinatie sa opresti dijkstra-ul.

Am reusit sa iau 100, mersi mult Magnvs!  

Se pot lua 100 de puncte cu Bellman-Ford / Dijkstra cu priority_queue? Cu Bellman-Ford am luat 50 cu TLE, iar cu Dijkstra 40 cu TLE, dar nu stiu daca e limita de timp prea mica sau mai trebuie sa optimizez. 

Pentru ca map-ul salveaza valoarea 0 pentru cheia Y daca o astfel de cheie nu exista deja.

Multumesc! 

Nu stiu exact de ce se intampla asa sau macar ce cere problema, dar ar trebui sa ai in vedere ca operatiile principale pe un map au complexitate logaritmica. Daca vrei complexitate medie constanta ar trebui sa folosesti unordered_map.

Ok, multumesc!

Imi cer scuze in legatura cu memoria, folosesc > 32 mb daca fac X += Hash[Y], dar folosesc < 1 mb daca fac X += (Hash.count(Y) ? Hash[Y] : 0).  

Cu valori modulo mai mari + hash de mana + O(N * 100) am reusit sa iau 100 de puncte, desi e cam jeg pentru ca a durat ceva pana sa aleg combinatia potrivita.  

LE: merge si fara bulaneli in O(N * 100).

Poate sa-mi explice si mie cineva de ce secventa de cod (Hash este un map<vector<int>, int>):

Cod:

Hash[Y] ++;

foloseste > 32 mb (iau MLE), pe cand secventa:

Cod:

if(!Hash.count(Y)) Hash.insert(pair<vector<int>, int >(Y, 1));
else Hash[Y] ++;

foloseste < 1 mb de memorie?

Cred ca limita de timp la aceasta problema este cam mica. Am complexitate O(N * C * 26), aceasta fiind si complexitatea din solutia oficiala.  
Initial, am incercat o solutie cu complexitate mai mica, folosind niste codificari, dar si solutia aceasta lua TLE.

Cred ca limita de timp la problema aceasta este cam mica. Am o solutie care are complexitate 2 * (N * log(CoordMax) + 2 * M * log(CoordMax)), CoordMax fiind Y-ul maxim al celor N puncte (cred ca asa este, nu sunt foarte sigur).


LE: am incercat sa reduc CoordMax la N prin normalizare si abia am reusit sa intru in timp pe 5 teste...

Deoarece problemele interactive inca nu sunt disponibile pe infoarena, problema aceasta va ramane ascunsa pana la introducerea acestor tipuri de probleme.

Problema inca nu este functionala,fiindca nu au fost inca implementate problemele interactive din cate stiu.

Din moment ce nu mai este ascunsa, tind sa cred ca au fost introduse problemele interactive.

Iau 0 cu TLE pe toate testele cu o sursa care doar citeste datele de intrare si la fiecare query afiseaza 0. Care ar fi motivul pentru care se intampla asta? Initial ma gandeam ca poate am TLE din cauza solutiei mele, dar se pare ca nu este asa.  


LE: Cred ca merita mentionat faptul ca sursa oficiala de 80 de puncte a lui Mugurel Andreica ia 0 cu TLE.