infoarena

Aici puteţi discuta despre problema Permutari (http://infoarena.ro/problema/perm).

Am demonstrat ca rezultatul este de fapt numarul lui Stirling

de speta intai |s(N,K)|, unde N si K sunt numerele din problema.

Am determinat s(N,K) cu formula de recurenta:
s(N,K) = (N-1)s(N-1,K) + s(N-1, K-1).
   Desi atat formula cat si calcularea ei recursiva mi se par

corecte ( sunt demonstrate in "Probleme de combinatorica si teoria

grafurilor" de Ioan Tomescu, Editura Didactica si Pedagogica,

1981, pag. 51) sursa mea este evaluata la 10 puncte.
  De ce?

tu ai bagat operatii pe numere mari? :D

Ce primesti Wrong Answer sau Time limit exceeded?

Ce numar stirling ai folosit? Primul sau al doilea?
Poate exista o formula nerecurenta, ca la combinari, care se poate calcula mai usor. :roll:

Apropo, stie cineva de unde imi pot cumpara I. Tomescu "Probleme de combinatorica si teoria grafurilor?". Exista vreo editie mai noua? Din cate stiu eu cartea e antica.

Tu esti sigur ca ai dem bine? Din cate am facut eu pe foaie nu e bine. M-am uitat pe http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html sa vad exact ce sunt numerele lui Sterling.
De ex pt 3 rezultatele ar fi 2, 3 si 1 (nu 1,3 si 1), iar pt 4 sunt 6,11,6 si 1, nu(1,7,6,1). Asta dc am inteles bine problema.

Am sa raspund la toate mesajele:
1. am implementat operatii pe numere mari de pana la 500 de cifre

(iar din calculele mele cel mai mare numar se obtine pentru 200 si 2 sau 200 si 3 si nu are decat 370 si ceva de cifre, un pic mai mult decat 200!).
2. folosesc primul numar al lui stirling, primesc "Wrong answer"

iar tmpul de executie este sub 0.05 sec (pt N=200).
3. pt Bogdan2412: ce ai gasit tu este nr lui Stirling de speta a

doua, care este cu totul altceva. Si am inteles bine problema. Pt n = 5, obtin 24, 50, 35 (ca in exemplul din problema), 10 si 1. Nu-i asa?

Acesta e textul problemei din "Probleme de combinatorica si teoria
grafurilor":
12.15 Demonstrati ca numarul permutarilor p ale multimii {1,2,...,n} care au proprietatea ca exista exact k elemente j pentru care p(j)>p(i) pentru orice i<j este egal cu |s(n,k)|.


|s(n,k)| numarul lui Stirling de speta intai si este egal cu coeficientul lui x^k din dezvoltarea: x(x+1)(x+2)...(x+n-1).


Daca doreste cineva am sa pun pe forum si demonstratia lui Ioan Tomescu.

Poate ma ajuta cineva care a luat maxim la problema asta.

Am rulat cateva teste:
1. N=13; K=8; Am obtinut sol = 1095154;
2. N=17; K=4; Am obtinut sol = 87077748875904;
2. N=70; K=45; Am obtinut
 sol = 26269688897329413126924403900781315211553781164470;

Va da si voua la fel?

Pentru primul raspunsul este 6926634
Pentru al doilea este 87077748875904 (aici iti da bine)
Iar pentru al treilea imi da 328693139125599643512870879273574455866682562802025734100

Cel mai probabil ai gresit la implementarea operatiilor cu numere mari,
Daca foloseai int64 obtineai 40p.
Rezultatul pentru n=13 si k=8 este 6926634.

@stifmeister: scuze... oricum, probabil ai gresit ceva la calcularea numerelor mari.

Eu am facut problema, dar la 9/10 teste am primit "RUN ERROR - Invalid memory reference". Am facut o clasa cu numere mari, reprezentarea unui numar mare am facut-o pe un vector int de 1001. Am folosit doi vectori de tip numar mare de dim 201 pt calcularea solutiei. Am verificat problema acasa pe 200 2 si 200 100 si 200 199 si nu am primit nici un mesaj Segmentation Fault... Ma poate ajuta cineva?

Va multumesc, am rezolvat problema si am luat 100p. Formula era buna dar am gresit la

implementarea adunarii numerelor. Era un caz particular si de-aia nu m-am prins repede unde

am gresit.

am facut si eu problema bazat pe aceeasi formula de recurenta , am facut si pe numere mari si pe mici , si tot iau 40 puncte , tot imi iese din timp , cand intra in recurenta cu k mare trebuie sa astept mult
Voi ce conditii de iesire aiti folosit??
eu pt n=k am gasit sa stir=1 si pt k=1 am gasit k=1 stir=(n-1)!
da in ritmu asta progrmu mere greu poate am ratat eu o chesti asa ca pls help

nu mai conteaza am gasit solutia , eu am facut o implementare simpla si directa si aceeasi valoare era calculata de f multe ori , am modificat algoritmul astfel incat sa se retina valorile obtinute si sa se refeoloseasca cand e nevoie am luat 100 p

[edited by svalentin] posts merged; nu mai postati dublu! daca aveti ceva de adaugat folositi "edit"!!

Folosesc numere mari, dar iau 60, pe 4 teste iau tle.. Am optimizat cat am putut, dar nu-mi dau seama ce s-ar mai putea face.. Aceasta este implementarea pe numere mari....


old e linia anterioara, curent e linia curenta...

Sugestii?

Poti incerca sa folosesti baza 10000 sau 10^6 pentru numere.

ok, am sa incerc, multumesc!


Later edit:
Ok, am gasit ce nu faceam bine... eu la fiecare pas puneam 'curent' pe 0... ceea ce era.... oricum, am sa incerc si varianta cu baza, pare interesant...

 Nu stiu daca am inteles prea bine problema .  Nu  posteaza cineva sirurile de lungime 3 cu 2 maxime ?

231
132
213

Poate sa-mi scrie cineva daca a facut 100 ... cat e timpul la testul 5 si 8?
Eu la testul 5 totdeauna am TLE  ](*,) ... si la testul 8 da 300 ms :P hlp pls (sry bad roman)

