Eu nu pot sa inteleg de ce la problema asta nu ar intra cu hash-uri. Pana la urma KMP-ul parcurge ambele siruri pentru fiecare sir mic. Asta ar insemna ca face in jur de 3000*1000 + 3000 operatii adica in jur de jumatate din limita de timp. Hash-urile ar procesa fiecare sir o singura data (adica (3000+3000) operatii * operatii cu hash-uri (care mi-e greu sa cred ca sunt de 8000 de ori mai incete decat un O(1) curat)). Chiar daca am lua mod-ul 666013 presupun ca ar intra si in timp si in memorie. Ca sa imi garantez ca minimizez sansa unei coliziuni de valori hash o sa-mi tin 2 valori hash eventual. De asemenea, nu inteleg cum de intra sa iti initializezi o matrice de 3000 pe 3000 la fiecare test (cum zice Visan Radu). De accord ca o matrice de 3000 pe 1000 intra (asa este, de altfel, si solutia mea). Daca cineva cunoaste ceva mai bine astfel de insight-uri si ar vrea sa imi raspunda as fi foarte recunoscator. 

P.S.: Cel mai ciudat lucru este ca daca pun bitset in loc de bool la matricea mea de 3000 pe 1000, merge mai incet.

Deci avem voie sa reordonam sirul, din cate deduc din exemplu?

Deci raspunsul trebuie sa fie >=n (legat de participarea la vot a candidatilor) sau poate fi 1 si daca ai 10 candidati?

Aparent cand intru acum pe site imi zice:
"Forbidden

You don't have permission to access /threads/gordian-knot/ on this server."
http://felicity.iiit.ac.in/threads/gordian-knot/

Pot deci presupune ca iar au probleme cu serverul? 

Update la rating cand se da?
Multumesc anticipat.

Care era solutia "adevarata" la kami?

Problemele au fost dragute, cu exceptia faptului ca la Kami se ia 100 cu o rezolvare de 2 lei, adica brut optimizat

Care era acea optimizare de 2 lei?

Frumoasa runda la 9-10, problema de gandire a fost intr-adevar cea cu patratul magic, cu o solutie ingenioasa in 30 de linii (m-am prins de ea in ultima ora si am zis in acel moment "Genial!"). Interesant ca dupa ce te prindeai de solutie trebuia sa o si reduci de la O(n^4) la O(n^2) (printr-o observatie simpla). Problema mission mi s-a parut foarte simpla ca idee, dar greu de implementat de 100p (se pare ca treaba cu sortatul dupa crossed product merge numai cand unghiurile formate < 180 grade - din acest motiv am pierdut 20p (si locul 1 in clasament  ). Problema kami (jos palaria eudanip ) mi s-a parut cea mai dificila (dar e genul de problema la care iti face placere sa te gandesti cum sa o scoti) - am luat 30p pe ea cu un brut. Am incercat initial sa imi tin un AIB pe sumele alea si sa caut binar, dar mi-am dat seama ca nu merge cautat binar si am abandonat ideea. Sunt curios cum se facea (poate ceva amortizat?). Oricum, runda mi-a placut si as vrea sa stiu si parerile celorlalti.

Problema asta e foarte dubioasa.
Iata doua surse identice, una cu cstdio si cealalta cu fstream:
http://www.infoarena.ro/job_detail/998115?action=view-source (50 puncte)
http://www.infoarena.ro/job_detail/998117?action=view-source (100 puncte)

Poate cineva sa explice diferenta substantiala de punctaj dintre cele doua surse? (eu stiam ca afisarea cu stream-uri e mai rapida, aici este exact pe dos) In timpul unui concurs o astfel de diferenta ar putea afecta destul de mult pe cineva care a implementat corect (si eficient) problema dar nu a stiut ca fara stdio nu se poate lua 100.

Multumesc,
Andrei 

Am facut si eu problema asta si am luat pe ea 100p, explicatia este foarte bine realizata! (mai ales ca poate fi usor generalizata rezolvarea problemei pentru Fn=aFn-1+bFn-2)  
La restrictii scrie ca "0 ≤ K ≤ 1 000 000 000." Cazul k=0 nu se afla in testele problemei desi este particular si multe surse (inclusiv prima pe care am trimis-o) dau raspuns gresit sau se blocheaza pe acest caz. Eu am tratat cazul printr-un simplu if. Cred ca ar trebui incurajata o rezolvare corecta a problemei caci in timpul unui concurs o sursa ce nu trateaza cazul k=0 poate duce la pierderea de puncte valoroase.
Toate cele bune.

Aceeasi problema e si la problema Liste.

L.E.: Din greseala am apasat pe salveaza la Liste.

In general, pe infoarena se pun probleme care pot contribui in mod semnificativ la pregatirea individuala (cu alte cuvinte, e greu de gasit o problema intr-adevar usoara pe infoarena). Iti recomand sa incerci de pe campion.edu.ro/arhiva problemele cadouri, psp, alo, case1, bancomat si barca (daca inca nu ai rezolvat problema capete). Iti urez succes si sa nu uiti niciodata ca toti am fost odata incepatori si ca vei depasi, daca inveti din placere, imediat momentul.

Eu ma refeream daca pagina ar arata asa:
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxxxxxxxx
xxxxxxx

Practic, textul se termina si nu mai avem ce sa despartim in silabe. Eu nu ma refeream sa fie randul in sine mai scurt ci sa nu fie complet.
Reformuland intrebarea, raspunsul este tot NU? (Scrieti DA daca este nu si NU daca este da raspunsul corect)

Multumesc

Ultimul rand poate fi mai scurt?
 

As avea si eu o intrebare. Daca se gaseste cineva binevoitor sa imi raspunda as fi foarte recunoscator:

Daca vrem sa calculam a/b (fractie) mod n, atunci:
a/b = a*inv(b)

In acest topic s-a scris ca inversul nu exista daca b si n nu sunt prime intre ele (intr-adevar 3/4 nu exista mod 7), insa, folosind formula de mai sus, avem ca:
9/3 (mod 6) = 9*inv(3, mod 6) (care, dupa cum s-a zis in topic nu se poate afla caci (3,6)=2)
Dupa logica mea insa, 9/3 (mod 6) = 3 (mod 6) (pe care l-am aflat  )).

