Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: BOI 2014  (Citit de 11952 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
GavrilaVlad
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 222



Vezi Profilul
« : August 07, 2014, 12:51:19 »

In perioada 10-17 august are loc Olimpiada Balcanica de Informatica in Ankara, Turcia.

Concurentii care vor reprezenta Romania sunt:


Dintre toti concurentii, doar Mihai Gheorghe a mai participat la BOI in anii precedenti, obtinand argint in 2012 si bronz in 2011.

Le uram tuturor mult succes si sa se intoarca cu rezultate cat mai bune!
« Ultima modificare: August 08, 2014, 11:52:57 de către Gavrila Vlad » Memorat
Impaler_009
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #1 : August 07, 2014, 22:02:43 »

Mult succes baieti !  Applause
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #2 : August 08, 2014, 17:17:07 »

Multa bafta! Sa aveti inspiratie si sa fiti cei mai buni!  Winner 1st place Winner 1st place Winner 1st place Winner 1st place
Memorat
atatomir
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 25



Vezi Profilul
« Răspunde #3 : August 10, 2014, 11:01:59 »

Mult succes tuturor ! Smile
Va urez sa veniti cu rezultate cat mai bune  Winner 1st place !!
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« Răspunde #4 : August 10, 2014, 18:55:41 »

Bafta bafta Very Happy
Memorat
xtreme77
Client obisnuit
**

Karma: 7
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #5 : August 11, 2014, 02:00:37 »

Mult succes !  Very Happy  Winner 1st place
Memorat
dnprx
Strain


Karma: 42
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #6 : August 12, 2014, 13:32:52 »

Revin cu cateva modificari, s-au mai acordat niste minute in plus concurentilor din cauza unor probleme de la o problema. Baietii nostri s-au mai zbatut pentru niste puncte, deci punctajele corecte sunt;

Dupa ziua I situatia in clasament este:
1. Un bulgar - 225 puncte
2. Mihai Andreescu - 200 puncte
....
10.Radu Szasz - 87 puncte
10.Mihai Gheorghe - 87 puncte
13. Tudor Tiplea - 82 puncte

Avem deci un aur, trei argint.
« Ultima modificare: August 12, 2014, 15:02:53 de către Dan Pracsiu » Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #7 : August 12, 2014, 13:33:01 »

Succes !
Memorat
GavrilaVlad
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 222



Vezi Profilul
« Răspunde #8 : August 12, 2014, 14:52:36 »

Succes in ziua 2, sa recuperati!
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #9 : August 12, 2014, 17:52:34 »

Cum sunau subiectele?
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #10 : August 12, 2014, 18:26:35 »

Prima problema:

Ai un arbore cu N<=260.000 noduri cu costuri pe muchii si trebuie sa partitionezi nodurile in K partitii nevide astfel incat distanta maxima dintre oricare 2 noduri care sunt in aceeasi partitie sa fie minima.

A doua problema:

Ai un dictionar cu N<=2000 cuvinte cu o lungime totala <= 2000 si trebuie sa numeri cate cuvinte de lungime K<=5000 exista cu proprietatea ca aceste cuvinte contin ca si subsecventa cel putin un cuvant din dictionar.

A treia problema:

Ai N<=100 diamante cu valori 2^0, 2^1, ..., 2^(N-1) pe care le distribui la trei persoane. La fiecare pas dai un diamant persoanei A, B sau C. Fie sumX suma valorilor diamantelor primite pana in acest moment de persoana X. Distribuirea diamantelor trebuie sa respecte conditia ca dupa fiecare pas sumA >= sumB >= sumC.

Codificam o distribuire sub forma: "p1.d1 p2.d2 ... pN.dN" cu semnificatia pi = persoana care primeste diamantul la pasul i si di = indicele diamantului dat la pasul i. Se cere sa afisezi codificarea celei de-a K-a distribuiri in ordine "lexicografica" (K<=10^300).
Sirul "pa1.da1 pa2.da2 ... paN.daN" se considera ca fiind mai mic "lexicografic" decat sirul "pb1.db1 pb2.db2 ... pbN.dbN" daca exista un 1<=i<=N cu proprietatea ca (pai<pbi sau (pai==pbi si dai<dbi) ) si (j==pbj si daj==dbj) pt orice 1<=j<i.
Memorat
Kira96
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #11 : August 12, 2014, 19:56:57 »

Bafta in ziua 2!
Memorat
GavrilaVlad
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 222



Vezi Profilul
« Răspunde #12 : August 13, 2014, 00:44:08 »

Idei de solutii, asa cum mi-au venit mie (selectati textul ca sa vedeti ce scrie, ca sa nu stric placerea celor care vor sa se mai gandeasca)

Problema 1:

Cauti binar raspunsul, dorind sa vezi daca pentru o distanta poti partitiona arborele intr-un numar de maxim K componente. Sa presupunem ca incercam raspunsul X. Ca sa vezi daca poti face asta, faci un DF pe arbore tinand d[ i ] - distanta maxima de la baza partitiei in care se afla nodul i, la nodul i. Daca pentru un nod i exista (1) un fiu pentru care d[fiu]+1 sa fie mai mare ca X, sectionam fiul respectiv de i, (2) daca exista doi fii, fiu1 si fiu2 pentru care d[fiu1]+2+d[fiu2] sa fie mai mare decat X, sectionam de i pe cel cu distanta mai mare. (Later edit - nu taiem maxim un fiu, ci pe toti care respecta una din conditiile de mai sus). Cand ajungem in radacina numaram cate sectiuni am facut, si asta ne da numarul de componente = numarul de sectiuni + 1. Daca acest numar e mai mare decat K crestem distanta, altfel o scadem (din cautarea binara). Reconstituirea e relativ usoara. Complexitate O(N log N).

Problema 2:

Construiesti automatul finit corespunzator dictionarului (vezi Aho-Corasick), eliminand cuvintele care contin alt cuvant drept prefix. Pentru fiecare nod din automat tii dinamica d[nod][lungime][valid]  - cate cuvinte se termina in nodul nod, au lungimea lungime, si valid = 1 daca contin ca subsecventa un cuvant deja existent sau 0 in caz contrar. Recurenta: mergi pur si simplu pe muchiile din nodul curent si adaugi valoarea starii la toti fii, adaugand la lungime 1 si modificand valoarea "valid" in 1 daca se ajunge intr-un nod care este capatul unui cuvant. Pe muchia de intoarcere adaugi valoarea dinamicii din starea curenta * numarul de caractere care nu duc spre fii, FARA a adauga 1 la lungime. Parcurgerea nodurilor este deci in ordinea inversa parcurgerii BF a automatului, pentru fiecare lungime de la 0 la K. Complexitate O(N*K).

Problema 3:

Observatie: nu te intereseaza deloc exact ce diamante ai dat oamenilor - trebuie doar ca diamantul cel mai mare dat lui A > diamantul cel mai mare dat lui B > diamantul cel mai mare dat lui C. Pe observatia asta tinem urmatoarea dinamica:

D[ i ][j][k][l] - numarul de moduri in care poti imparti diamantele incat prima persoana a primit cel mai mare diamant pe i, a doua persoana a primit cel mai mare diamant pe k, intre valorile i si k mai sunt j diamante disponibile, iar sub k mai sunt l diamante disponibile. Recurenta este specifica unei dinamici "inainte" si nu o scriu complet aici, insa se bazeaza pe ideea ca variezi ce diamant dai:

- daca dai diamant nou persoanei 1, ai doua optiuni: fie ii dai un diamant mai mic decat i (si scazi fie pe j, fie pe l cu 1), fie ii dai un diamant mai mare, si cresti pe i si pe j cu aceeasi valoare x variabila incat i+x sa nu depaseasca N. (later edit - daca faci dinamica inapoi in schimb, poti face o suma partiala in functie de x a valorilor din dinamica, reducand complexitatea la O(1) pentru recurenta).
- daca dai diamant nou persoanei 2, ai 2 optiuni: fie ii dai un diamant mai mic decat k (si scazi pe l cu 1), fie ii dai un diamant mai mare si cresti pe k si l cu aceeasi valoare x variabila, fara insa ca k sa depaseasca pe i. (aceeasi reducere se aplica si aici la O(1) pe recurenta)
- daca dai diamant nou persoanei 3, poti doar scadea pe l cu 1.

In toate aceste cazuri, adaugi valoarea starii curente inmultita cu numarul de diamante pe care le poti da pentru a produce acea modificare, la starea noua, obtinuta prin modificarea lui i, j, k si l. Pentru reconstituire, observi din ce stari ai veni pentru operatiile mentionate mai sus, care sunt scrise in ordine lexicografica. Daca la un moment dat K > d[stare_din_care_ai_putea_veni], scazi din K valoarea dinamicii din starea aceea si treci la urmatoarea stare. Daca nu, adaugi operatia la solutii si te muti in starea respectiva. Complexitate O(N^4*numere_mari) - dar cred ca constanta este destul de mica si intra de 100.

Later edit - N-am observat ca nu intra in memorie ce am zis mai sus, si n-am idee cum as putea repara asta...
« Ultima modificare: August 13, 2014, 19:05:30 de către Gavrila Vlad » Memorat
GheorgheMihai
Strain
*

Karma: 24
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #13 : August 13, 2014, 16:11:55 »

@Vlad
La problema 1 nu cred ca ai inteles bine. Daca ai cazul urmator: un nod conectat la 10 fii si costul dintre nod si oricare fiu e 10, iar ce ai cautat tu binar e 15, trebuie sa eliminii pe rand toti fiii, nu doar pe cel mai mare. Pentru asta cam trebuie sa sortezi descrescator fiii pentru un nod si dupa sa vezi primii doi care au suma mai mica sau egala cu ce ai cautat tu. Complexitatea iti iese cam O(N log N log Cmax) si nu era destul de buna. Cu mai multe optimizari am reusit sa am 1.2 secunde, dar limita era o secunda.
La problema 3 se poate o dinamica d[n][j][k] = in cate moduri poti sa pui n numere daca al doilea poate sa aleaga numere din cele mai mici j si al treilea poate sa aleaga din cele mai mici k, n >= j >= k. Exista recurenta destul de usoara in O(N), dar se poate reduce cu sume partiale la O(1). Daca folosesti numere mari cu baza 10^9 intra destul de lejer in timp si O(N^4 * nr_mari) pentru ca ai constanta foarte mica.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #14 : August 13, 2014, 18:34:34 »

@Gem
N-ai nevoie să scoți doar fiii mai adânci de D (ce-ai fixat in cautare binara) / 2? Bine, eventual unul din ei rămâne, dar iese liniar oricum. Nu ai nevoie de sortare.

Baftă multă  Smile
« Ultima modificare: August 13, 2014, 19:01:58 de către Mihai Calancea » Memorat
GavrilaVlad
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 222



Vezi Profilul
« Răspunde #15 : August 13, 2014, 19:02:48 »

@GM: Sunt constient de asta (m-am exprimat prost in postul anterior, modific acuma), dar nu trebuie sa sortezi nodurile; pur si simplu retii cele mai mari 2 noduri la un moment dat. Cand dai de un nod X care da distanta mai mare singur il tai automat fara sa modifici pe cei doi cei mai mari. Cand dai de un nod X care doar din suma face urat, ai doua optiuni: fie e el cel mai mare si il tai, fie e mai mic decat cel mai mare dintre cei 2 retinuti (dar obligatoriu mai mic decat celalat, altfel cele doua noduri retinute ar fi dat anterior suma mai mare decat trebuie), asa ca il tai pe cel mai mare si il inlocuiesti cu X. La o privire mai atenta nici nu trebuie sa-l retii pe al doilea cel mai bun (el serveste doar pentru demonstratie).
Memorat
dnprx
Strain


Karma: 42
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #16 : August 14, 2014, 09:23:10 »

Concursul live al zilei a doua este aici:
http://boi2014.etu.edu.tr:8890/Ranking.html
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #17 : August 14, 2014, 10:28:13 »

Mult succes!  Smile
Memorat
atatomir
Strain
*

Karma: 3
Deconectat Deconectat

Mesaje: 25



Vezi Profilul
« Răspunde #18 : August 14, 2014, 22:00:49 »

Felicitari tuturor pentru rezultatele obtinute !  Applause
Sunt curios cum vor fi distribuite medaliile  Think
Si ... Suntem cumva primii pe natiuni ?  Dancing
Memorat
SRadu
Client obisnuit
**

Karma: 31
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #19 : August 14, 2014, 22:42:47 »

Mihai Andreescu  Winner 1st place
Tudor Tiplea  Winner 2nd place
Radu Szasz Winner 2nd place
Gheorghe Mihai Winner 2nd place

Astea sunt medaliile, oficial.
Memorat
dutzul
De-al casei
***

Karma: 42
Deconectat Deconectat

Mesaje: 119



Vezi Profilul
« Răspunde #20 : August 14, 2014, 23:31:17 »

Felicitari !!!! Very Happy aveti valore multa  Very Happy
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #21 : August 15, 2014, 00:44:57 »

Felicitari tuturor!
Memorat
GavrilaVlad
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 222



Vezi Profilul
« Răspunde #22 : August 15, 2014, 00:48:20 »

Felicitari tuturor!

Nu cred ca suntem primii pe natiuni, cred ca sarbii au doua de aur.
Memorat
omer
Strain


Karma: 9
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #23 : August 15, 2014, 07:30:56 »

La info clasamentul pe natiuni se face dupa medalii si nu dupa punctajul cumulat?  Huh
Felicitari pentru rezultat!
Memorat
GavrilaVlad
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 222



Vezi Profilul
« Răspunde #24 : August 15, 2014, 11:19:16 »

Pai nici asa nu suntem primii, bulgarii au mai mult. In mod normal circula neoficial ambele clasamente (si dupa medalii, si dupa punctaj), insa e mai folosit cel pe medalii.
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

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