Din pacate anul acesta nu am reusit sa aflam din ce judete vin sumele. Am incercat la banca sa aflam de unde vin intrarile, dar nu ne-au putut ajuta.

[60]

Din pacate s-a strecurat o greseala in blog-postul initial. Referindu-ne la finala concursului Algoritmiada am scris:

Fondurile vor fi folosite pentru a asigura cazarea, masa si premiile celor mai buni 60 concurenţi, elevi si studenţi.

Nu vrem sa se produca confuzii: numarul finalistilor concursului Algoritmiada va fi in continuare in jur de 40 ca si in anii trecuti, dar numarul exact nu este stabilit deocamdata. Vom decide acest lucru dupa runda 4 de calificare.

Am sters din blog-post numarul exact al finalistilor.

Aici puteti discuta pe marginea postului Vă mulţumim că ne-aţi fost alături şi în 2009! .

Wow... poti uita sa trimiti, sa nu ai timp sa trimiti, sau sa faci chestii dubioase pe retea . Ce-i drept, ce e mai bun decat o salvare pe stick si dupa aia sa astepti la coada sa ti se evalueze cate o sursa pe rand? Aici bineinteles nimic nu poate merge rau.

@Cosmin: de curiozitate... ai pus vreun test cu N = 1000 si matricea plina de 1? eu tocmai am luat 100 http://infoarena.ro/job_detail/400891 si solutia mea face total++.

Raspunsul pentru ultimul test este peste 500 milioane. Merge destul de repede solutia aia a ta.

Am miscorat limita de timp la 1.8 secunde si am reevaluat sursele din arhiva. Imi cer scuze pentru neplacerile cauzate .

Ideea cu 3 note mi se pare foarte buna. Cateva comentarii:

1) Nu cred ca cele mai mici punctaje adica problemele foarte usoare ar putea neaparat fi rezolvate de cineva de la gimnaziu. Adica poate exista o problema foarte usoara dar care necesita ceva cunostinte peste gimnaziu (un arbore de intervale). Deci (pentru Paul) problema setarii dificultatii unei probleme nu se rezolva cum discutasem eu pentru IAP-ul meu, dar este poate mai bine asa.

2) Pentru a nota cat mai obiectiv problemele ar trebui sa facem niste criterii generale de notare. Ceva de genul AVL are nota 10 la cunostinte teoretice, si 10 la implementare, heap are x, etc. De aici e posibil ca nota de cunostinte teoretice sa poata fi dedusa din tagurile pe care incercam acum sa le punem. Cea mai mare problema cu obiectivitatea o sa fie la nota pentru idee dar asta cred ca este rezolvata de faptul ca o sa fie mai multe persoane care noteaza.

3) Si eu cred ca timpul estimat de Wefgef este destul de optimist mai ales ca se bazeaza pe faptul ca noi o sa reusim sa taguim probleme fara oprire timp de 5 ore :p. Deci cred ca o sa dureze destul de mult sa reusim sa notam tot, dar un tagging camp ar ajuta destul de mult.

Citeste mai bine ce inseamna C.

Nu.

Citeste mai bine enuntul.

00111 la sfarsit si 11000 undeva pe la mijloc. Uita-te mai bine.

Limita superioara pentru numarul de muchii din graful rezultat este N * M, nu M^2 cum ai aproximat tu. Fiecare muchie (x, y) poate avea maxim N muchii care intra capatul in x si maxim N muchii care ies din y. De aici putem deduce ca in graful rezultat fiecare nod (adica muchie din graful initial) are cel mult 2 * N vecini (N intra, N ies) => cel mult N * M muchii in total => si complexitatea de N * M a solutiei.

Da. (citeste cu atentie tot enuntul si precizarile)

Strategia pe care o zici tu duce la un efort mai mare ca 18. Deci nu este cea optima.

Da.

@ yrar: Creste cu rata... nush de unde scoti tu +1 ala (tot nu inteleg foarte bine intrebarea dar sper ca ti-am raspuns bine).
@ freak93: Daca scazi cum zici tu vei ramane cu suma totala 2, nu 1.

Reformuleaza. Nu inteleg.

Nu.

Wefgef, cred ca te stresezi prea tare. Problema intuitie si 468 sunt oricum destul de clasice. Iar shgraf e posibil... dar mai asteapta sa vezi cateva probleme neclasice care sa apara si la ei. Atunci poti sa zici ca ne copiaza.

Uf uf...

Da, aparent solutia mea e proasta rau 
In mare parte am uitat de cazul cand daca B nu face mutarea sa minimizeze chestia aia, A-u sa nu poata muta astfel incat sa il evite... ups

pe urmatorul test pica :
1
7
A******
*#####*
******B
*******
*******
*******
*******

Ar trebui sa fie inclus prin teste ca sa nu mai ia 100

[O(N^2)]

O sa postez aici solutia mea pentru ca este diferita de solutia oficiala, si are o complexitate mai buna, dar nu sunt sigur ca este corecta (dar am luat 100 de puncte), asa ca poate ma ajuta cineva sa demonstrez ca e corect sau nu ce fac

Solutie de complexitate O(N^2) timp, si O(N^2) memorie

Fie D distanta minima intre A si B. Dupa cum zice si in solutia oficiala A si B vor incerca sa mearga pe drumurile minime intre cele doua puncte. In caz ca D este impar A, castiga.

Ramane cazul in care D este par. Cand D este par A o sa incerce sa nu ajunga in aceeasi pozitie cu B (pentru ca atunci B va sari peste A) si B o sa incerce sa ajunga in aceeasi pozitie cu A ca sa poata sa sara peste A.

