Daca iti da corect pe exemplul de la problema nu inseamna ca iti da pentru toate

Nu introdu toate nodurile de la inceput, doar pe cele pe care le-ai vizitat. Le introduci pe parcurs pe fiecare.
Asta e greseala cea mai mare... In rest, am modificat <= in < si >= in > (nu ma intreba de ce, dar a facut diferenta de la 80 la 90...). N-am putut pana la 100, dar vezi tu...

Sursa ta modificata: http://infoarena.ro/job_detail/527679?action=view-source

Am avut probleme initial fiindca nu stiam ca daca am de exemplu "FALSE AND TRUE" atunci dupa ce programul meu evalua FALSE-ul nu mergea mai departe deoarece nu avea rost, oricum era falsa expresia. (aveam ceva de genu r=r && functie(); si nu mai intra in functie)
A trebuit sa calculez rezultatul functiei intr-o alta variabila ca sa "pacalesc" programul ca sa nu stie ce urmeaza sa fac cu ea .
Mi s-a parut interesant Nu stiam de chestia asta.

De unde sa stie lumea ca ce gresesti tu? Posteaza ideea sau o parte din sursa de la programul tau... dar a fost deja explicata destul de detaliat ideea mai sus.

1) Raspunsul este: aranjamente de N luate cate K.
2) Construiesti un vector S[ i], cu semnificatia S[ i]=a₁+a₂+..+a_i. Faci cu un for i=1,n : La fiecare pas i cauti j-ul minim astfel incat S[ i]-S[j-1] il divide pe K (adica a_j+a_j+1+...+a_i il divide pe K), 1<=j<=i si daca i-j e mai mare decat diferenta maxima curenta, max=j-i.
3) Citesti cuvintele intr-un vector de string-uri si il sortezi. Apoi, verifici proprietatea ceruta la vectorul sortat. Daca e respectata, se poate realiza, daca nu, nu.

Sper ca sunt corecte solutiile mele
P.S.: Nu iti va da nimeni rezolvari complete. Do it yourself!

A/B = A * B^-1

Tu ai de calculat valoarea % M a sumei.

(A/B)%M= [(A % M) * (B^-1 % M)] % M

Acel B^-1 reprezinta inversul modular al lui B. ( B * B^-1 % M = 1, B^-1 e intreg )
Acest lucru e folositor pentru ca poti retine doar valoarea modulo M a valorii lui A si B fara a avea probleme cu memoria (sa iasa din long long).
Asa ceva  ... sper ca te-a ajutat.

Cat e rezultatul pentru asta?

Cod:

0 0 1000000 100000
-500000 -500000 0 0
-250000 -250000 250000 250000

Am incercat cu 3 surse de 100 si mi-au afisat:
2 dintre ele

Cod:

1398891776 119

cealalta

Cod:

0 0

Nu ar trebui sa fie mult mai mare perimetrul? E ceva ce imi scapa?

Ar trebui puse mai multe comentarii in sursa

Am incercat sa explic algoritmul cat de bine am putut.

http://infoarena.ro/job_detail/521309?action=view-source

(Nu garantez nimic Cititi pe proprie raspundere)

Nu stiu ce ai facut tu acolo cu lista vecinilor, dar e ceva mult mai complicat decat e nevoie... sau poate nu inteleg eu Am vazut ca faci coada alocata dinamic, mie mi-a mers si static. De asemenea... long?

Cum se aloca memoria pentru 100p? Daca folosesc un vector de 10 000 000 elemente iau decat 60 din cauza memoriei.

Eu asa am facut:
v[ i ]= elementul intrat al i-lea in multime (deci, practic sirul pe care il citesc)
H[ i ]= pozitia in sirul v a elementului de pe pozitia i in heap
poz[ i ]= pozitia in heap a elementului de pe poztia i in sirul v
v[H[ i ]]= valoarea elementului de pe pozitia i in heap

Si de aici lucrezi cu v[H[ i ]] cand compari valorile. Vectorul poz il folosesti ca sa stii instant care element il stergi.

