Da, ai dreptate. E bine ca din implementarea normala de flux, cele care nu sunt legate la nicio nod "uniune" oricum nu au cum sa trimita flux, fara a trebui sa fie considerat caz particular.

Foarte reușită problema PQ.
Problema Tribut a avut enunț greșit (încă are) și anume:
În „Date de ieșire” e scris „valoarea maximă a tributului pe care o va primi de la toate sistemele solare.” pe când sursa care afișa valoarea maximă a tributului pe care o primește doar de la uniuni comerciale lua AC și cea care socotea și sistemele solare WA. (Ar fi bine să corectați, măcar pentru arhivă).

p.s. Nasol că la Națională au fost probleme din alte concursuri. : )

Este corect enuntul. Este valoarea primita de la sisteme solare, uniunile au doar rolul de a regula cat anume da fiecare sistem solar (gandeste-te la uniunii doar ca la niste reguli pe care le respecta sistemele, tot sistemele sunt cele care dau banii in final ).

Foarte frumoase problemele la aceasta runda, felicitari comisiei

Foarte interesant, felicitari!

O sugestie ar fi ca pentru fiecare utilizator din acel top sa fie si link catre sursa cu care a obtinut acei timpi (un click pe timp/memorie/dimensiune sa duca la sursa respectiva).

Am o intrebare legata de submisiile cu erori de compilare. Se considera ca incercari incorecte? La ACM parca nu se luau in calcul. 

@Cristy94 trebuia sa te asiguri ca sufixul tau nu era mai lung decat prefixul. Vezi cat iti da pe
ababab
ab
ababab

Dadea bine , ca am facut cu o coada in care adaugam pozitia de la care poate sa inceapa urmatorul sufix (just for the lolz).
(am facut problema, am intrebat doar pentru ca am crezut ca mai era vre-un alt caz pe care nu l-am tratat dar a mers)

Felicitari pentru secv10, mi-a placut cazul particular si m-am prins foarte greu de el.
Sigur se incadreaza in precizia ceruta solutia la mafia?

Ce caz particular era? Noi parca am facut KMP + dinamica simpla, fara a trata vreun caz particular.

La mafia trebuia pur si simplu calculata acea formula cu combinari (cu break-urile de rigoare), sau era ceva mai destept ca sa intre in precizie/complexitate?

" atât şirul A cât şi şirul B ca şi subsecvenţă."

Din exemplu reiese ca este vorba de subsir, nu subsecventa, nu?

Frumoasa problema

Puteti adauga solutiile la probleme: http://www.infoarena.ro/acm-icpc-nationala-2014-2015/solutii

Puteti adauga solutiile la probleme: http://www.infoarena.ro/onis-2014/solutii-runda-finala

Voua va mai merg conturile de dreamspark? Mai stiti cumva care era structura adresei de e-mail si parola?

Dupa mine concert2 avea complexitate maxima de O(N*logN). Daca k1>1 si k2>1 atunci chiar intra in O(N), iar daca unul dintre ele era 1 atunci era cel mai lung subsir crescator. Multumesc lui Andrei Heidelbacher pentru observatia de mai sus, acel greedy nu e corect daca k1=1 sau k2=1.

Poti sa explici ideea ta de solutie in O(N)?...

[<]

@Cristy94 In testul 3 nu trebuia sa inlocuiesti niciun cuvant

Pai vad ca mie imi da bine cand nu trebuie sa inlocuiesc nimic Poti sa imi trimiti testul prin PM, chiar sunt curios de ce nu merge

LE: Cred ca am gasit greseala, aveam un < in loc de <=  

Awe http://www.infoarena.ro/job_detail/1157884
Era vreun caz particular pe testul 3?  

Dati refresh, a fost corectat exemplul.

De ce nu mai se poate vizualiza clasamentul? http://www.infoarena.ro/onis-2014/clasament/runda-3

[sort(..., cmp)]

Felicitari pentru runda, unele probleme au fost chiar frumoase

O sugestie ar fi (cum a mai scris cineva mai sus) sa nu se ia submisie gresita pentru eroare de compilare. Noi am trimis o sursa in care foloseam sort(..., cmp) iar in functia de cmp aveam cmp(int &a, int &b). La mine nu zicea nimic, pe infoarena a dat eroare de compilare, parametrii trebuind sa fie si "const".


Clasamentul general cum se calculeaza si cand se actualizeaza?
Cate echipe se califica mai departe?

PS: Am trimis din gresala o submisie de pe contul meu in loc de cel al echipei, sper ca nu are nimic  

Salut, particip pentru prima oara la olimpiada de informatica, iar la OJI m-am calificat la baraj, puteti sa imi spuneti in ce consta acest baraj?

Barajul este organizat de judetul tau, o sa va adunati toti de la baraj intr-o sala cu calculatoare si o sa mai dati inca o proba asemanatoare cu OJI. Daca sunteti 3 la baraj si aveti 2 locuri libere atunci primii 2 de la aceasta proba o sa se califice.

