infoarena

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

Bafta baieti! Va tinem pumnii :D

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

Succes !!!

Sa le luati aurul!  :)

Mult succes!

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

Bafta  :) sa luati  :winner1:

Bafta!  :banana:

Succes

Mult succes!!! :guns: :rastabanana:

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

Bagati mare. :winner1:

Mult succes !!! :winner1: :winner1: :winner1: :winner1:

Baietii au  :weightlift: mult asha ca sigur iau  :winner1:! Succes!

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 :P.

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

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. 

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! :D

Nu se afiseaza rezultatele dupa prima zi?

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

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

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

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

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.

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)

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

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

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

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.

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

Suntem primii in clasamentul pe tari!

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?

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.

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

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 :D

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

Super tare. Felicitari  =D> =D>

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

Au aparut pe undeva subiectele rezultatele?

LE: Sunt pe site-ul oficial acum.

Jos palaria! Tot respectul!  =D>

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

Bravo baieti  =D> succes la ioi  :D

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

Multumim pentru sprijin! :)

Felicitari!!!  :winner1:

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