Eu, daca l-as avea de aflat pe a/b (mod n) = x (mod n), as face asa:

a (mod n) = b*x+n*y (mod n)
(Impartim toti termenii la (a,b) si rezolvam de aici prin euclid extins (aflam x-ul si y-ul si inmultim iar cu (a,b))). Conditia de existenta a raportului ar fi b|a (nici aici nu sunt prea sigur, corectati-ma).

Mi se pare mult mai dificil de facut chestia asta daca avem a/(b*c). Contraziceti-ma daca gresesc (sau dati-mi o solutie mai simpla decat a mea).

P.S.:Rege nu e Combinari modulare, greseala mea. 

Sunt si eu curios de ceva legat de problema:
Daca Geminski are doua variante de a trage primul glont pe care o va alege? Intreb asta deoarece Cosmin Negrusesti a spus ca dupa ce se trage primul glont, geamurile sparte de el dispar si astfel raspunsurile pentru urmatoarele gloante pot diferi in functie de ce alegere face Geminski pentru glontul cu 2 variante.

Ex. Se poate sa dispara puncte unde se sparg 4 geamuri daca alegem o varianta de la glontul 1 sau sa nu dispara daca o alegem pe cealalta.

Multumesc anticipat.

Mentionez ca am gasit rezolvarea cu Smenul lui Mars deja.

L.E.: Rezolvat!

As ruga un administrator sa mareasca limita de memorie la aceasta problema.

Multumesc,
Andrei

Ma chinui de ceva timp sa imi fac rezolvarea sa nu mai ia Memory Limit Exceeded, am micsorat variabilele, am facut totul posibil. In cele din urma, am trimis urmatoarea sursa si am luat din nou MLE.

Cod:

#include <fstream>

using namespace std;

int main()
{
    ofstream fout("nunta.out");

    fout<<"1\n";
    fout.close();
    return 0;
}

Rezolvarea nu foloseste memorie dar tot ia MLE.  I-as fi recunoscator celui care imi va spune care este problema.

PS.: Sursa este trimisa la http://infoarena.ro/job_detail/878564?action=view-source. Am incercat sa pun si citirea si rezultatul este acelasi (http://infoarena.ro/job_detail/878569). Sursa cu toata rezolvarea este http://infoarena.ro/job_detail/878517.

Multumesc,
Andrei

Vroiam sa zic O(n^2*logn). Greseala mea.

,Andrei

Eu am inteles solutia O(n^2) dar sunt chiar curios de cea in O(nlogn). Cutare binara? Un hint, ceva, va rog.

,Andrei

La orice problema parsarea merge mai repede decat citirea caracter cu caracter. 

Adevarat, dar uneori nu se observa, cum este si aceasta problema. Cred ca asta ai vrut sa intrebi Andrei, doar ca ai formulat un big ambiguu. Astfel, pentru limite destul de mari (de la 1 milion incolo), ar cam trebui sa se simta citirea parsata.

La asta ma referam, multumesc Robert!

PS: Am pus intrebarea pentru ca am facut cu parsare si am observat ca ia timpi la fel de mici ca si solutiile fara parsare.

As vrea si eu sa stiu, de curiozitate, daca la aceasta problema parsarea merge mai repede decat citirea caracter cu caracter. Multumiri anticipate.

Andrei

Cumva toate coordonatele intermediare trebuie sa fie numere naturale sau doar inceputul si sfarsitul, caci nu se specifica si am incorect pe 4 teste?  Daca trimit sursa cu conditia sa fie naturale iau mai mult decat daca o trimit fara aceasta conditie.

Multumesc pentru raspuns. Am reusit 100 cu O(n*suma/2). Vreun  hint despre cum se face in 100*suma/2? Vector de frecventa?

In momentul de fata 4 pagini cu surse sunt in asteptare.