CEOI 2008

[•Adriana_S]

Rezultate:
Cosmin 451
Bogdan 417
Paul 273
Stefan 202

Cosmin zicea ca deasupra lui ar mai fi zuza si un polonez din cate a vorbit el pe-acolo, dar ca in orice caz argint ia sigur.

[•wefgef]

probabil ca polonezu e Marcin Andrychowicz (a iesit al 6-lea la IOI anu trecut)

Tocmai am vorbit cu bogdan la telefeon:

Zuza e primu cu 520 - cica a luat 150 de puncte cu randomuri
Polonezu pe doi cu 470
Cosmin pe trei cu 451
Bogdan pe patru cu 417

[•mariusdrg]

Super bine s-a reprezentat romania anu asta, suntem primii,nu? sau cel putin in primii 3.  bravo la toti sunteti smecheri..... Nu uitati ca mai vine si ioi-ul sa faceti la fel! 

[•filipb]

La ultima problema trebuie facuta infasuratoarea convexa a gropilor (se demonstreaza ca nu are rost sa construiesti stalpi decat in punctele de pe infasuratoare), iar apoi iese o dinamica cu N^2 stari, recurenta N (in total O(N^3)).

Daca te referi la fence, nu e chiar asa. E intuitiv ca solutia e mereu poligon convex (daca ar fi concav am lua infasuratoarea care contine un numar mai mic sau egal de varfuri si cel putin tot atatea puncte in interior), dar nu e mereu pe varfurile infasuratorii convexe a celor N gauri. Uite un contraexemplu: un patrat cu 2 pomi in interior, de parti diferite a celor doua diagonale, si un triunghi in interiorul patratului care sa contina ambii pomi. E clar ca solutia e triunghiul, deci niciun vf. nu e de pe infasuratoare.

Personal as fi bagat urmatoarea solutie: pentru fiecare punct (sa-l notam O) se considera ca fiind originea si se sorteaza dupa unghi punctele din dreapta lui O. Facem programare dinamica de genul M(i,j) = nr. maxim de pomi continuti intr-un poligon cu i varfuri in care ultimul varf sa fie punctul j. Avem relatia: M(i,j) = maxim(M(i-1,k) + TRI[O-k-j]), unde TRI[O-k-j] este nr. de puncte din triunghiul de varfurile alea. Asta poate fi aflat in O(1) daca preprocesam la inceput pt. fiecare pereche de puncte cati pomi sunt sub segmentul respectiv.
Dupa ce am construit tabloul M raspunsul va fi minim(20 * p + M[p][k]). Desi nu se impun restrictii in algoritmul de dinamica, solutia va iesi mereu un poligon convex (se observa ca nu avem nevoie sa intoarcem trei puncte B, C, D "la stanga", pentru ca exista mereu un alt triunghi care il include).
Complexitatea pt. O fixat este N^3 de constanta 1/2.

Complexitatea totala este 1/2 * O(N^3 + (N-1)^3 + (N-2)^3 + ... + 1^3) = 1/2 * O( [N(N-1)/2]^2 ) = 1/8 * O(N^4), adica cam 12.5 milioane de operatii, care intra intr-o sec. S-ar putea sa mearga si mai repede decat zic, nu m-am gandit.

Felicitari echipei Romaniei. Asteptam sa vedem repartizarea pe medalii.

[•wefgef]

Cosmin - aur
Bogdan - argint
Paul - argint
Stefan - bronz

Suntem primii in clasamentul pe tari!

[•silviug]

Super tare!!  Felicitari baietilor, chiar e un rezultat mare!!

Da cum se face clasamentul asta pe tari? Conform medaliilor ar trebui ca Polonia sa fie prima. Probabil ii batem la suma punctajelor sau cum?

[•wefgef]

Polonezii au un aur, un argint si un bronz.

Suntem singura tara cu 4 medalii. In clasamentul pe medalii suntem cu siguranta primii. Probabil ca si in cel cu suma punctajelor.

[•silviug]

Ah, shit, Zuza nu e polonez  Eu traiam cu impresia ca este.

Atunci chiar e super rezultat! Nici nu mai stiu de cand n-a fost Romania prima la CEOI (poate cand a luat Fechete aur atunci?).

Silviu

[•wefgef]

Nu, atunci au luat aur fechete si 3 polonezi )

Oricum, anul acesta se pare ca Romania va rupe la concursurile de info. Cred ca si la JBOI iesim primii... Eu pun pariu ca si la BOI ... Sa vedem la IOI

[•Protoman]

la JBOI avem 2160 cu 540 media pe concurent...  suntem foarte departe de toti ceilalti din cate am auzit de la ei... Sa speram ca asa si e

[•devilkind]

Super tare. Felicitari 

[later edit] Are cineva subiectele salvate pe comp, ca eu am lipsit de la ceoi by net ca am fost plecat pe la munte, si nu reusesc sa gasesc problemele pe site. De fapt nu gasesc cam nimic pe siteul ala, e cam dubios.

[•silviug]

Au aparut pe undeva subiectele rezultatele?

LE: Sunt pe site-ul oficial acum.

[•c_sebi]

Jos palaria! Tot respectul! 

@devilkind: problemele le gasesti aici http://141.76.28.152/

[•astronomy]

Bravo baieti  succes la ioi 

[•gcosmin]

multumim mult pentru incurajari si felicitari 
sper ca o sa fie bine si mai departe

[•pauldb]

Multumim pentru sprijin!

[•flmanea]

Felicitari!!! 

[•mariusdrg]

cam cu intarziere dar problema de pe uva este 11315, adica
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2290
Aceea care seamana cu de la ceoi din prima zi