BOI 2014

[•GavrilaVlad]

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

Concurentii care vor reprezenta Romania sunt:

• Mihai-Dan Gheorghe
• Radu Szasz
• Mihai-Iulian Andreescu
• Tudor-Petru Tiplea

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!

[•Impaler_009]

Mult succes baieti ! 

[•a_h1926]

Multa bafta! Sa aveti inspiratie si sa fiti cei mai buni! 

[•atatomir]

Mult succes tuturor !
Va urez sa veniti cu rezultate cat mai bune  !!

[•freak93]

Bafta bafta

[•xtreme77]

Mult succes !   

[•dnprx]

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.

[•danalex97]

Succes !

[•GavrilaVlad]

Succes in ziua 2, sa recuperati!

[•eudanip]

Cum sunau subiectele?

[•tzipleatud]

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.

[•Kira96]

Bafta in ziua 2!

[•GavrilaVlad]

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

[•GheorgheMihai]

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

[•klamathix]

@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ă  

[•GavrilaVlad]

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

[•dnprx]

Concursul live al zilei a doua este aici:
http://boi2014.etu.edu.tr:8890/Ranking.html

[•mihaipopa12]

Mult succes! 

[•atatomir]

Felicitari tuturor pentru rezultatele obtinute ! 
Sunt curios cum vor fi distribuite medaliile 
Si ... Suntem cumva primii pe natiuni ? 

[•SRadu]

Mihai Andreescu 
Tudor Tiplea 
Radu Szasz
Gheorghe Mihai

Astea sunt medaliile, oficial.

[•dutzul]

Felicitari !!!! aveti valore multa 

[•a_h1926]

Felicitari tuturor!

[•GavrilaVlad]

Felicitari tuturor!

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

[•omer]

La info clasamentul pe natiuni se face dupa medalii si nu dupa punctajul cumulat? 
Felicitari pentru rezultat!

[•GavrilaVlad]

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.