Salut!
Am calculat fluxul folosind Ford-Fulkerson si dupa aia am facut o parcurgere din sursa trecand doar prin muchii ce au capacitatea mai mare ca fluxul. In final, afisez toate muchiile ce au un capat viziat si unul nevizitat. Iau 30p cu WA. Imi poate spune cineva daca ideea de rezolvare este corecta? Multumesc anticipat!
sursa: http://www.infoarena.ro/job_detail/993364

Salut!
Dupa cum probabil trebuia sa vezi din solutia oficiala( http://www.infoarena.ro/job_detail/227473?action=view-source ) in functia phi daca N este diferit de 1 ( asa NU insemnand ca e prim neaparat ) afisezi

Cod:

if ( B != 1) return ( p/B * ( B - 1 ) );

nu N-1. Cu aceasta modificare sursa ia 100p.

PS: nu mai calcula in conditia de la while sqrt(B); ori calculezi sqrt(B) inainte de while ori pui i*i<=B ca in sursa oficiala.

Salut!
In caz ca te mai intereseaza gresesti cand scoti un element din deque( cand nu mai poate face parte din secventa ). Secventa fiind de lungime L-1 nu trebuie scos atunci cand
 

Cod:

if( i - dq.front() >= l )
            dq.pop_front();

ci atunci cand

Cod:

if( i - dq.front() >= l - 1 )
            dq.pop_front();

.

Cu aceasta modificare sursa de ia 100p. Bafta!

PS: Dupa parerea mea ar trebui sa modifici si in while deoarece nu are rost sa tin un element in deque daca cel pe care urmeaza sa il inserez este egal cu el.
Ma refer la

Cod:

v[ dq.back() ] < v[i]

care ar trebui sa fie

Cod:

v[ dq.back() ] <= v[i]

Salut!
Am incercat o rezolvare cu teorema lui Lucas astfel: am descompus A, B in baza P si am facut produs de combinari ca in teorema. Avand precalculate factorialele si inversele modulara pana la P in O(P log P) am raspuns pe query in O(1) + descompunerea. Se poate lua 100p cu o rezolvare ca aceasta deoarece eu iau pe testele 14-20 TLE ?

Am si eu o nelamurire despre cum se formeaza graful. Eu am incercat sa parcurg toate nodurile de la 0->2ⁿ-1 si pentru fiecare nod aflu vecini are cam asa:

Cod:

for ( int i = 0; i < ( 1 << N ); ++i )
    {
        for ( int j = 1; j <= M; ++j )
        {
            int nod = i | sarje[j].nr;

            node x = { nod, sarje[j].P };
            G[i].push_back( x );
        }
    }

Problema este ca atunci cand fac Dijkstra de la 0 la 2ⁿ-1, pe exemplu imi da 3(de la nodul 0 folosind sarja 1 merge in 5 si din 5 folosind sarja 2 merge in 7). Am gresit modul de constructie al grafului sau imi scapa altceva...?

In teorie ambele variante au aceeasi complexitate O(N*suma/2) dar in practica se pare ca varianta cu vectorul de sume este mai rapida.
http://www.infoarena.ro/job_detail/991009 - aceasta este rezolvarea din arhiva educationala adaptata la problema asta si ia 40p asa ca se pare ca nu sunt la fel ce rapide.

La dinamica ta nu stiu ce mai poti optimiza dar poti lua 100 cu o alta abordare de dinamica.
Tii un vector format[ i ] = 1 daca poti forma suma i si 0 altfel. Si faci ceva de genul:

Cod:

format[0] = true;

    for ( int i = 1; i <= n; ++i )
    {
        for ( int j = suma_elemente/2; j >= 0; j-- )
                if ( format[j] )
                {
                    format[j + v[i]] = 1;
                }
    }

Daca tot nu iti iese scrie-mi in privat si mai iti explic...

Am si eu o nelamurire: Dijkstra cu costuri mici implementat ca in articolul din GInfo ia 70p cu 3 TLE. Daca scot functia de stergere din vechea lista ( ceea ce teoretic este o greseala ) ia 100p. Asa ar trebui sa se intample sau nu sunt propuse testele astfel incat astfel de solutii sa nu ia 100?

Asta pentru ca poate a fost imbunatatit compilatorul...

Am si eu o problema la: http://www.infoarena.ro/problema/incantatii ; nu are sectiune de comentarii asa ca scriu aici.
Am incercat diferite implementari: codificarea grupelor de 3 caractere in int-uri, sort-ul din STL ia 80p cu TLE cu O(9*NlogN) si diferite versiuni de radix sort care nu iau mai mult de 50 de puncte cu MLE/TLE.
Poate cineva sa-mi dea un hint legat de rezolvarea problemei sau sa-mi explice/arate o implementare de radix sort corecta care sa nu consume prea multa memorie?

Da acel warning se refera ca nu ai atribuit nici o valoarea iteratorului; daca tot nu iti trebuie poti sa nu-l mai pui, lasa asa:

Cod:

for ( ; itA != A.end(); itA++)

Am si eu o nelamurire: optimizarea pentru 100p nu e de fapt algoritmul lui Dinic?

Salut, salvez muchii logaritmate si apoi fac flux maxim folosind Ford Fulkerson. Poate cineva sa-mi spuna daca gresesc ca idee sau daca gresesc ca precizie pe undeva. In plus, as fi recunoscator deca mi-ar explica mai detaliat "Flux maxim prin scalare" deoarece din articolul cu solutii nu am inteles prea multe.

Am si eu o intrebare legata de muchiile din graful in care se cauta ciclul: muchie este i->j cu i si j citite din fisiere sau i->k cu i->j si j->k cele 2 taste din fisier?

Multumesc de raspuns, se mai gasesc testele/solutii de la CEOI 2000 pe undeva ca pe site-ul Universitatii Babes-Bolyai nu mai exista nimic?

Am si eu o intrebare: care este algoritmul care determina numarul minim de muchii ce trebuie adaugate la un graf( si ce muchii ) pentru a deveni biconex?

Am luat 70p folosind si algoritmul lui Tarjan si cel al lui Kosaraju pentru componente + backtracking. Se poate lua 100p cu backtracking ?

In privinta vitezei nu o sa ma cert cu tine pentru ca nu cunosc atat de bine subiectul dar nu inteleg cum un limbaj poate fi mai plictisitor ca altul sau mai performant in functie de numarul de linii de cod.
Si ca sa raspund totusi la subiect...nu o sa stea nimeni sa faca subiectele ( mai ales limitele ) pentru 5 limbaje diferite la olimpiada si nu o sa caute nimeni sa vada ce functii sunt implementate in ce limbaje ( de exemplu sortari sau diferite structuri de date ).

PS1: Nu este o lauda sa te angajezi la Microsoft si sa nu fi auzit de C/C++.
PS2: Tu inveti Java pentru tine sau ca sa o folosesti la olimpiada?

Problema nu se rezolva cu permutari ci cu produs cartezian. Tu ai 3 multimi: S-multimea subiectelor, P-multimea predicatelor si C-multimea complementelor. Tu trebuie sa generezi toate triplele de forma (a,b,c) cu a apartine S, b apartine P si c apartine C.
Acum, cum faci back-ul? Ceva de genu:

Cod:

back(nivel)
{	
	if(nivel==4) //am pus si subiect si predicat si complement
		afisare();
	else
		{
			for ( int i = 1; i <= M[ nivel ][ 0 ]; i++ ) //M[nivel][0] = cardinalul multimii M[nivel], multime in care stochezi cele 3 multimi S,P,C; ai un masiv 3-dimensional unde stochezi sirurile
			{
				st[ nivel ] = M[ nivel ][ i ];
				back(nivel+1);
			}
		}
}

Daca nu iti iese sau ai nevoie de ajutor la ceva...sa-mi spui. Bafta!

Am si eu o intrebare: am calculat cei doi vectori nr[ i ] = numarul de noduri din subarborele nodului i si sum[ i ] = distanta pana la toate nodurile din subarborele nodului i dar nu imi pot da seama cum pot afla suma distantelor de la un nod de la cele care nu sunt in subarborele sat. Imi poate explica cineva va rog frumos cum s-ar calcula ?

Nu neaparat...gandeste-te ca pe un sir aproape sortat MergeSort-ul e O(NlogN) pe cand BubbleSort-ul e aprope liniar....Nu exista un cel mai bun algoritm de sortare ...toate au cazuri particulare pe care nu sunt cele mai bune

PS: MergeSort-ul este sigur O(NlogN) pe orice tip de sir asa ca da...e destul de bun

Problema 3 se rezolva cu descompunere in factori primi: pentru fiecare numar il descompui in factori primi si retii cati de 2 si cati de 5 apar in descompunerea tuturor.
Rezultatul este minimul dintre contorul de 2 si cel de 5.

Te complici aiurea cu toate functiile alea...din punctul mea de vedere iti trebuie doar o functie care sterge caracterul de la pozitia i: strcpy(s+i,s+i+1);
Avand functia asta trebuie doar sa faci 2 parcurgeri de la inceputul sirului si de la sfarsitul sau si cand gasesti o consoana o stergi si iesi.
Ti-am atasat programul care face asta dar incearca mai intai sa-l scrii singur si daca nu iti iese uita-te pe rezolvarea mea. Succes!

PS: nu abuza de pointeri decat daca nu ai cum scapa

OK...multumesc de raspuns nu stiam ce sa mai cred...

Am rezolvat problema si pe primul exemplu imi da 3 1...pot fi mai multe raspunsuri corecte sau ...?