Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: CEOI 2008  (Citit de 13530 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Adriana_S
De-al casei
***

Karma: 51
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #25 : Iulie 10, 2008, 14:54:01 »

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. Smile
« Ultima modificare: Iulie 10, 2008, 15:21:45 de către Paul-Dan Baltescu » Memorat

wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #26 : Iulie 10, 2008, 14:58:33 »

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
« Ultima modificare: Iulie 10, 2008, 16:30:47 de către Andrei Grigorean » Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
mariusdrg
Client obisnuit
**

Karma: 70
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #27 : Iulie 10, 2008, 19:00:03 »

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

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #28 : Iulie 11, 2008, 08:55:46 »


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.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #29 : Iulie 11, 2008, 17:38:24 »

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

Suntem primii in clasamentul pe tari!
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #30 : Iulie 11, 2008, 17:41:56 »

Super tare!!  Yahoo! 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?
Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #31 : Iulie 11, 2008, 17:43:48 »

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.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #32 : Iulie 11, 2008, 18:03:54 »

Ah, shit, Zuza nu e polonez  Aha 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
Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #33 : Iulie 11, 2008, 18:05:01 »

Nu, atunci au luat aur fechete si 3 polonezi Smile)

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 Whistle... Sa vedem la IOI Very Happy
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Protoman
Infoarena Monthly
De-al casei
*****

Karma: 119
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #34 : Iulie 11, 2008, 18:32:47 »

la JBOI avem 2160 cu 540 media pe concurent...  Shocked suntem foarte departe de toti ceilalti din cate am auzit de la ei... Sa speram ca asa si e Very Happy
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #35 : Iulie 11, 2008, 18:35:35 »

Super tare. Felicitari  Applause Applause

[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.
« Ultima modificare: Iulie 11, 2008, 18:41:14 de către Savin Tiberiu » Memorat
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #36 : Iulie 11, 2008, 19:28:40 »

Au aparut pe undeva subiectele rezultatele?

LE: Sunt pe site-ul oficial acum.
« Ultima modificare: Iulie 11, 2008, 20:00:58 de către Silviu-Ionut Ganceanu » Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
c_sebi
Client obisnuit
**

Karma: 24
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #37 : Iulie 11, 2008, 20:26:48 »

Jos palaria! Tot respectul!  Applause

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


Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #38 : Iulie 12, 2008, 08:13:34 »

Bravo baieti  Applause succes la ioi  Very Happy
Memorat
gcosmin
Nu mai tace
*****

Karma: 205
Deconectat Deconectat

Mesaje: 307



Vezi Profilul
« Răspunde #39 : Iulie 12, 2008, 19:44:55 »

multumim mult pentru incurajari si felicitari  Smile
sper ca o sa fie bine si mai departe
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #40 : Iulie 12, 2008, 21:36:19 »

Multumim pentru sprijin! Smile
Memorat

Am zis Mr. Green
flmanea
Client obisnuit
**

Karma: 78
Deconectat Deconectat

Mesaje: 68



Vezi Profilul
« Răspunde #41 : Iulie 13, 2008, 20:48:48 »

Felicitari!!!  Winner 1st place
Memorat
mariusdrg
Client obisnuit
**

Karma: 70
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #42 : August 03, 2008, 10:30:43 »

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
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines