Solutii la concursul acm 2013 etapa nationala partea I

[•Cosmin]

http://www.infoarena.ro/blog/acm-2013-etapa-nationala

[•scipianus]

Normal stiu ca nu se posteaza surse pe forum,dar presupun ca asta e referitor la problemele din arhiva. Daca nu e asa,va rog sa-mi spuneti.
Am intampinat niste probleme la taskurile J si K si as dori va rog sa se uite cineva care a facut problemele daca are timp si sa-mi spuna ce gresesc la implementare (mai ales la K; poate ca la J nu e asa inteligibila sursa mea)

J : http://pastebin.com/zRbGVq4a
K : http://pastebin.com/80WjV2rZ

Multumesc anticipat

[•S7012MY]

Normal stiu ca nu se posteaza surse pe forum,dar presupun ca asta e referitor la problemele din arhiva. Daca nu e asa,va rog sa-mi spuneti.
Am intampinat niste probleme la taskurile J si K si as dori va rog sa se uite cineva care a facut problemele daca are timp si sa-mi spuna ce gresesc la implementare (mai ales la K; poate ca la J nu e asa inteligibila sursa mea)

J : http://pastebin.com/zRbGVq4a
K : http://pastebin.com/80WjV2rZ

Multumesc anticipat

Nu vad nimic evident, dar in loc de map<int,bool> poti folosi set

[•Cristy94]

La problema K (cu trenurile) enuntul a fost destul de prost formulat, de aceea multi nu au trimis (trebuia sa citesti de multe ori sa iti dai seama ce vrea sa zica problema).

Oricum, frumoase probleme

[•PlayLikeNeverB4]

Normal stiu ca nu se posteaza surse pe forum,dar presupun ca asta e referitor la problemele din arhiva. Daca nu e asa,va rog sa-mi spuneti.
Am intampinat niste probleme la taskurile J si K si as dori va rog sa se uite cineva care a facut problemele daca are timp si sa-mi spuna ce gresesc la implementare (mai ales la K; poate ca la J nu e asa inteligibila sursa mea)

J : http://pastebin.com/zRbGVq4a
K : http://pastebin.com/80WjV2rZ

Multumesc anticipat

La J nu iti este bun comparatorul. Pentru setul tau, toate elementele cu acelasi first[] sunt acelasi element. Deci, cand stergi unul, le stergi pe toate.

Cod:

8 3
1 2 3 4 5 4 5 1

Cod:

2

La K nu faci bine lazy update.

Cod:

1
5 7
3 5
3 5
3 5
1 5
1 5
1 2
1 5

Cod:

Case 1:
1 2 3 4 5 6 

[•scipianus]

Multumesc mult pentru timpul pierdut pe citirea surselor mele
La J da,ai dreptate,eu ma gandisem la asta si am zis ca valorile din first sunt diferite,dar asta era doar pt valorile din vector,alea din afara le-am pus n+1 pe toate Am incercat acum cu set punand valori diferite si cu multiset,dar in ambele variante iau TLE. Ma rog,macar acum merge corect

La K ce e gresit in functiile de la arborele de intervale ca principiu? Intreb asta fiindca nu am prea implementat pana acum lazy update

[•PlayLikeNeverB4]

Ruland pe testul dat de mine iti dai seama ca ar trebui sa faci update si la fiii nodului la care te opresti. Deci schimbi putin semnificatia vectorului lazy.

[•scipianus]

Am corectat doua chestii si am luat accepted,dar vreau sa fiu sigur ca doar atat era:

- am inlocuit

Cod:

val[nod]=max(max(val[2*nod],val[2*nod+1]);

de la update cu

Cod:

val[nod]=max(val[nod],max(val[2*nod],val[2*nod+1]));

(sigur e bine? sau e doar bulaneala?)
- imi lipsea un newline in plus la afisare dupa fiecare test,de-aia am luat dupa "Presentation Error"

[•PlayLikeNeverB4]

Cred ca e bine.

[•ciprianf]

Vreo idee de rezolvare la problema C - http://acm.tju.edu.cn/toj/vcontest/showp9268_C.html?

[•alexalbu95]

Are cineva idei pentru problema "B.Manhattan Wiring"?

[•S7012MY]

O sa scriu un articol si cu celelalte probleme dupa ce trece bacul

[•popoiu.george]

Si eu iau WA la J si imi merge pe testul lui PlayLikeNeverb4. Am implementat heapuri clasice ca sa evit problema lui scipianus.

Daca vrea cineva sa se uite putin pe sursa poate vede ceva gresit as fi recunoscator.

http://pastebin.com/8X7gsqrS

Multumesc anticipat !

[•PlayLikeNeverB4]

Prima data bagi noul template si apoi te decizi pe care il scoti.  Exista situatii cand acest lucru face diferenta.