Limita de timp pe toate testele este de 0.3 s [sau 300 ms]. Testele nu sunt neaparat ordonate in ordinea dificultatii. Oricum, mai optimizeaza. :)

Stiu ca limita de timp e 0.3 ms dar vreau sa stiu timpul la testul 5 cine a facut 100, pentur ca daca e foarte mica (20-80 ms) atuci nu n sau k e mare ci am o problema in program cu numerele mici. #-o..la testul 8 am primit eu 300 ms exact cat trebuie de aceea am 90 puncte...Si poti sa-mi dai niste idee de optimizare?

Ti-as zice ce timpi am pe testul respectiv, dar sursa am trimis-o pe infoarena 1. Ca optimizari ai putea sa calculezi numerele mari intr-o baza mai mare (gen 10000) si sa nu calculezi toate starile din dinamica, ci doar alea de care ai nevoie pentru a obtine rezultatul.

Pe testul 5 sursa mea ruleaza in 288ms, iar pe testul 8 ruleaza in 252ms :)

si mie mi-a intrat cam cu aceeasi timpi aproximativ folosind baza 10.

Da nu calculez nici unu in plus (asa a fost) dar am incercat baza 10^4 si am resuit!!! :yahoo:
Acum timpul la testul 5 e 72 ms  :D ... Thx  :ok:

Nu pricep. Aplic formula, calculez recursiv si folosesc int64. Normal daca da pe afara cred ar trebui sa dea un fel de eroare sau sa devina valorile negative dar imi da TLE. Folosind operatii pe numere mari nu ar dura si mai mult ?

Recursivitatea e mai inceata.

Am facut in baza 10^4 si am luat 100p.  :yahoo: Super problema, chiar am avut de invatat niste cazuri particulare in la operatiile cu numere mari. Eu programator inrait pe borland a trebuit sa fac multe schimbari pe agoritm sa functioneze de 100 in fpc. Oricum, multumesc mult pentru sfaturi!

 ok .. ceva nu imi iese mie .. bine si nu vad unde gresesc ... :|
     Eu gandesc in felul urmator  :
       folosesc o matrice sol[ i ][ j ] care reprezinta numarul de permutari cu "i" elemente care au "j" maxime . O permutare cu "n" elemente si "k" maxime se poate forma din :
                    - o permutare cu "n-1" elemente si "k-1" maxime prin adaugarea elementului "n" la sfarsitul permutarii .
                    - o permutare cu "n-1" elemente cu "k" maxime prin adaugarea elementului "n" inaintea ultimului maxim.
                    - o permutare cu "n-1" elemente cu "k+1" maxime prin adaugarea elementului "n" inaintea ultimelor doua maxime .
             ....................................
             ....................................
                   - o permutare cu "n-1" elemente cu "n-1" maxime prin adaugarea elementului "n" dupa primele "k" elemente din permutare .

       De aici rezulta ca numarul de permutari cu N elemente si K maxime se calculeaza in felul urmator :

