Complexitatea nu ar trebui sa fie O(M*(sqrt(b)+2^X*X)) ?

In caz ca ii trebuie cuiva evaluatoarele... http://ler.is.edu.ro/~cex_is/Informatica/pregatire.html

Nu se elimina nimic din lista, in enunt spune clar ca, la momentul T, se numara circular T pozitii din lista nodului curent.
In exemplu, la momentul 12 ai lista:
1, 6, 2, 9, 5.
Daca o repeti, vine 1, 6, 2, 9, 5, 1, 6, 2, 9, 5, 1, 6, 2, 9, 5, …
Al 12-lea numar e 6, deci la momentul 13 vei fi la nodul 6. Dupa care se face acelasi lucru, insa cu lista de adiacenta a nodului 6 (si se vor numara 13 pozitii), nu tot cu lista asta, daca nu cumva asta e lista nodului 6.

next_permutation tine cont doar de vectorul dat ca parametru, nu de a cata oara a fost apelat. Daca pentru sirul {0,1,0,0} nu ar schimba nimic pe motiv ca se interschimba 0-urile, programul ar intra in ciclu infinit pentru ca vectorul ar ramane mereu neschimbat.

next_permutation genereaza urmatoarea permutare distincta.

Desenul de la explicatie nu este corect.
Dreptunghiul cu aria 50.32 e asta:

Daca primesc un PM si dau click pe linkul din mail ca sa raspund, iar apoi trimit mesajul fara sa schimb destinatarul, o sa il trimit la cel al carui username pe forum e acelasi cu numele adevarat al utilizatorului de la care am primit pm.
Daca bifez sa se salveze o copie in mesaje trimise se vede ca nu s-a trimis unde trebuie.

Pai, sa zicem ca avem un sir pe care il parcurgem pentru a afla functia pi.
Cand suntem la pozitia i, prefixul parcurs pana acum va fi ceva de genul:

abacabadabacaba

Cand trecem la pozitia i+1, se mai adauga un caracter.
pi[i] (zis si k) indica sirul "abacaba" (cel mai lung prefix care e si sufix). Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'd'. Daca se potriveste, inseamna ca pi[i+1] <- k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

abacaba

pi[k] indica sirul "aba", iar k va primi valoarea lui pi[k] si se repeta pasii. Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'c'. Daca se potriveste, inseamna ca pi[i+1] <-k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

aba

pi[k] indica sirul "a", iar k <- pi[k]. Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'b'. Daca se potriveste, inseamna ca pi[i+1] <-k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

a

pi[k]=0, se va face o ultima verificare si daca nici de data asta nu coincide, pi[i+1] va fi 0.
Ideea e ca pe masura ce ne indreptam in sir spre stanga, prefixul de lungime k e acelasi cu sufixul de lungime k, in continuarea caruia trebuie pus caracterul de pe poz i+1.
Pe aceeasi idee se bazeaza si codul Algoritm_potrivire_KMP.

Nu, pentru ca acolo spune de capatul recurentei, unde b=0 si cmmdc=a, iar o solutie pentru a*x+b*y=d <=> a*x+0*y=a, e cand x=1 si y=0, pentru ca a*1+0*0=a.

Nu inteleg de ce sursa oficiala se complica in cazul cand n ramane > 1 si mai calculeaza fractia din formula, pentru ca e clar ca noul factor prim (adica n) apare in N la puterea 1, deci suma divizorilor trebuie sa se mai inmulteasca doar cu n+1.

Sunt cazuri cand intr-un numar din fisierul de intrare apare un factor prim cu exponentul 1 si al carui patrat nu ar intra pe long long si conform formulei o sa se apeleze factorul la puterea a doua.

De exemplu programul nu o sa mearga daca in fisier e numarul 999999999989.

Ar trebui inlocuita partea asta

Cod:

	if(n > 1)
	{
		nd *= 2;
		sd *= ((1LL*n*n - 1) % MOD);
		sd %= MOD;
		sd *= pow(n-1, MOD-2);
		sd %= MOD;
	}

cu asta

Cod:

	if(n > 1)
	{
		nd *= 2;
		sd = (1LL*sd*(n + 1)) % MOD;
	}

Ideea e ca permutarile de lungime N se obtin prin introducerea lui N, pe rand, pe toate pozitiile, in fiecare permutare de lungime N-1. Sa zicem ca il asezam pe N pe pozitia i (i=1,n). Cum N e numarul maxim, el nu are niciun numar mai mare in stanga, deci determina o maxima. In dreapta lui N nu va fi niciun numar mai mare decat N, ceea ce inseamna ca N e cel mai din dreapta numar cu aceasta proprietate. Cum noi vrem ca permutarea sa aiba K maxime, trebuie ca in stanga lui N (pe pozitiile 1..i-1) sa avem niste numere ce alcatuiesc K-1 maxime. Noi cunoastem S(i-1,k-1), adica numarul de permutari ale multimii {1, 2, … , i-1} cu K-1 maxime. Pentru fiecare astfel de permutare, numerele respective pot fi inlocuite cu oricare i-1 valori care sa respecte relatiile de ordine, iar sirul va avea tot atatea maxime. De exemplu, sirul 2, 1, 3 are 2 maxime. Valorile 1, 2, 3 ar putea fi inlocuite cu alte valori, sa zicem 4, 7, 22, iar sirul 7, 4, 22 va avea tot 2 maxime. Noi trebuie sa completam primele i-1 pozitii cu numere din multimea {1, 2, …, N-1}. Oricare i-1 numere din aceasta multime pot respecta relatiile de ordine care vor duce la existenta a K-1 maxime, deci modul de a completa primele i-1 pozitii e C(n-1,i-1)*S(i-1,k-1). Pentru fiecare i numere fixate la inceput, toate celelalte numere de la 1 la N care au ramas vor completa ultimele N-i pozitii, numarul de posibilitati fiind P(N-i). Deci daca N e pus pe pozitia i, exista C(n-1,i-1)*S(i-1,k-1)*P(N-i) posibilitati, adica (n-1)!/((i-1)!*(n-i)!)*S(i-1,k-1)*(n-i)!=(n-1)!/(i-1)!*S(i-1,k-1)=i(i+1)(i+2)…(n-1)*S(i-1,k-1). Raspunsul problemei se obtine dandu-i lui i toate valorile de la 1 la N, adica vom avea S(n,k)=1*2*…*(n-1)*S(0,k-1)+2*3*…*(n-1)*S(1,k-1)+…+(n-1)*S(n-2,k-1)+S(n-1,k-1)
Pentru forma recurenta, se da (n-1) factor comun:
S(n,k)=(n-1)[1*2*…*(n-2)*S(0,k-1)+2*3*…*(n-2)*S(1,k-1)+…+S(n-2,k-1)]+S(n-1,k-1)=(n-1)*S(n-1,k)+S(n-1,k-1).