Nu poate fi chiar atat de greu daca si eu am inteles )

Cred ca e (si mai mult decat probabil) de la modalitatea in care afli "elementul intrat al x-lea in multime".
Tu lucrezi in Heap direct cu valoarea elementelor si strici pozitia lor cronologica.
Ceea ce trebuie sa faci e sa memorezi pentru fiecare element din sir pozitia lui in Heap si pentru fiecare element din Heap pozitia lui in sir.

Din cate am observat, problema ta e la afisare.

Cod:

    for(int i=1;i<=n;i++)
        if(viz[ i ] == 0)
        {
            tarjan(i);
            printf("\n");
        }

In codul de mai sus, se executa "printf("\n");" doar cand se trece la alta componenta conexa (pentru ca altfel se merge pe lantul de vecinatati in interiorul procedurii).
De asemenea, trebuie sa afisezi si numarul de componente tari conexe, deci trebuie sa retii toate componentele pentru a le afisa dupa ce afisezi numarul lor.
De aici probabil stii ce ai de facut.
Sper ca te-am ajutat. (Mie nu mi-a verificat nimeni sursele )

E exact ca la sah cu opozitia dintre regi (pentru cunoscatori )

Bun articol. Am reusit sa inteleg dupa cateva ore de chinuiala. Pana la urma mi-am dat seama ca defapt algoritmul nu face decat sa caute in mod normal sirul N in M si verifica daca cumva exista mai multe potriviri care "se suprapun". Functia pi arata urmatorul loc unde e posibila aceasta suprapunere.

omg diferenta dintre 40p si 100p au facut-o 4-5 linii de comentarii <=> 30-40 ms

Greseala pe care o faceam eu (cand luam 40) era ca nu updatam heap-ul in caz ca gaseam un nod deja introdus in heap care are distanta noua mai mica decat inainte. Poate scutesc pe cineva de niste ore pierdute si nervi

Aveti idee de ce imi da Incorect la 5,6,7,9?
Folosesc ideea de pe topcoder.
Sursa mea: http://infoarena.ro/job_detail/498661?action=view-source

Edit: Dupa 3 luni , am gasit greseala: C[y][ x]=0. Am omis si eu faptul ca pot exista arcele x->y si y->x in acelasi timp. Totusi din enunt ("Intre oricare doua noduri x si y exista maxim un arc.") nu prea reiese asta. Sau daca reiese, e mult prea subtil.

Am implementat algoritmul lui Prim dupa solutia oficiala. Diferenta dintre 90 de puncte si 100 a fost o mica modificare in procedura downheap (push parca era in cea oficiala). Mai exact, daca cel mai mic dintre fii era egal cu nodul curent nu le mai interschimba pentru ca (dupa parerea mea) nu avea rost. ( if(D[H[son]]>=D[H[k]]) , acum e doar >). Am gasit aceasta "corectura" doar din noroc. Puteti sa-mi dati un exemplu pentru care ar face vreo diferenta?

Sursa: http://infoarena.ro/job_detail/496180?action=view-source

Chiar nu inteleg de ce nu iau 100... sau macar punctaj mai mare.
http://infoarena.ro/job_detail/495408?action=view-source

Edit: Nu conteaza. Construiam heap-ul gresit. Faceam upheap de jos in sus. Stupid, stupid me.

P.S.: Quicksort sux !

Ma tot chinuiam sa gasesc vreo optimizare la programul meu pentru ca luam 90 de puncte si la ultimul test depasea timpul. Dupa cam o ora de cautari printre sursele altora mi-am dat seama ca in mare sunt la fel. Am gasit solutia in final printr-o amarata comanda de settextbuf. Doar recent am auzit de aceasta de la alti membri printre comentarii, dar habar nu aveam ca poate sa faca o asemenea diferenta. In sfarsit 100! 

Mda, m-am chinuit si eu sa scot timpul in Pascal, dar degeaba Exista macar sursa de 100p pentru Pascal? Daca nu, sugerez si eu (la fel ca si altii) marirea limitei de timp.