La ciclu2 care este numarul maxim de intrebari / test?

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.

Referitor la probleme, ele au fost ok, dar nu cred ca scopul unui asemenea concurs e optimizarea unor solutii de complexitate buna. Cred ca ar trebui sa fiti mai putin stricti la capitolul asta.

E cam mica limita de timp la Triopalindrom. (asta in cazul in care solutia cautata e O(N^2))

Cele 2 triunghiuri pot avea un varf in comun?

Exemplu:

{ (0, 0); (2, 2); (0, 4) } si { (0, 4); (2, 6); (0, 8) }

Nu e cam stransa limita de timp? 

Felicitari, super rezultate! 

Mult succes echipei! 

Un rezultat superb! Felicitari echipei!

Dupa urmatoarele operatii:

Cod:

erase(0, x)
insert(x)

structura este vida la momentul de timp 1?

Structura poate sa contina acelasi element de mai multe ori?

Adica daca efectuez operatiile:

Cod:

insert(x)
insert(x)
erase(0, x)

la momentul de timp 1 structura va fi nevida?

Misto demonstratia! Am inteles, multumesc mult! 

Salut!

Am citit solutia oficiala la aceasta problema, si din cadrul acesteia am scos o observatie de care nu imi dau seama de ce e mereu corecta.
Pentru cei care nu au chef sa citeasca problema si solutia, voi face un rezumat: "Se da un arbore, in care anumite noduri sunt colorate in negru. Trebuie sa se determine setul format din nodurile care reprezinta LCA-urile oricarei perechi de noduri colorate in negru."
Din solutia oficiala a acestei probleme, rezulta ca trebuie facuta sortarea in ordinea parcurgerii DF a nodurilor colorate in negru.
(Functia DF arata cam asa):

Cod:

void DF (int nod) {
if (culoare[nod]==negru) V.push_back(nod);
...
parcurgere_DF_fii;
...
}

Apoi, este de ajuns sa se insereze intr-un set LCA-urile nodurilor negre aflate pe pozitii consecutive in vectorul V. Conform solutiei oficiale, acest set reprezinta set-ul cautat (cel format din nodurile care reprezinta LCA-urile oricarei perechi de noduri colorate in negru din arbore).

Raman recunoscator daca ar putea sa imi explice cineva de ce aceasta tehnica este corecta, iar in caz contrar, sa imi atraga atentia asupra faptului ca poate am interpretat gresit solutia oficiala.

Multumesc anticipat!

Salut!

Cred ca ar trebui marita putin limita la aceasta problema, deoarece am o solutie in O(N*sqrt(B)) (cand B<=10^6) si nu reusesc sa trec de 80 de puncte. Totodata, am observat ca sursele ce au luat 100 recent sunt chiar la limita (48 ms pe testul maxim). Multumesc anticipat!

Legat de mega-evaluatoru ala .. poate sa imi spuna cineva ce ar trebui sa faca?
Iti ia sursa si o ruleaza si iti arata timpul si memoria?
Iti verifica out-ul?
Iti ruleaza pe exemple?

In principal, ideea acelui evaluator ar fi sa iti ruleze sursa si sa iti spuna timpul si memoria folosita pentru exemplu. Nu cred ca ar avea rost sa iti spuna daca sursa ta da raspuns corect pe exemplu, pentru ca sa verifici tu manual chestia asta nu ar fi mare chestie, insa ar fi foarte bine daca acel evaluator ti-ar spune timpul si memoria folosita pe orice test dat de tine.

Am citit acest topic cu atentie, si am vazut multe idei si opinii demne de luat in seama. Insa (si poate sunt eu mai pesimist) nu cred ca multe dintre aceste idei vor prinde viata, deoarece se va ajunge la un moment dat cu aceste idei in fata organizatorilor, care vor recurge la clasicul raspuns "ne pare rau, nu avem bani".

In opinia mea, prima data ar trebui sa se gaseasca modalitati pentru a strange bani,adica sa se inceapa campanii si petitii pentru ca statul sa investeasca mai multi bani in aceste olimpiade (multe probabil vor esua ) si sa se caute sponsori mai seriosi, si mai darnici. Astfel, se va ajunge la un moment dat ca cineva sa spuna: "dispunem de fonduri in valoare de.., asteptam sugestii". In acel moment, ar trebui sa se caute cele mai importante modificari care trebuie aduse sistemului, si care se incadreaza in buget.

Ceea ce vreau eu sa spun e ca degeaba stam cu totii si ne chinuim sa gasim solutii, daca se va ajunge pana la urma la simplul raspuns "nu avem bani, o lasam tot asa".

Da, ai dreptate. Am deschis infoarena cu Internet Explorer si toate cele 3 feature-uri functioneaza. Scuze, greseala mea.

