CEOI 2008

[•pauldb]

In perioada 6-12 iulie, va avea loc Olimpiada de Informatica a Europei Centrale. Va exista si o varianta online a competitiei. Probele sunt marti si joi de la ora 9:30.

[•wefgef]

Bafta baieti! Va tinem pumnii

[•Marius]

Baftă! Să daţi tot ce aveţi mai bun!

[•devilkind]

Succes !!!

[•cos_min]

Sa le luati aurul! 

[•CezarMocan]

Mult succes!

[•alex_mircescu]

Bafta multa!
Va tinem pumnii stransi si va asteptam cu medalii cat mai stralucitoare   

[•toni2007]

Bafta  sa luati 

[•wickedman]

Bafta! 

[•tribanp]

Succes

[•c_e_manu]

Mult succes!!!

[•Protoman]

Multa concentrare, inspiratie si bafta cat cuprinde !
Sa va intoarceti cu 4 x  .

[•filipb]

Bagati mare.

[•gabitzish1]

Mult succes !!!

[•MciprianM]

Baietii au  mult asha ca sigur iau  ! Succes!

[•wefgef]

Ce ati facut?

Eu m-am gandit sa le rezolv asa:

1. Prima problema - dominance

Rotesti planu cu 45 de grade si imparti in 2 cazuri ca sa nu mai ai de a face cu romburi, ci cu patrate. Normalizezi si baleiezi: ai evenimente cand incepe si cand se termina un patrat. Complexitate: O(N^2).

2. A doua problema - information

Nu am idee. Ma gandesc sa faci mai multe DF-uri randomizate pentru primul arbore, dupaia verifici daca il poti gasi pe al doilea. Pare ca e bine sa fie primul arbore cat mai "adanc".

3. A treia problema - knights

Trebuie sa vezi pentru fiecare cal daca e pozitie castigatoare sau pierzatoare in jocul urmator: Se da un cal pe o tabla N*N, la fiecare pas unul din jucatori muta calul, pierde cine nu mai poate muta. Desemenea, cel care pierde vrea sa o faca cat mai repede, iar cel care castiga cat mai tarziu. Se observa ca sunt 4 cazuri in functie de restul lui N la 4 pentru a afla daca o pozitie este castigatoare, precum si numarul de mutari. Complexitate O(K).

Aveam de gand sa implementez, dar cand am deschis prima problema si am vazut ca e cu romburi de alea care trebuie rotite.. am zis ca o las balta .

Edit: Joi cred ca veti primi o interactiva, altfel nu s-ar fi chinuit aia sa implementeze sistemul de submit cu interactive.

[•mariusdrg]

Nici eu nu am apucat sa implementez(am avut probleme tehnice), dar cat despre solutii prima e cam cum a zis wefgef, a aparut si pe uva. Iar cea de-a 3a are regula se vede clar dupa brute(acum am facut de curios)! Dar la a 2a nici o idee nu am.. Daca are cineva vreo idee nu ar trebui sa ii fie rusine. Sunt foarte curios cum se face. Ar fi o idee super sa discutam diferite abordari si eventual sa scoatem ceva eficient. 

[•wefgef]

Intr-adevar, prima si ultima problema au fost mai accesibile (desi implementai ceva la ele). Unde ai zis ca e pe uva prima problema? Ai un link?

L.E.: Tocmai am vorbit cu prostu la telefon. Se pare ca nici ei nu au facut a doua problema. Gcosmin e singurul care crede ca a facut atat prima problema, cat si ultima. Sa le tinem pumnii!

[•cos_min]

Nu se afiseaza rezultatele dupa prima zi?

[•wefgef]

Am aflat ca existe probleme cu sistemul de evaluare, din aceasta cauza rezultatele nu au fost inca afisate nici pentru concurentii online, nici pentru cei onsite.

Legat de a doua problema:

In mod evident, trebuie sa existe 2 drumuri disjuncte la muchii intre nodul 1 si oricare alt nod. Din cate am inteles (nu sunt sigur), aceasta conditie este si suficienta pentru existenta celor doua arborescente. Se pare ca era clasica treaba, o demonstrase Edmonds cu nuj cati ani in urma =)).

[•Mira_rt]

Rezultate dupa prima proba:
Bogdan 224
Paul 222
Cosmin 180
Stefan 81

[•wefgef]

Detaliat pe probleme:

Bogdan Tataroiu - 100, 32, 92 - 224
Paul-Dan Baltescu - 35, 87, 100 - 222
Cosmin Gheorghe - 100, 0, 80 - 180
Stefan Filip - 35, 46, 0 - 81

[•CezarMocan]

Felicitari!!! Asa, din auzite, ceilalti cam ce au facut?

[•wefgef]

Am citit problemele de jumatate de ora si ultimele doua mi se par accesibile pentru concurentii romani:

A doua problema este un flux, ai nostri au mai rezolvat probleme in acest gen (din pacate s-a dat si la cpspc 2007 asa ceva). Ne construim o retea de transport, legam de sursa lucrarile si punem valoarea capacitatii sa fie profitul obtinut din fiecare lucrare. Legam fiecare lucrare de masinile care sunt necesare pentru executarea ei si punem capacitate costul inchirierii. Fiecare masina o dublam, is pe muchia dintre noduri punem costul cumpararii. Legam al doilea nod al masinilor de destinatie cu costul infinit. Trebuie gasita o taietura minima in aceasta retea, iar raspunsul este suma tuturor lucrarilor - taietura minima (= fluxul maxim).

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

Asa cum era de asteptat, prima problema este interactiva - si probabil problema grea din a doua zi. Aici se vor decide medaliile de aur in opinia mea. O rezolvare de 50 de puncte pare ca deriva direct dintr-o cautare binara.

[•mariusdrg]

Deci din cele zise de wefgef la problema din prima zi bagai muchie intre toate nodurile(mai putin 1 ) la o destinatie virtuala si capacitate 2 pe muchia aia si daca fluxul mergea atunci aveai , daca nu,nu?
P.s. wefgef e buna solutia ta la a 2a problema dar ar trebui sa editezi, "Fiecare masina o dublam, is pe muchia dintre noduri punem costul cumpararii. Legam al doilea nod al masinilor de destinatie cu costul infinit. Trebuie gasita o taietura minima in aceasta retea, iar raspunsul este suma tuturor lucrarilor - taietura minima (= fluxul maxim)." ar trebui sa fie: Fiecare masina o dublam, si pe muchia dintre noduri punem capacitate costul cumpararii. Legam al doilea nod al masinilor de destinatie cu capcacitate infinit. Trebuie gasita o taietura minima in aceasta retea, iar raspunsul este suma tuturor lucrarilor - taietura minima (= fluxul maxim).
Ca sa se inteleaga mai bine...(nu m-am prins de ea inainte sa citesc misto solutie pacat ca s-a mai dat)