sol[ n ][ k ] = sol[ n-1 ][ k-1 ] + sol[ n-1 ][ k ] + sol[ n-1 ][ k+1 ] + ... +sol[ n-1 ][ n-1] 
initial sol[ 1 ][ 1 ] = 1

Calculand in felul acesta nu se ajunge la rezultatul corect .

1
1 1
2 2 1
......
in loc de al doilea 2 corect era "3" .. ( se poate vedea ca e si exemplu dat ...) nu vad unde gresesc .. evident .. nu va merge pentru teste mari .. insa .. nu vad unde gresesc .. :| ( ma refer la ideea de rezolvare )

   Nu poate nimeni sa imi dea nici un sfat .. sau toti cei care pot sunt la baraj pentru lot ??   :-k 
 :winner1:
 :roll:

Ai gresit recurenta.
Defapt problema cere sa determini numarul lui Stirling de speta intai.
s(N,K) = (N-1)s(N-1,K) + s(N-1, K-1).

 Am vazut ca au afisat cineva la inceputul topicului striling de speta 1 ... insa .. eu vream sa stiu ce e gresit in gandirea mea ....

Tu pentru k+p maxime te gandesti ca poti introduce elementul N inainte de ultimele p-1 maxime. Problema este ca s-ar putea sa ai mai multe locuri in care sa-l poti introduce.

Uite un exemplu:

3 2 1 4 5

Vrei sa obtii doua maxime cand bagi pe 6 si poti obtine:

3 6 2 1 4 5
3 2 6 1 4 5
3 2 1 6 4 5

In recurenta ta, aduni o singura data.

  Ah da .. corect .. nu m-am gandit la asta :) merci ..

Am si eu o problema ... fac problema prin numerele lui stirling, afisez cu numere marisi totusi imi da WA la 4 teste, am incercat cu 10^4 afisarea pana la 10^9... tot 4 teste gresite imi da, dar culmea culmilor este k testele gresite nu coincid knd schimb baza de afisare  ](*,)... poate cineva sa-mi spuna care-i faza  :-s

Ai grija cand folosesti o baza mai mare ca 10 sa afisezi si zerourile. De exemplu, daca folosesti baza 10^4, numarul 73 trebuie afisat ca 0073.

Ms mult pentru observatie... am luat si eu suta  :banana:

Cat va da pentru :


Cred ca asta ii cel mai mare rezultat care se poate obtine.

23159060312564359871950929055455674021435236167923959343115750040823047581979908380727537796461185778013737134426559431288744237478343902437539133012028435084567718670531340662889488184573823549876303454548719715122034588710323516710029845203752585692844797698070034630498657231556170312181971812010087147350420585907013230054604800000000000000000000000000000000000000000000

Cum as mai putea sa-mi optimizez solutia ca sa iasa in timp?
http://infoarena.ro/job_detail/164223

foloseste baza 10000 pentru numerele mari. ai grija la afisare.

el ia 9 tleuri deci probabil ca face back. Nu cred ca il ajuta sa mareasca baza la numere. Incearca sa te gandesti la alta abordare.

E greu sa dai indicatii daca nu stii ce e in sursa aia... Alex, descrie putin ce faci acolo.
Dupa numarul de teste care depasesc timpul, probabil Devilkind are dreptate : incearca altceva.

Generez toate permutarile si dupa aceea verific cate maxime are....daka are k maxime afisez solutia...

Cauta o solutie mai eficienta. :) Iar daca nu te prinzi, citeste cu atentie posturile anterioare din topicul asta.

am si eu o problema
am facut functia de stirling pe nr mici
folosind formula
s(n,k)=(n-1)*s(n-1,k)+s(n-1,k-1)
si la testul n=5 si k=3 imi da 34 si nu 35
ma poate ajuta cineva va rog

Va rog scrieti demonstratia,ca eu nu am inteles de ce solutia acestei probleme e formula asta:s(N,K) = (N-1)s(N-1,K) + s(N-1, K-1).

vreau si eu sa va intreb ceva... am facut sirul stirling... dar din pacate iau decat un test din toate... testul 6 mai precis.... puteti sa imi dati testul 1 sau 2 sa vad care e problema?


 Editat de moderator: Foloseste tag-ul code cand postezi cod!