Astazi am intalnit 3 buguri, si nu cred ca sunt de la mine, deorece am intrebat si alte persoane, si toti au intampinat aceleasi probleme.
Bugurile sunt urmatoarele:

1) Syntax Highlighter nu functioneaza. Adica in momentul in care incerc sa vizualizez o sursa, aceasta apare neformatata, incadrata intr-un chenar mic.

2) Pe pagina oricarei probleme, in locul comentariilor apare doar textul "remote content".

3) Tot pe pagina oricarei probleme, nu se pot vizualiza indicatiile de rezolvare. Adica apare butonul "Arata x categorii", dar in momentul in care dau click pe acel buton nu se intampla nimic.

Salut!

Cred ca ar trebui marita limita de timp la aceasta problema, deoarece am bagat solutia oficiala, cu O(sqrt N) pe update si pe query si iau doar 85 de puncte.  In plus, mi-am permis sa trimit o sursa care lua 100 in trecut, si acum ia doar 80 de puncte. ( Am vazut ca sunt surse de 100, cu arbori de intervale, dar nu stiu daca acelea au complexitatea optima worst-case).

Multumesc anticipat!

Eu am facut un DF din fiecare nod S si calculam pentru fiecare nod i hash-ul stringului ce reprezinta lantul S->i si i->S. Daca cele 2 hash-uri erau egale, atunci aveam un palindrom. Problema era ca luam TLE caci faceam operatii modulo. Asa ca mi-am precalculat operatiile de modulo, si, ca prin minune, nu am scapat de TLE .

Graful dat este conex?

Hei, cum se putea rezolva "biperm" prin cuplaj o.O"? Eu n-am gasit decat un algoritm backtracking  .

Considerai pentru fiecare coloana p cele 2 valori care apar pe ea (de pe prima linie si de pe a doua). Duceai muchie de la coloana la cele 2 valori si astfel construiai un graf bipartit pe care aplicai algoritmul de cuplaj maxim.

@speedzeal

Citind topicul acesta, am decis sa analizez cateva din "actiunile" tale (nu stiu daca ar trebui sa folosesc persoana a II-a plural, deoarece nu te cunosc si nu iti cunosc varsta, dar considera tot ceea ce am scris si voi scrie in continuare ca fiind lucruri spuse cu respect).

1) Atitudinea ta

Ai intrat pe acest topic si ai inceput sa iti exprimi opiniile. Ok, e foarte bine, si nu are nimeni nimic impotriva acestui lucru, insa modul in care ai hotarat sa iti exprimi aceste opinii este, in opinia mea si probabil a altor persoane de pe acest forum, unul nu foarte respectuos si cuvenit.

2)

Haha! Cum sa scrii ca 2575 au luat cel putin 0 puncte? Haha! Eu instinctiv citisem 2575 au luat 0 puncte. E ca si cum ai zice 2575 au participat. Cu cat mai mult de comuniste pot fi statisticile astea?

Ok, poate exprimarea folosita in acele statistici nu este cea mai usor de inteles, dar nu inteleg ce legatura are acest lucru cu regimul comunist, avand in vedere ca aceasta statistica este una corecta si zic eu, destul de relevanta.

3)

Anyway, vreo 2000 de oameni v-au urmat sfaturile si au luat 0 puncte ... hehe.

Dupa cum ziceau si alte persoane, nu a fost cineva pe acest topic care sa sugereze participantilor la OJI sa obtina 0 puncte, si nu cred ca exista cineva care sa aiba ca scop indrumarea unor copii spre punctaje nule.

4)

Ah! Ce ne-am face fara nenea ICHB? Bune vremuri traim, cand privilegiul de a invata e doar pentru copiii de grofi, dar orice amarat stie ce-i aia "Stirile Pro TV".

Din nou, partial ai dreptate. Este o scoala privata la care cativa dintre elevi platesc pentru a studia acolo. Dar, din cate stiu eu, sunt multi elevi care studiaza acolo pe baza unor burse obtinute in urma unor rezultate exceptionale la concursuri si olimpiade, iar ceea ce ai spus tu reprezinta o ofensa la adresa lor.

5)

Priviti noua generatie ! Aplauda-te fiule !

Radu Szasz te-a contrazis si a comentat, zic eu, cu bun simt opiniile tale. Insa tu ai recurs din nou la ironie si la ofense adresate, indirect unei intregi generatii de oameni, care nu ti-au facut nimic.


Te rog, asadar, ca in viitor sa iti exprimi opiniile intr-un mod respectuos, precum o fac ceilalti utilizatori ai acestui forum.

Sambata, 16 februarie, de la ora 16:00 are loc concursul COCI Contest #5.

Marti, 29 ianuarie, de la ora 18:00 are loc SRM 568 pe TopCoder.