infoarena

Sambata, 2 august, de la ora 19:00 va avea loc concursul Google Codejam Online Round 2 (http://code.google.com/codejam/).

Nu ar fi bine sa se discute problemele care au trecut, daca nu pentru mai mult, macar pentru curiozitatea participantilor? Daca ar fi mai multa lume de acord cu asa ceva s-ar putea face dupa fiecare concurs un topic cu idei.....

Mi se pare o idee foarte buna sa se discute problemele pe forum. Am putea sa le discutam chiar in topicurile din aceasta sectiune, si asa majoritatea au 0 posturi :)

Ok.. pai atunci ii dam bice?
Ideile mele
La prima aia cu arborele boolean... Se putea face o dinamica pe arbore a[ i ][0/1]....
La a 2a e destul de clar ca un punct dintre cele trei ale triunghiului trebuie sa fie intr-un varf din cele 4 ale dreptunghiului mare... si consideram punctul asta primul punct (x1,y1) cu coordonate fie(0,0), fie(0,m)(n,0) sau (n,m). Prin tranzlatie putem sa facem punctul x1,y1 sa fie (0,0)(pt a face calculele mai usoare) si atunci avem 3 puncte (0,0), (y2,x2) si (x3,y3)... deci daca facem determinantul ne da ca aria este 0*y2 + x2 * y3 + y3 * 0 - 0 * x2 - y2 * x3 - 0 * y3 = A * 2; deci x2 * y3 - y2 * x3 = A * 2. Deci iteram cu x2 prin toate cele n posibilitati si cautam binar y2 astfel incat punctul x3,y3 sa ne dea in interiorul dreptunghiului(daca un segment toate punctele care alese ca al 3lea punct sa dea arie egala se afla pe o dreapta, asta din cauza ca inaltime * segm dat e constant).
Si la a4a pt 5 puncte faci toate permutarile.
Daca are cineva alte idei sau poate solutii la ultimele 2 probleme ar fi foarte apreciate.

La a 4a fixezi caracterul care se afla pe prima pozitie in fiecare grup si cel care se afla pe ultima pozitie in fiecare grup (K^2). Apoi faci o dinamica in 2^(K - 2) * N. A[ i ][ j ] = alea minime aparute daca am trecut de primele i pozitii (i <= k) si cu configuratia j (ce permutari mai am voie sa folosesc).

Complexitate totala: O(K^2 * 2 ^ (K - 2) * N).
Sper sa fie ok, nu am implementat.

Pentru problema a 4-a se poate mai bine: O(N*K + K^3 * 2^K).

Initial precalculcam A[ i ][ j ][0 / 1] = cu cat este influentata lungimea totala daca intr-o permutare oarecare urmeaza pozitia i dupa pozitia j si i si j sunt sau nu in acelasi grup de K. => complexitate K^2 * N/K => K*N
Apoi facem o dinamica C[ i ][ j ][ k ] = care este lungimea totala minima daca pentru permutarea cu configuratia binara k prima cifra este i si ultima cifra este j. Recurenta este O(K) (iteram cifra precedenta) => K^3 * 2^K.

Daca se poate si mai bine, as fi curios sa aflu.

La a 3a (Star Wars) merge Simulated Annealing :D