Mi-au placut subiectele. Cam mici limitele de timp si memorie la unele probleme si cam mari la altele, dar per total a fost ok. Astept urmatoarele runde. 

Se garanteaza ca nodurile sunt etichetate cu numere de la 1 la N? Sau nu neaparat? (de exemplu, N = 4 si nodurile sunt etichetate cu 3, 4, 5, 6)

Cod:

int n;
int v[102];

cin >> n;
for(int i = 1; i <= n; i++)
    v[i] = i * 2;

Am inteles asta, asa am rezolvat si eu problema in timpul concursului. Dar vreau sa stiu cum s-ar rezolva problema daca limitele ar fi mai mari (peluza infinita si N = 50, de exemplu).

Pai eu afisam 10^14 + 1 si luam 100. Nu pare prea corect. De exemplu, daca N e mai mare de 30, cum s-ar rezolva?

Cum se rezolva de 100? Eu fac asa pentru 80 de puncte: sortez vectorul a si iau valoarea maxima (fie ea MaxVal). Apoi, pentru fiecare valoare a[j], iau toti multiplii sai <= MaxVal si ii caut binar in vectorul a. Daca am gasit vreun multiplu al lui a[j] la pozitia m, inseamna ca am muchie intre j si m in graful pe care il construiesc. Raspunsul este egal cu numarul de componente conexe din graf, lucru pe care il rezolv cu BFS. Vreo idee pentru 100? Se face altfel sau trebuie un pic optimizata ideea mea?

Cum se face problema asta corect?

Concursul a fost ok. Probleme frumoase cu grad variat de dificultate. Mi-a placut.
Felicitari!
P.S.: Astept mai multe concursuri pe infoarena! 

L.E.: Mi-a placut faptul ca problemele au avut ca tema meciul Grecia - Romania, pacat ca "fotbalistii" nostri nu au fost in stare de mai mult.

Foloseste o stiva in varful careia sa tii tipul ultimei paranteze deschise, iar cand intalnesti o paranteza inchisa verifici daca este de acelasi tip ca cea din varful stivei si o elmini. In cazul in care paranteza din varful stivei nu coincide cu paranteza intalnita, sirul este gresit parantezat. La sfarsit mai ai de verificat daca stiva este goala.

Incearca sa refaci solutia pornind de la final (cand matricea este goala); gandeste-te ce se intampla cand asezi o bila pe tabla (daca se unesc componente conexe).

Pe campion nu merge citirea din C++, decat daca ai putine valori de citit, altfel iei TLE. Nu prea ai cum altfel decat cu citirea din C, asta daca nu vrei sa ramai la Pascal. Dar chestia cu citirea din C++ se intampla numai pe campion; pe infoarena sau la concursuri si olimpiade nu o sa ai probleme de genul.

Felicitari!

Mult succes!

Felicitari!

Succes!

De ce dintre urmatoarele 2 functii de cuplare

Cod:

inline bool pair_up(int x) {
    if(used[x])
        return 0;
    used[x] = 1;
    for(size_t i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if(!R[y]) {
            L[x] = y;
            R[y] = x;
            return 1;
        }
    }
    for(size_t i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if(pair_up(R[y])) {
            L[x] = y;
            R[y] = x;
            return 1;
        }
    }
    return 0;
}

si

Cod:

inline bool pair_up(int x) {
    if(used[x])
        return 0;
    used[x] = 1;
    for(size_t i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if(!R[y] || pair_up(R[y])) {
            L[x] = y;
            R[y] = x;
            return 1;
        }
    }
    return 0;
}

prima este mai rapida?
Cu alte cuvinte, de ce este mai rapid ca intai sa cuplez nodul x cu un nod catre care am muchie si nu este cuplat, iar abia apoi sa incerc sa-l cuplez cu un nod catre care am muchie si pe care-l decuplez de nodul cu care acesta era cuplat?

Da, cred ca ai dreptate. Am omis faptul ca ordinea in care formezi subsirul conteaza. Aveam senzatia ca merge pentru ca in timpul concursului cand am implementat aflarea subsirului maximal in N^2 (deci complexitatea totala N^3) mi-a trecut toate testele pe care n-am luat TLE

Vreau si eu o parere despre solutia mea:
M-am gandit sa aplic o strategie greedy; la fiecare pas (adica la fiecare poza facuta), incerc sa fac in asa fel incat sa se vada cat mai multe clase (care n-au aparut si in alte poze), in felul urmator: la inceput sortez elevii din fiecare clasa dupa inaltimea lor si apoi incerc sa sortez clasele in asa fel incat daca clasa i poate fi asezata inaintea clasei j la poza astfel incat sa se vada toti elevii din ambele clase, clasa i va fi pe o pozitie inaintea clasei j in sirul sortat al claselor. Acum incerc sa iau un numar maxim de clase astfel incat sa fie vizibile toate la poza; pentru asta voi face un subsir crescator maximal in K dimensiuni. Dupa ce am gasit valoarea Max = lungimea maxima a unui subsir crescator, marchez toate clasele care au format acest subsir ca si folosite: used[clasa] = true si apoi trec la pasul urmator (urmatoarea poza), unde voi forma din nou un subsir maximal crescator, avand grija sa nu folosesc decat clasele unde used[clasa] = false. Algoritmul se repeta pana cand used[j] = true, pentu orice 1 <= j <= N. Complexitatea totala e Nr_pasi*N*logN = N^2*logN.
Eu am gresit implenetarea in timpul concursului, dar nu gasesc niciun contraexemplu.

Am inteles, mersi!

Pentru:
1 0 2 1
0 1 1 2
1 2 2 3
2 1 3 2
raspunsul e 4 sau 5?

Pe acest test nu exista 7 patrate?
Eu gasesc
(0,0; 1,1)
(1,1; 2,2)
(0,1; 1,2)
(1,1; 2,2)
(2,1; 3,2)
(1,2; 2,3)
si (0,0; 2,2)

Nu stiam ) oricum, cam aiurea 

Succes!
P.S.: de ce linkul catre pagina lui Teodor Mihai Cotet duce pe youtube?   

Pe testul

Cod:

14 15
1 2 5
1 4 9
2 3 3
2 14 8
3 4 4
4 5 8
5 6 10
5 8 7
6 7 11
8 11 2
8 13 10
8 12 9
11 13 14
11 12 15
11 14 10

imi da (cu sursa de 100p)

Cod:

24
2 4 1 
3 4 3 2 
2 4 5 

Cand vezi ca doar tari ca SUA, Rusia, China si Coreea de Sud sunt peste tine, atunci intr-adevar inseamna ca ai realizat ceva deosebit. Macar prin cateva discipline sa ne remarcam si noi  . Felicitari si mult succes in continuare!

Pai eu am complexitate M * (N/K). La fiecare pas iau din intervalul  (pe care inca nu l-am folosit) de cost minim pentru care capatul din dreapta este >= N, apoi marchez intervalul ca si folosit si actualizez N-ul: N -= K. Repet procedeul pana cand ajung cu N la 0.