sigur sunt testele bune? sirul stirling arata pentru 5 3 varianta 25...

 Editat de moderator: Nu posta in continuu, ci editeaza mesajele precedente daca sunt pe aceeasi tema.

Testele sunt bune. Nu ti se pare ciudat ca au luat si altii 100, daca testele sunt gresite?

Mai sunt pe acest topic cateva teste, le-ai incercat?

Ghitza, tu ai inteles problema... sau ai citit pe forum ca se face cu Stirling si ai cautat pe google relatia de recurenta?

am citit pe forum;)) si nu imi da ceva bine... dar nu inteleg, cum s-ar putea face?

Pai tu ai implementat numerele lui Stirling gresite ;). Cauta pe wikipedia si vei vedea ca exista atat numerele lui Stirling de speta I, cat si de speta a II-a (au semnificatii, recurente, respectiv valori diferite)

 :eyebrow: Nu stiu cum ati reusit sa faceti de 200 si ceva de ms...mie, la testu 5 :evil: imi ia 53 ms si la 10 imi ia cel mai mult :winner1:->84 ms \:D/

la fel cum a mai spus inanitea mea si eddy, poate cineva sa puna si demonstratia ca solutia este numarul stirling de speta I, cred ca nu este  prea evident ca asa este chiar daca merge...

Mai bine îți găsești singur dinamica, decât să cauți de ce sunt numerele lui Stirling sau ale nu știu cui. Așa ai șanse și să înveți ceva din ea.

Ok. sunt incepator dar totusi... cum scriu eu sirul de numere care rezulta din 200 2 de exemplu ?!
Ca nu vad niciun tip de variabila care sa salveze siruri asa de lungi.
Si mai sunt si pascal  :oops:

Trebuie sa reprezinti numerele ca siruri (vectori) de cifre si trebuie sa implementezi "de mana" operatiile de care ai nevoie (aduname, inmultire, etc.). Poti sa consulti sectiunea "Numere mari" din acest articol (http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai) ca sa-ti faci o idee (desi explicatiile sunt in C, poate reusesti sa transpui codul in Pascal).

Salut!
Vreau si eu niste ajutor pentru ca nu inteleg cum sa ajung la relatia de la numere stirling.
Uitati cum gandesc eu si va rog frumos sa-mi dati indicatii unde gresesc(daca gresesc) si ce are trebui sa fac sa ajung la recurecta respectiva.
a[n][k] ->numarul de permutari  de n elemente din multimea {1,2,3...n} cu k maxime

