Daca ati amintit de Warcraft ... sunt fani DoTA pe aici (in afara de mine )?

Intra si quick sort in timp, trebuia doar sa il faci random.

Articol despre teoria jocurilor ma ofer eu sa scriu. Oricum, ma gandesc la ceva mai amplu, deci cred ca sunt sanse sa il termin in urmatoarele 3-4 saptamani.

Rezolvarea este in O(N log N), pentru ca e nevioe de o sortare, si intra in timp.

Am terminat articolul referitor la rotatie lexicografic minima ( http://infoarena.ro/rotatie-lexicografic-minima ), si am adaugat un link si pe pagina de articole. Daca sunt necesare modificari, anuntati-ma  .
O sa incep sa lucrez si la restul articolelor (mai putin cel despre arbori de intervale) dupa ONI.

Sunt interesat si eu, deocamdata sa scriu cele 4 articole (arbori de intervale, cautari ortogonale, rotatie minim lexicografca si ghid complet pentru concursuri de informatica ).
Daca vreti si aveti aprobare pentru articole predate la loturi, pot sa transcriu si de acolo.

Se pot lua 80 de puncte (probabil si mai mult) cu un algoritm O(N^2*M) in felul urmator: pentru fiecare punct se calculeaza distanta minima pana la cele M drepte, apoi se adauga in multimea acestui punct toate punctele ce se afla la o distanta mai mica decat aceasta valoare. Apoi pentru oricare doua puncte, daca sunt in multimi diferite, se verifica daca exista vreo dreapta care sa le separe, daca nu, se unesc multimile celor doua. S-ar putea rezolva daca in teste punctele ar fi apropiate de drepte, de ex. la sqrt(2)/2.

De vreme ce pentru multe probleme nu se poate face o diferentiere clara pentru doua solutii cu complexitati diferite, si daca vreti sa impartiti arhiva pe categorii de dificultate, ati putea face variante noi ale problemelor dar care sa aiba limitele variabilelor mai mari, si in acest caz sa se poata face diferentierea clara intre un algoritm optim neoptimizat si un algoritm neoptim optimizat.

Imi spuneti va rog, pentru

Cod:

10
3 4
2 10
15 50
13 18
29 69
13 31
99 88
100 100
44 55
27 11

va da 1511 ?

later edit:
Nu mai trebuie... de fapt da 4. Uitasem ca xor are prioritate mai mica decat == in c++.

La problema joc2, http://infoarena.ro/problema/joc2, raspunsul din joc2.out lipseste.

La problemele expr si coach apar in tabelul de sus mesaje "invalid task id" pe fond rosu in loc de numele fisierelor, autorilor etc.

Imi puteti spune va rog cat va da pentru:

aaaabbbbbbbbcccccddddddeeeeeeeeeezzqqqq

( mie imi da 315... )

"rezultatul se va afisa rotunjit la 7 zecimale exacte". asta inseamna ca se vor afisa primele 7 zecimale exacte, sau ca
ultima ( din cele 7 ) zecimala va fi rotunjita in functie de ce urmeaza? am incercat cam toate modurile de afisare pe care le stiu, si testul 3 tot nu vrea sa imi dea puncte .

E o mica problema de afisare pe pagina clasament-rating in firefox 1.5.

Am pus poza: http://infoarena.ro/sandbox?action=download&file=snapshot1.png

Din cate am observat, taburile nu se vad bine din cauza rezolutiei mici. Daca pui o rezolutie mai mare ( ex. 1280 * x ), se vad ok.

Pana la urma ramane la voi vinul si berea . Sau mai ramane valabila oferta dupa ce se pun problemele in arhiva? . Cred ca cei mai multi au luat probleme in ordine, crezand ca sunt ordonate dupa dificultate, ca la concursurile anterioare de pe infoarena. Oricum, concursul a fost foarte bine organizat, problemele interesante, eu am numai cuvinte de lauda... cine stie, poate mai faceti unul peste vreo luna-doua. Felicitari oricum pentru munca depusa !

A cam disparut articolul cu ideile de rezolvare. Din cate am vazut, a disparut orice articol ce avea legatura cu Summer Challenge 1.