Ok, mersi pentru raspuns 

Salut!

Am si eu o intrebare: evaluatorul de la ONI va sti sa returneze MLE doar pe o parte din teste cand e cazul (ca cel de pe Infoarena) sau va fi ca cel de pe .campion, unde, daca memoria declarata depaseste memoria maxima, se iau 0 puncte cu KBS 11 pe toate testele?

M-am uitat pe sursa ta si mi-am dat seama ca tu cauti binar pozitia din b pentru fiecare element, ceea ce nu iti garanteaza ca la sfarsit elementele se vor gasi in aceeasi ordine in sirul initial (adica in b nu ai un subsir). De exemplu, la testul 3 programul tau afiseaza:

38
6625742 13552532 18812311 (...)

iar in sirul din fisierul de intrare, numarul 18812311 e inaintea lui 13552532.

1) In enunt scrie:

In cazul in care c nu se divide cu d ecuatia nu poate fi rezolvata in multimea numerelor intregi

Intotdeauna exista o infinitate de solutii.
Daca notam d=cmmdc(a,b), prod1=a/d, prod2=b/d, inseamna ca prod1,prod2 sunt intregi si avem
a*x+b*y=c
prod1*d*x+prod2*d*y=c
d*(prod1*x+prod2*y)=c
Daca d nu il divide pe c, atunci numarul c/d nu o sa fie intreg, ceea ce inseamna ca cel putin unul din numerele prod1*x si prod2*y apartine lui Q\Z, si cum prod1 si prod2 sunt din Z, inseamna ca ecuatia nu admite solutii intregi.

2) In enunt scrie:

In cazul in care exista mai multe solutii pentru o ecuatie, se poate afisa oricare solutie pentru care necunoscutele nu depasesc in valoare absoluta 2 000 000 000

Algoritmul lui Euclid extins e doar o metoda prin care poti sa afli o solutie a ecuatiei intotdeauna cand exista (in Z). Tu poti sa folosesti si un algoritm brut, dar nu o sa iei punctajul maxim.

Daca vrei sa gasesti ciclul de cost minim prin parcurgerea muchiilor in ordinea crescatoare a costului, selectand mereu muchiile pana cand se formeaza un ciclu, nu o sa mearga.
Imagineaza-ti un graf de genul:

Cod:

7 8
1 2 4
1 4 4
2 3 4
2 5 10
3 4 4
5 6 5
5 7 5
6 7 5

Prin parcurgerea muchiilor sortate, primul ciclu care se formeaza e cel alcatuit din arcele 1-2, 2-3, 3-4, 4-1, care are costul 16, iar ciclul de cost minim e format din muchiile 5-6, 6-7, 7-5 si are costul 15.

Al doilea for introduce in suport toate nodurile din stanga care sunt incidente la muchiile din cuplajul maxim, ceea ce asigura ca toate muchiile cuplajului maxim vor avea in suport cel putin un nod. Deoarece suportul minim e egal cu cuplajul maxim, multimea S si-a atins deja cardinalul final, iar in continuare algoritmul doar va scoate din multime elemente pe care le va inlocui cu altele. Sunt parcurse toate nodurile i din stanga care nu au fost cuplate (deci nu se afla nici in multime) si sunt parcursi vecinii lor. Daca se gaseste un vecin j care nu se afla in suport inseamna ca muchia dintre nodurile i si j nu are niciun varf in suport, asa ca se adauga nodul j. Nodul j cu siguranta e cuplat (pentru ca altfel ar fi putut fi cuplat cu nodul i, deci cuplajul nu ar mai fi maxim) cu un nod k. Cum muchia dintre j si k are acum ambele varfuri selectate, k va fi scos si se va lansa aceeasi procedura si pentru el, care verifica daca prin scoaterea lui k a ramas vreo muchie ale carei noduri incidente nu sunt selectate.

Uite niste exemple in care minimul se obtine in cazul al doilea (si raspunsurile pe care mi le da sursa de 100):

Cod:

9
61 14
40 98
17 10
37 24
24 81
45 99
35 53
20 94
8 73
Output: 15129

Cod:

8
35 20
97 31
31 100
71 60
65 69
81 71
47 61
84 42
Output: 31133

Cod:

9
49 59
58 3
56 36
57 74
2 75
72 11
30 42
67 15
89 5
Output: 18177

Cod:

8
57 35
88 77
6 72
41 45
99 71
13 40
23 66
1 86
Output: 22939

Sper sa te ajute.

Nu ai nevoie de mai mult de n numere pentru fiecare coloana, deci vectorul tau poate sa aiba doar 20000 de elemente