@Mira : "munceste cat de mult poti pentru a ajunge sa fii foarte bun pentru tine, nu pentru OJI, ONI, etc.”. "
[...]
Consider ceea ce ai spus o prostie foarte mare deoarece nu suntem la Yoga sau la finalul jocului Double Dragon 2 cand ultimul boss e umbra ta.

In ce clasa esti? 

Pentru ca algoritmul clasic are complexitatea O(N^3) si 2.807 < 3.

Are format normal, 3 probleme de algoritmica, trebuie rezolvate in 3 ore. Exista o impartire pe divizii, Bronze, Silver si Gold. Bronze e open, iar promovarea la o divizie superioara se face dupa ce intr-o runda ai iesit pe unul din primele locuri (variaza in functie de punctaje, dificultatea problemelor, etc).
Mult succes! 

Si eu am facut rezolvarea cu principiul includerii si excluderii dar am luat 80 din 100 din cauza timpului. Este vreo optimizare care trebuie sa o faci sa iei 100 sau ce?
Thanks

Trebuie sa faci in 2^K (eventual cu back recursiv si sa tii cmmmc-ul la parametru), si nu in 2^K * K.

Solutiile mele:

- Walls:
Pentru un tun fixat la (x, y), evident pot trage doar in turnurile care se afla la stinga lui x, si astfel caut binar cel mai din dreapta turn astfel incit sa fie la stinga lui x. Fie acesta TT. Acum ma intereseaza sa caut cel apropiat turn de coordonata tunului (x) din intervalul [1, TT], cu H[turn] >= y.
Astfel fac o cautare binara, limita inferioara = 1, limita superioara = TT. Testez pe intervalul [mijloc, TT] care este cel mai inalt turn (facind un query pe un arbore de intervale), daca acest cel mai inalt turn este >= y, atunci il retin ca solutie (adica turnul in care va urma sa trag) si restring intervalul (limita inferioara = mijloc + 1), altfel nu imi convine si caut intr-un interval mai mare (limita superioara = mijloc - 1).
Daca nu am gasit niciun turn cu propr respectiva, atunci afisez MISS. Sa zicem ca am gasit un turn, il notez cu T. Evident eu trag acum un shot pe linia y a acestui turn T. Imi tin un map<pair<int, int>, int> shot, unde imi notez de cite ori am tras in linia y a turnului x (adica shot[ make_pair(x, y) ]). Acum mai trag o data, deci shot[ make_pair(TURN, y) ] ++. Daca shot[ make_pair(TURN, y) ] = W[TURN], atunci nivelul se distruge, H[TURN] devine = y-1 si updatez in arborele de intervale noua inaltime.
Cum sunt maxim 200.000 de shoturi, in map nu ar trebui sa retin mai mult de 200.000 de entry`uri, asa ca memoria nu ar trebui sa fie o problema (sincer nu am trimis inca sursa caci nu e problema adaugata in Arhiva, deci este posibil sa ma insel ).
Complexitate: N * log^2N.

Astept sa apara problemele in arhiva ca sa vad mai exact cite puncte obtin pe aceste idei. Daca observati vreo greseala, nu ezitati sa ma corectati

Toate cele bune!
Vlad.

Prima parte a solutiei tale (cea cu cautarea binara si query-ul in arborele de intervale) se poate rezolva in O(logN), desi cred ca si O(log^2 N) intra in timp. Faci 2 query-uri pe arborele de intervale. Primul dintre ele iti spune cel mai din dreapta interval complet inclus in intervalul tau de query, care are maximul >= y. In total sunt maxim O(logN) intervale ale arborelui complet incluse in query-ul tau, asa ca pana acum avem O(logN). In cel de-al 2-lea query cautam raspunsul in intervalul gasit in pasul anterior. Stiind ca toate elementele sale sunt "bune" putem face urmatoarea chestie: verificam maximul din fiul drept, daca e mai mare decat y mergem in dreapta, daca nu, inseamna ca cel din fiul stang sigur e bun si mergem acolo. Asta este tot O(logN), inaltimea maxima a arborelui.

Sper ca am fost suficient de explicit. 

Eu am luat 100 asa, nu am avut probleme.

http://infoarena.ro/problema/pscpld

Are solutii la sectiunea Articole. Spor!

http://infoarena.ro/problema/lgput

Succes!

Gata, acum ca v-ati luat de Vlad de pe conturile de surse (si nu numai), comunitatea va va aprecia de 3 ori mai mult  . Serios vorbind, ar fi bine sa incetati, pentru ca cearta asta nu duce nicaieri. In loc sa va bateti capul cu ce mesaj la misto sa postati, ati putea sa ajutati omul sa inteleaga problema, sau sa imbunatatiti explicatia din articol.
E foarte trist ca unii care au ajuns sa se creada "mari bazati" incep sa faca misto in stanga si in dreapta. Stiu ca asta suna ca o chestie spusa de parinti, dar chiar ar trebui sa va revizuiti atitudinea.

Joi, 27 Ianuarie 2011, de la ora 18:00 va avea loc concursul SRM 495 pe TopCoder.

Sambata, 22 Ianuarie 2011, de la ora 19:00 va avea loc concursul Member SRM 494 pe TopCoder.

Sambata, 5 Februarie 2011, de la ora 23:00, va avea loc Facebook Hacker Cup Round 2 .

Duminica, 30 Ianuarie 2011, de la ora 02:00, va avea loc Facebook Hacker Cup Round 1C .

Marti, 25 Ianuarie 2011, de la ora 23:00, va avea loc Facebook Hacker Cup Round 1B .

Sambata, 22 Ianuarie 2011, de la ora 20:00, va avea loc Facebook Hacker Cup Round 1A .

Luni, 31 Ianuarie 2011, de la ora 18:00, va avea loc concursul Codeforces Beta Round #54 pe Codeforces.

Marti, 25 Ianuarie 2011, de la ora 18:00, va avea loc concursul Codeforces Beta Round #53 pe Codeforces.

In perioada 21 Februarie - 3 Martie 2011 se va desfasura runda 7 a concursului .campion.

Duminica, 13 Februarie 2011, de la ora 9:00, va avea loc runda 6 a concursului .campion.

In perioada 17-27 Ianuarie 2011 se va desfasura runda 5 a concursului .campion.

Se poate, dar nu cred ca are vreun efect.

S-ar putea comenta mult pe marginea calitatii problemelor si testelor de la campion, dar stim cu totii aceste lucruri si nu cred ca e cazul sa le discutam aici .

Intr-adevar, s-a modificat intre timp. Este pe 8 ianuarie.

Din cate stiu este pentru prima oara cand Facebook organizeaza aceasta competitie, asa ca nu stiu nici eu prea multe detalii. Personal cred ca va fi ceva asemanator cu Google Code Jam, dar vom vedea.

P.S. Craciun fericit 

In perioada 7-10 ianuarie 2011 va avea loc runda de calificare a concursului Facebook Hacker Cup.

Este posibil sa se creeze cate-un tabel separat la fiecare concurs, sa se inlocuiasca monitorul cu acest tabel (sau sa se dea disable la monitor si sa se creeze un monitor de concurs), iar dupa terminarea concursului sa se adauge noul tabel la cel cu monitorul "mare"?

Ar exista totusi 2 inconveniente:
1. nu s-ar mai putea rezolva probleme in arhiva in acest timp
2. in cazul in care ruleaza mai multe runde in paralel, cum e la Algoritmiada de exemplu, ar fi o mica problema la final cu ordinea inserarii job-urilor in monitor (nu stiu daca baza de date retine si timpul de submisie... daca da, atunci problema asta se rezolva cu o mica interclasare)