Fie Xa, Ya si Xb si Yb pozia lui A si respectiv B pe tabla. Fie Dx = |Xa - Xb| si Dy = |Ya - Yb|. Ca B sa il ajunga pe A inseamna ca el trebuie sa faca Dx si Dy sa fie egale cu 0.

O sa facem in continuare niste observatii pe o tabla libera de obstacole:

A***
****
****
***B

in acest caz D = 6
Daca A muta la stanga, se observa ca B este obligat sa mute in sus altfel nu-l va putea prinde pe A.
In mod asemanator daca A muta in jos, B este obligat sa mute la dreapta.

Putem observa ca B incearca sa minimizeze MAX(Dx, Dy) si are o singura modalitate de a face acest lucru. Poate ca va ganditi ce se intampla cand Dx == Dy ca atunci o va putea lua in mai multe directii, dar din cauza ca D este par, dupa ce A muta, D (distanta intre A si B) va fi impar => Dx + Dy = impar => Dx != Dy => B muta pe directia care va miscora valoarea maxima intre Dx si Dy. Se poate usor observa ca daca B nu muta astfel va trece pe langa A, si se potriveste foarte bine cu faptul ca atunci cand B il prinde pe A, MAX(Dx, Dy) = 0.

Deci de aici putem deduce ca B o sa se mute in functie de A in modul urmator: trebuie sa ramana pe drumul minim dintre A si B si sa minimizeze MAX(Dx, Dy), si ca pentru aceasta el are o singura mutare posibila la fiecare pas (dupa ce muta A)

Pentru ca B este dependent de pozitia lui A putem sa facem urmatoarea dinamica : din[xa][ya] = true daca A are sigur strategie de castig daca se afla in pozitia (xa, ya) pe tabla. Dupa cum am stabilit mai sus pozitia lui B o sa fie unic determinata si o sa fie un anume (xb, yb). O sa rezolvam aceasta dinamica memoizat pentru ca este mult mai usor sa urmarim poztia lui B la fiecare pas.

O sa scriu un mic pseudo-cod pentru a se intelege mai bine:

bool get_din(int xa, int ya, int xb, int yb)
{
   daca deja_calculat[xa][ya] == true return din[xa][ya];
   deja_calculat[xa][ya] = true;
   
   daca A este in pozitia finala return din[xa][ya] = true;
   
   daca pozitia lui B este deasupra lui A return din[xa][ya] = false; // (xa == xb && ya == yb) <=> MAX(ABS(xna - xnb), ABS(yna, ynb) == 0
   
   pentru fiecare pozitie (xna, yna) inspre care o poate lua A pe drumul minin do {
      calculeaza noua pozitie B (xnb, ybn) pe drumul minim, astfel incat MAX(ABS(xna - xnb), ABS(yna - ynb)) minim posibil
      
      daca get_din(xna, yna, xnb, ynb) == true return din[xa][ya] = true; // reapelam functia pentru un caz mai mic
   }
   
   return din[xa][ya] = false;
}

Explicatie algoritm: ------------------------------------------------------------------------------------------
La fiecare pas mai intai vedem daca suntem intr-o stare finala (ori A este la final, ori A si B sunt pe aceeasi pozitie, caz in care B poate sa sara peste A si sa castige).
Apoi incercam sa mutam A spre o pozitie castigatoare (in acelasi timp calculam si unde ajunge B). Daca gasim o astfel de pozitie inseamna ca pozitia curenta este si ea castigatoare, altfel pozitia curenta este pierzatoare.

La inceputul functiei verificam daca cumva am mai calculat starea curenta pentru a nu o calcula din nou. In aceasta consta memoizarea. Pornim de la starea initiala (cea mai mare) si ne mutam spre starile mai mici si chiar finale si nu invers cum facem la majoritatea dinamicilor nememoizate.
-------------------------------------------------------------------------------------------------------------

Se mai observa ca chiar daca B nu poate miscora la acest pas MAX(Dx, Dy) nu inseamna ca pierde neaparat pentru ca drumul intre A si B poate fi unul serpuit din cauza obstacolelor. De genul:

A**********
***********
***********
****###*###
****#***###
****#*#####
****#*#***#
****#*#*#*#
****#***#*#
****#####B#
****#######

Acest ultim caz ma face sa fiu nesigur pe solutia mea pentru ca din cauza drumurilor serpuite conditia de mai sus pentru drumul parcurs de B devine un pic cam aiurea, dar ma gandesc ca atunci cand A si B vor fi cumva intr-o pozitie mai apropiata fara un drum serpuit intre ele atunci acea conditie conteaza si pana atunci nu, pentru ca pana atunci nu conteaza foarte mult pe unde o ia fiecare ca tot acolo o sa ajunga. (nu prea are sens ultima fraza dar nu stiu sa formulez mai bine ).

Foarte tare concursul. A fost totusi destul de greu (am avut un pic noroc ca am luat 300: facusem ceva asemanator cu posta candva mai demult (nu cred ca o scoteam altfel)).
Singura parte nashpa: nici un pic de detailed feedback : macar cel mai mic test sa vedem ca am afisat bine si ca merge treaba. Nicaieri nu mai e fara nici un fel de feedback (e macar pe exemplu).
In rest toate bune si frumoase. Multumesc pentru ocazia de a ne mai antrena un pic pentru IOI

Keep up the good work 

Woo hoo... let's do this... mai particip si eu la un concurs infoarena 

Era gresit, e ok acuma.

S-a modificat exemplul. Acum respecta conditiile.

DA