Ca să-ți faci combinările rapid, îți precalculezi toate factorialele mod P și toate inversele modulare ale factorialelor mod P. Apoi răspunsul e fact[n] * invfact[k] * invfact[n - k]  

Mersi mult, chiar am cautat pe net in timpul concursului si nu am gasit niciunde explicat ok. Ar trebui sa fie un articol pe infoarena despre asta, stiu ca a mai fost data de curand o problema la care trebuia acelasi lucru.

LE: Am vazut ca este sumar explicat si aici: http://www.infoarena.ro/problema/inversmodular

Mi se pare foarte natural sa trebuiasca sa iei in considerare si constanta atunci cand estimezi timpul de executie. Constanta nu conteaza cand limitele tind catre infinit sau catre zero, altfel conteaza chiar foarte mult.

@Buleandra Cristian:
Diferenta intre cele doua surse nu este citirea ci faptul ca folosesti stl string (http://www.infoarena.ro/job_detail/1115778?action=view-source). stl string este o clasa wrapper peste char*, ceea ce pe langa niste functionalitati dragute pe care le aduce, face insa ca operatorul [] sa mai faca un pas in plus cand acceseaza un element al sirului. Nu stiu daca e normal sa fie atat de lent, dar macar stim ca nu e de la citire

Da, ai dreptate. Oricum, in continuare parerea mea este ca nu ar trebui ca departajarea sa se faca in functie de aceste mici diferente .

Legat de solutia la DIV4. Solutia era destul de evidenta inca din timpul concursului, insa poate sa puna cineva un link catre un articol care explica cum sa calculezi combinari (n,k) % p eficient? (sa precalculezi folosind invers modular, sau ceva asemanator parca era). Sau nu era nevoie de asta?

Tu folosesti niste operatii de tip modulo pe acolo, care sunt destul de lente, din cate se poate observa. Solutia oficiala este mult mai simpla si mult mai directa. Timpul de executie a fost setat pentru acea solutie si atat.

Stiu, exact asta ziceam. Voi considerati ca solutie corecta doar solutia oficiala, nu si alte solutii de aceeasi complexitate dar cu o constanta putin mai proasta.  

Si, lasand la o parte asta, solutia mea intra in timp citind sirul cu scanf, insa nu intra citind sirul cu cin, deci era la limita solutia aceasta. (oricum e vina mea ca am uitat sa schimb citirea)

Triopalindrom era o problema de nivel B. Pentru rezolvarea ei nu erau nevoie de cunostinte de hashing / KMP. Cititi solutia oficiala pe pagina solutiilor.

Concursul nu a avut ca scop optimizarea unor solutii de complexitate buna.

La problema Triopalindrom, solutia oficiala folosea un O(N^2) curat, din cate se poate observa. Cel mai probabil solutiile care foloseau hashing / KMP, de aceeasi complexitate, erau mult mai lente.

LE: Vom adauga in scurt timp si solutiile celorlalte probleme.

Mi se pare chiar aiurea

Asta sa intre: http://www.infoarena.ro/job_detail/1115596
Asta sa nu: http://www.infoarena.ro/job_detail/1114668

Stiu ca nu e bine sa faci citire cu cin (la concursuri), dar sa iasa din timp pentru o singura operatie de citire a unui sir scurt de caractere?

Felicitari pentru runda!
Mi s-au parut mai ok problemele runda trecuta, acum au fost 3/4 de matematica   

Triopalindrom nu intra in timp cu hash-uri? Nu prea inteleg de ce sunt limitele asa stranse, adica eu cred ca ar trebui sa intre si sursele care au aceeasi complexitate ca cea oficiala, insa nu folosesc aceeasi metoda de rezolvare... (banuiesc ca sursa oficiala e cu KMP). Ar trebui macar sa puneti testele de feedback pe cele mai mari ca daca intra pe ultimul sa stii ca intra in timp/memorie si pe celelalte.

Ce urat : http://www.infoarena.ro/job_detail/1114668


Si etapa trecuta la fel, nu a intrat o solutie cu arbori de intervale, insa intra cea cu AIB.

Nu este absolut de loc cinstit  .Eu m-am chinuit o ora sa o fac sa intre in timp cu limita aceea si voi o mariti acum.Ar trebui lasata cum era. Oricum se putea lua 100, numai ca mai greu.

Nu ai de unde sa stii daca luai 100 pe ea sau nu, sunt doar doua teste la feedback si de multe ori nu sunt cele mai mari...
Oricum la majoritatea problemelor sunt cam stranse limitele, tinand cont ca este un concurs la care depinde si de timpul de rezolvare.

Pentru N=1000000, K=2 o sa ai multe numere in hash.

Vai, cred ca jumate din toti de am trimis ne-am tapit crezand ca exista maxim 1000 distincte xD. Super problema