este suma din:
       -a[n-1][k-1]*(n-pozitia ultimului maxim) pentru ca putem adauga pe n dupa ultimul maxim si vom avea k maxime <=> daca avem {maxim , e1, e2, e3} avem 4 pozitii(pozitia lui e3 este n-1 iar a lui maxim n-4) in care putem pune pe n (in locul celor 3 virgule sau dupa e3)
       -a[n-1][k]*(pozitia ultimului maxim-pozitia penultimului maxim) pentru n va "bloca" orice maxim care se afla dupa el iar numarul de maxime va ramane k <=>daca avem{maxim1, e1, e2, e3, maxim2} atunci putem pune pe n in locul celor 4 virgule (poz[maxim1]=poz[maxim2-4])
       
       - a[n-1][k+1]*(pozitia[penultim]-pozitie[antepenultim] ) pentru n trebuie sa blocheze 2 maxime deci trebuie pus intre antepenultimul si penultimul maxim
        ...
        -a[ i ][j]*(poz[al k-lea maxim]- poz[al k-1-lea maxim]
         ...
       -a[n-1][n-1]*(poz[al k-lea maxim]-poz[al k-1-lea maixim] =1 putem pune intr-un singur loc al n-lea element

Va rog mult sa ma ajutati.

Rezolvarea ta nu e buna pentru ca nu stii pozitiile maximelor.

O problema asemanatoare cu aceasta este problema doipe (http://infoarena.ro/problema/doipe), care are solutia explicata intr-un articol (http://infoarena.ro/winter-challenge-1/solutii). Poti sa cauti acolo indicii despre abordarea acestui tip de probleme.

Imi puteti explica si mie recurenta de la numarul lui Stirling de speta I ? Chiar nu am reusit sa o pricep.

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).

Daca problema asta se face cu numere mari, de ce nu sunt numere mari la indicii?

In primul rand nu cred ca exista un tag cu numere mari, in al doiela rand ar trebuie facut unul ....  \:D/

http://infoarena.ro/cauta-probleme?tag_id%5B%5D=104 (http://infoarena.ro/cauta-probleme?tag_id%5B%5D=104)

_____________

Ce e gdb.exe? Pt ca imi crapa in timpul debug-ului, apoi crapa si MinGW?
gdb.exe nu crapa daca rulez normal programul sau daca dau debug dar fara sa pun la watch nimic.

___mai tarziu___
Am mai facut niste teste si se pare ca gdb crapa daca declari tablourile prea mari, chiar daca ruland normal sau cu debug dar fara sa pui la watch tabloul merge.

Merci, chiar nu am stiut de el .

infoarena.ro/portal (http://infoarena.ro/portal)

Am creat eu un mic portal de taguri (neoficial).

GDB e ... debug-erul ... http://en.wikipedia.org/wiki/GNU_Debugger

Multumesc.

Ce parametrii ar trebui sa pun la o functie care sa imi inmulteasca doua numere mari (vectori) ?

(daca vectorul e de int)

in  mingw imi da bine pt toate testele, dar evaluatorul imi spune "killed by signal 11" si nu inteleg dc... ](*,)

S-ar putea sa accesezi o zona de memorie nedeclarata. Asta e cauza cea mai frecventa.

la primul exemplu sunt permutari:
123
132
213
231
312
321
Care sunt cele 3 permutari cu 2 maxime?

132
213
231

AAA deci si primul termen satisface conditia... Ok mersi :)

Eu am facut cu long long si am luat 10 puncte.

Ma gandeam sa refac dupa pe numere mari DAR pe exemplul al doilea imi da 34 in loc de 35.

Am folosit formula de recursivitate:

S(n,k) = (n-1)*S(n-1,k) + S(n-1, k-1)

Matricea arata cam asa:

1
1 1
1 3 1
1 10 6 1
1 41 34 10 1

E corect?

PS deasupra diagonalei principale din matrice sunt zerouri.

Mie imi da asa, cred ca ai gresit la implementare undeva :)

Cu ce s-o mai optimizez și eu? Fac dinamică, calculez numai ce îmi trebuie, numere mari, baza 10000, altceva?

Ar trebui sa mearga sa folosesti o baza mai mare, nu?

Mersi Paul. Până la urmă problema era la afișare.

Pentru N=200, K=5 intoarce cel mai mare numar de permutari (un numar de 375 de cifre)


Pentru N=300, K=6 intoarce cel mai mare numar de permutari (un numar de 614 de cifre)


 :yahoo:

Eu nu inteleg problema asta.
Care ar fi cele 3 permutari care au 2 maxime?

Permutarile sunt: (2,3,1), (1,3,2), (2,1,3); iar in legatura cu problema cauta numerele lui Stirling.

O intrebare am .Cand zice k maxime la ce se refera ca nu prea am inteles din cerinta.

Cum se rezolva problema asta daca in loc de permutari avem niste siruri oarecare, unde se pot repeta unele numere ??? :?

Mai sunt 2 zile din concursul de pe codechef :P

Ei bine acum ca s-a terminat concursul de pe codechef imi ziceti si mie cum se rezolva  :)

Am senzatia ca exemplul 2 e gresit. Daca mai crede cineva asta sa imi spuna, daca nu sa imi posteze cineve cele 35 de siruri sau sa imi explice regula. Mersi!

vladm98
Nope, nu e gresit
1 2 5 3 4
1 2 5 4 3
1 3 2 5 4
1 3 5 2 4
1 3 5 4 2
1 4 2 3 5
1 4 2 5 3
1 4 3 2 5
1 4 3 5 2
1 4 5 2 3
1 4 5 3 2
2 1 3 5 4
2 1 4 3 5
2 1 4 5 3
2 3 1 5 4
2 3 5 1 4
2 3 5 4 1
2 4 1 3 5
2 4 1 5 3
2 4 3 1 5
2 4 3 5 1
2 4 5 1 3
2 4 5 3 1
3 1 2 4 5
3 1 4 2 5
3 1 4 5 2
3 2 1 4 5
3 2 4 1 5
3 2 4 5 1
3 4 1 2 5
3 4 1 5 2
3 4 2 1 5
3 4 2 5 1
3 4 5 1 2
3 4 5 2 1

am folosit backtracking dar imi da doar 10 puncte

ma raportez singur :banana: