Afişează mesaje
Pagini: 1 [2] 3 4 ... 6
26  infoarena - concursuri, probleme, evaluator, articole / FMI No Stress 4 / Răspuns: FMI No Stress 4 Feedback : Noiembrie 17, 2013, 22:43:11
Hm.. ok.. eu imi aminteam de 1.5 sec. Probabil imi amintesc gresit (poate era 1.5 sec la alta problema si confund, dar imi e lene sa verific acum). Oricum, intre timp mi-am optimizat solutia si intra in 1 sec, asa ca nu mai am intrebari Smile [ aveam prea multe operatii modulo in sursa - cand le-am inlocuit, timpul a scazut la o treime din ce aveam initial ]
27  infoarena - concursuri, probleme, evaluator, articole / FMI No Stress 4 / Răspuns: FMI No Stress 4 Feedback : Noiembrie 17, 2013, 22:07:59
Vad ca in arhiva limita de timp la problema "peluzanord" este de 1 sec. In timpul concursului era de 1.5 sec. De ce ati redus limita?
28  infoarena - concursuri, probleme, evaluator, articole / FMI No Stress 4 / Răspuns: FMI No Stress 4 Feedback : Noiembrie 15, 2013, 20:01:55
Problemele au fost dragute, dar limitarea la 1 singura submisie in asteptare (per ansamblu) mi s-a parut foarte enervanta. Poate avea sens o limitare de 1 submisie in asteptare per problema, dar pe intreg concursul (care a avut 11 probleme) mie mi s-a parut aiurea - mai ales ca evaluare submisiilor a fost destul de lenta in timpul concursului. Sper sa nu devina o regula generala si pentru alte concursuri organizate pe infoarena.
29  infoarena - concursuri, probleme, evaluator, articole / Concursuri / Invitatie la Codechef October 2013 Long Contest : Octombrie 03, 2013, 20:21:47
Pe 4 octombrie, la ora 12:30, va incepe pe Codechef concursul "lung" al lunii octombrie 2013 (la adresa http://www.codechef.com/OCT13). Concursul dureaza 10 zile si consta din 10 probleme de dificultate variata (de la foarte usoare la foarte grele, inclusiv una de tip Challenge).

La acest concurs am propus si eu una dintre cele 10 probleme, asa ca va invit sa participati, de data aceasta, din calitatea de "problem setter".

Va garantez ca o sa va placa concursul si problemele si fiecare va gasi probleme potrivite pentru nivelul sau actual de pregatire (iar daca veti reusi sa rezolvati toate cele 9 probleme in afara celei de tip Challenge puteti sa va felicitati!).
30  infoarena - concursuri, probleme, evaluator, articole / Concursuri / Răspuns: Codeforces Round #198 : August 31, 2013, 02:20:36
Au fost niste probleme dragute.
Problema E (Div1), insa, s-a mai dat mai demult la un concurs in Romania, in Ginfo: vezi http://www.ginfo.ro/revista/11_2/concurs2.pdf
E funny ca aveam sursa de 100p la problema aia din Ginfo, dar mi-am amintit abia dupa sfarsitul rundei unde am mai intalnit problema Smile
Anyway, momentan mai incerc sa o bulanesc  Smile  (cu un BFS prin spatiul starilor pt a gasi solutia pt 3 gramezi).
31  infoarena - concursuri, probleme, evaluator, articole / .com 2012 / Răspuns: Feedback .com 2012 : Martie 15, 2013, 13:57:25
Problemele de la toate cele 3 runde au fost dragute si interesante. Daca ar fi existat si niste mini-editoriale cu solutiile problemelor, totul ar fi fost chiar excelent!  Very Happy
32  infoarena - concursuri, probleme, evaluator, articole / .com 2012 / Răspuns: Luff : Martie 10, 2013, 23:20:02
Eu am facut Kruskal (considerand muchiile in sens descrescator al costurilor). Am folosit disjoint sets cu "union-by-size". Dupa fiecare Union tineam minte pt nodul "parinte" ca la timpul T (T = muchia ce face unirea) dimensiunea componentei sale a devenit egala cu valoarea V (V=nr de noduri din cele 2 componente tocmai unite). Pt nodul care devenea fiu al "parintelui" tineam minte ca trece in parinte la timpul T.

Practic, apoi, pt fiecare nod X, aveam un sir de perechi (T,V) sortate (dimensiunea V creste pe masura cu timpul creste -- sau, echivalent, costul muchiei de unire scade). Dupa acest sir de cresteri ale dimensiunii componentei lui X (in care X ramane radacina), X devine fiul al lui P(X) (la momentul TP(X) = muchia ce realizeaza unirea lui X cu P(X)).

Pt un query trebue sa pleci din nodul X dat si sa urci in sus pe parintii lui de multimi disjuncte pana dai de un nod Y a carui dimensiune a componentei (la ultimul moment cand mai era radacina a componentei sale) este >= K. Raspunsul e apoi maximul dintre muchiile parinte prin care s-a trecut si muchia la care nodul Y ajunge sa aiba dimensiune >= K.

Partea de preprocesare (Kruskal) e O(M*(log(M) + log(N))) si apoi avem O(log(N)) pe query.

Eu as fi interesat sa stiu cum e solutia cu cautare binara in paralel (sau alte solutii la problema asta). Mie problema asta mi-a placut cel mai mult din concursul de azi.
33  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Feedback Algoritmiada 2013, Runda 3 : Februarie 27, 2013, 00:17:36
OK... Smile
Din ce am citit aici (http://infoarena.ro/documentatie/rating), ideea nu pare rea (cel putin la prima vedere). E drept ca as putea sa ma uit si pe codul sursa al algoritmului ce calculeaza rating-ul (pentru ca ati pus link catre el) ca sa il inteleg mai bine, dar imi e lene sa fac asta Smile

In orice caz, bazat pe ce m-as astepta eu, pentru concurentul de pe locul 1 de la un concurs, in cel mai rau caz, rating-ul ar trebui sa ramana la fel (si in cel mai bun caz ar trebui sa creasca). De la locul 2 in jos anything may happen (de ex, daca concurentul cu cel mai mare rating din concurs iese pe locul 2 este acceptabil ca rating-ul lui sa scada, avand in vedere ca a obtinut un rezultat "sub asteptari").
34  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Feedback Algoritmiada 2013, Runda 3 : Februarie 26, 2013, 23:52:44
Mi se pare cam dubios cum functioneaza sistemul de rating. Am iesit pe locul 1 la grupa Open, dar rating-ul meu a scazut cu 3 puncte (de la 1163 la 1160) !

Ce puteam sa fac mai mult pentru ca rating-ul meu macar sa nu scada ? Smile  [ inteleg ca in calculul rating-ului nu conteaza punctajul propriu-zis, ci pozitia relativa in clasament ]
35  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Flux2 : Februarie 24, 2013, 14:01:02
Exista 2 cazuri cand raspunsul pe un test e 0:

1) daca fluxul mai poate fi crescut cu cel putin 1 unitate (in acest caz nu ai nevoie sa folosesti si costurile : o simpla parcurgere de la S catre D e suficienta, tinand cont ca e posibil ca pt a incrementa fluxul global sa fie nevoie sa-l decrementezi pe unele muchii ; anyway, e practic o iteratie dintr-un algoritm de flux maxim fara costuri)

2) daca fluxul nu mai poate fi crescut, dar exista un ciclu de cost negativ in reteaua data (adica costul ar putea fi redus) Pentru a determina daca exista ciclu de cost negativ, fiecare muchie x->y de cost C se transforma in maxim 2 muchii :
-- muchie x->y de cost C daca flux(x->y) < capacitate(x->y)
-- muchie y->x de cost -C  daca flux(x->y) > 0

Cazul 2 e cazul mai greu, deoarece are complexitatea mai mare: teoretic se poate ajunge la O(N^3) sau O(N*(N+M)) folosind algoritmul Bellman-Ford sau Bellmand-Ford-Moore (practic Bellmand-Ford dar cu coada). Eu am implementat destul de eficient algoritmul asta (desi, aparent, ultima versiune submitata nu era cea mai rapida si eram aproape sa iau TLE pe unul din teste).

Sunt curios daca exista o solutie de complexitate (teoretica) mai buna.
36  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Unicat : Februarie 24, 2013, 13:13:12
@Murtaza Alexandru: Si daca, de exemplu, ambele siruri contin 500.000 de 'a'-uri fiecare ?
In acest caz ai palindroame lungi de la fiecare centru posibil, iar suma lungimilor lor este O(N^2) (chiar daca in trie o sa ai doar O(N) noduri).
37  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Flux2 : Februarie 24, 2013, 09:08:12
Pentru fiecare retea data, se garanteaza ca cantitatea de apa transportata de la S la D este maxim posibila ?

Altfel spus, trebuie DOAR sa verificam ca se obtine costul minim (in conditiile in care cantitatea de apa este maxima) ?

In cazul in care raspunsul la intrebarea precedenta este NU: trebuie sa verificam atat:
1) ca se transporta o cantitate maxima de apa de la S la D
SI
2) costul de transport al apei este minim
?
38  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Algoritmiada 2013, Runda 2 : Ianuarie 28, 2013, 03:25:15
Mie mi se pare ca singura dificultate a problemei apare atunci cand aceeasi pozitie trebuie eliminata din ambele siruri (pt ca ai 2 variante de a ordona cele 2 operatii pt pozitia comuna). Altfel, daca din cele 2 siruri s-ar elimina seturi de pozitii distincte, ar fi un mod unic de a le interclasa pt a iesi in ordine crescatoare (si, astfel, raspunsul ar fi egal chiar cu numarul de subsiruri comune de lungime maxima, diferite doar ca seturi de pozitii, ceea ce se poate calcula usor extinzand un pic dinamica standard).

Mai exact, daca exista K pozitii eliminate din sirul 1 comune cu pozitiile eliminate din sirul 2 (pt a obtine dupa eliminare un subsir comun maxim), atunci pt acest subsir comun maxim trebuie adunata la rezultat valoarea 2^K  (pt ca pt fiecare pozitie comuna poti elimina ori mai intai pozitia din primul sir, ori pe cea din al doilea sir, dar in afara de asta, pozitiile pot fi interclasate intr-un singur fel).

Insa nu imi dau seama daca s-ar putea modifica cumva dinamica standard pt subsir comun de lungime maxima pt a "prinde" in solutii cazurile cand aceeasi pozitie i este eliminata din ambele siruri (ea "prinde" fara probleme cazurile cand aceeasi pozitie i este pastrata din ambele siruri, dar noua nu asta ne trebuie).
39  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Algoritmiada 2013, Runda 2 : Ianuarie 20, 2013, 22:42:11
Asa e, sunt doar O(log(N)) lungimi distincte, dar eu n-am vrut sa ma complic in vreun fel, asa ca am considerat toate intervalele independent.

In solutia mea nu am avut nevoie de inverse modulare (desi initial mi s-a parut ca as avea). Toti factorii importanti pe care ii aveam erau de forma Combinari(N,K) * (N - K)!  (pt diverse valori ale lui K). Daca explicitam combinarile, obtinem N! / (K! * (N-K)!) * (N-K)! = N!/K!. Asadar, toti termenii importanti erau de forma N!/K! = N * (N-1) * (N-2) * ... * (K+1) => am precalculat valorile astea (sunt O(N) astfel de valori, "sufixe" ale lui N!): in mod evident N!/K! = N!/(K+1)! * (K + 1).
40  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Algoritmiada 2013, Runda 2 : Ianuarie 20, 2013, 22:09:59
Am gresit analiza complexitatii solutiei mele la mergesort. De fapt, iese O(N). Numarul de intervale prin care trece mergesort este doar O(N) -- practic, o analiza de calcul simpla ne spune ca sunt N intervale de lungime 1, N/2 intervale de lungime 2, N/4 intervale de lungime 4, etc. Asadar, numarul de intervale este aprox. N+N/2+N/4+N/8+....+1=aprox. 2*N=O(N). Cum fiecare interval este procesat in timp O(1), reiese ca solutia are complexitate O(N).
41  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Algoritmiada 2013, Runda 2 : Ianuarie 20, 2013, 22:00:15
@Radu Szasz: Ti-a iesit si recurenta ok ? (adica sa intre in timp)  Bineinteles ca m-am gandit si eu sa folosesc alta baza decat 2 pt stramosi. Dar ideea e ca daca vrei sa calculezi Ancesor(x,i) = al 10^i-lea stramos al nodului x, trebuie sa il calculezi in 10 pasi, nu ? (pornesti de la Ancestor(x,i-1) si mergi in sus de inca 9 ori din Ancestor(*, i-1) in Ancestor(*, i-1), pana acoperi o "distanta" de 10^i). Anyway, mie mi s-a parut ca asta o sa fie prea lenta pt limita de memorie (daca ai facut ceva mai destept de atat, please share).



@Petru Trimbitas: Referitor la circulatie (ai mentionat ca solutia cu cuplaj ar fi prea lenta): Eu am facut cuplaj (x 2), insa folosind optimizarea Hopcroft-Karp, care creste "fluxul" pe mai multe drumuri simultan. Altfel zis, pt fiecare parcurgere BFS pe care o faci nu cresti fluxul doar pe un singur drum, ci pe un numar maximal de drumuri disjuncte. In felul asta, complexitate devine O(M*sqrt(N)) (M=nr muchii, N=nr noduri), adica pt problema asta O(N*sqrt(N)). E suficient sa faci 2 cuplaje, pt ca al 3-lea consta din muchiile care nu sunt incluse in primele 2 cuplaje.



@Dan Alexandru: Referitor la Mergesort: Eu am facut O(N*log(N)), asa cum ai zis si tu. Practic am "simulat" mergesort-ul si pt fiecare interval [left,right] la care se ajunge conform algoritmului am calculat (in timp O(1)) cate permutari ajung pana la intervalul respectiv (avand intervalul respectiv ori sortat ori nesortat) -- ideea e ca daca numarul de permutari pt care ajungi la un interval [left,right] este X (indiferent daca continui mai departe sau nu), rezultatul este suma acestor valori X pt fiecare astfel de interval [left,right].
42  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Algoritmiada 2013, Runda 2 : Ianuarie 20, 2013, 21:43:15
La Citylog care era solutia ?

Eu am avut de ales dintre doua solutii:

1) sa fac aproape O(log(N)) pe operatie (memorand toti stramosii cu 2^i nivele mai sus pt fiecare nod), insa din cauza limitei de memorie nu se puteau tine toti stramosii pana la log(N) (caz in care devenea O(logmax) + O(N / 2^logmax) pt operatiile de tipul 1 -- logmax a ajuns pana la 6 pt a se incadra in limita de memorie) -- am incercat si varianta in care am "comprimat" mai multi stramosi in limita de memorie (pana la logmax=11), caci fiecare stramos avea nevoie doar de maxim 17 biti, insa era mai lenta din cauza ca faceam O(17) pt a seta/gasi fiecare stramos
2) sa memorez stramosii cu O(sqrt(N)) nivele mai sus pt fiecare nod (sau de la un nivel multiplu de sqrt(N)), care ar fi condus la o complexitate de O(sqrt(N)) pe operatie, ceea ce mi s-a parut prea mult pt limita de timp a problemei

In cele din urma am ales solutia 1 (cu diverse variante), neavand timp sa testez si varianta 2 (si neavand nimic care sa sugereze ca varianta 2 ar fi fost mai rapida).

Daca exista o alta solutie mai buna decat cele 2 mentionate, as fi curios sa o aflu. Daca cumva se voia solutia cu radical (pe care nu am incercat-o), atunci parerea mea e ca a fost o problema aiurea (pt ca limita de timp nu sugera ca o solutie cu O(sqrt(N)) pe operatie ar fi suficient de rapida). Sincer, sper ca exista o solutie mai desteapta la care nu m-am gandit eu...
43  infoarena - concursuri, probleme, evaluator, articole / .com 2012 / Răspuns: Raco : Ianuarie 12, 2013, 10:40:42
1) "subsir" inseamna ca elementele trebuie sa fie consecutive ca pozitie in sir ?


2) Daca NU, atunci pentru exemplul din enunt, cele 3 subsiruri sunt (ca valori):
2 1
3
2 3 1
?


3) Doua subsiruri se considera diferite daca contin aceleasi numere (ca valoare), in aceeasi ordine, dar cel putin unul din numere provine de pe pozitii diferite ale sirului initial ?

4) Un subsir este determinat de pozitiile din sirul initial pe care se afla elementele sale (considerand pozitiile in ordine crescatoare) ?
44  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Feedback Runda 1 : Decembrie 20, 2012, 00:49:47
Mie mi-au placut mult problemele de la runda asta de Algoritmiada (ma refer acum doar la cele de la Open, caci doar pe ele le-am citit, dar cum ele au facut parte si din setul de probleme de la celelalte clase, reprezinta o vedere destul de buna asupra intregii runde).

Partea de organizare a avut, intr-adevar, cateva probleme (probabil mai multe decat la alte runde de Algoritmiada). Printre cele de care m-am lovit eu sunt urmatoarele:

- la "interzis" luam TLE pe testul de feedback 9 (desi aveam complexitate O(N*L), care banuiesc ca e si complexitatea solutiei oficiale...) : m-am gandit ca e din cauza ca o exista o solutie de complexitate mai buna de atat si am pierdut ceva timp incercand sa o gasesc (fara succes) ; pana la sf. concursului acceptasem ca o sa iau TLE pe testele 9 si 10, dar se pare ca aceste teste aveau N-ul mai mare decat in enunt si au fost modificate (cand N-ul a fost redus la <= 15.000 sursa mea a intrat in timp) ... inca nu stiu daca ar fi trebuit sa intre in timp si pe testele initiale (cu N <= 20.000) ; nu stiu daca schimbarea testelor si reevaluarea au avut loc in timpul concursului, caci nu am mai verificat feedback-ul la sursa mea dupa ce am decis sa trec la urmatoarea problema

- la "critice2" am terminat sursa cu 30 min inainte de finalul concursului, am trimis-o si luam WA pe cele 2 teste de feedback... am inceput sa-mi generez teste (de mana, ca sa le pot verifica, apoi mai mari ca sa vad ca nu da vreun rezultat aiurea) in speranta ca o sa-mi gasesc bug-ul... nu am gasit.. am mai facut mici modificari si am tot retrimis sursa, insa am luat mereu WA.. ultimele 30 min le-am petrecut incercand sa inteleg ce e in neregula cu sursa mea... pana la urma am renuntat, iar la sf. concursului credeam ca o sa iau 0 pe sursa... se pare, insa, ca eval-ul nu era chiar OK la momentul respectiv (nu verifica cu precizia mentionata in enunt, ci verifica ca output-ul sa fie identic cu cel al comisiei... eu am incercat sa afisez ori cu 4 zecimale, dupa cum se preciza in enunt, ori cu 7... output-ul comisiei banuiesc ca era generat cu 6 zecimale... daca afisam si eu tot cu 6, probabil scapam de 30 min de stress in incercarea de a debug-a o sursa corecta Smile )

- la "taie" limita initiala de timp era, parca, de 0.2 secunde; eu am implementat o solutie in O(N^2 * log(N)) despre care eram sigur ca nu va intra in timp (nu doar din cauza complexitatii, dar si pt ca apelam atan2 de O(N^2) ori, ceea ce e destul de time-consuming) ; ma gandeam ca trebuie sa existe o solutie in O(N^2) pe care urma sa incerc s-o gasesc daca mai aveam timp la final (ceea ce n-am mai avut) ; pana la urma am avut noroc ca s-a marit limita de timp si solutia mea s-a incadrat in aceasta limita de timp (desi as fi foarte curios sa stiu o solutie de complexitate mai buna decat O(N^2 * log(N)).. sau macar una care nu foloseste unghiuri atat de mult precum solutia mea)


Insa nu pot sa ma plang de un concurs organizat de voluntari (de ex., la TopCoder ar avea sens sa ma plang daca ceva e in neregula cu problemele, caci acolo oamenii sunt platiti pt pregatirea si testarea problemelor... la fel pe Codechef... pe Codeforces nu stiu cum sta treaba.. cred ca si acolo e activitate voluntara, insa nu stiu sigur ; si astea sunt celelalte 3 site-uri la care particip la concursuri in mod regulat). Ce-i drept, insa, astfel de probleme de organizare ar putea descuraja unii concurenti de la participarea la Algoritmiada.

Relativ la dificultatea problemelor, cel putin la grupa Open, nu as putea sa zic ca as putea eticheta vreuna din probleme ca fiind "simpla" (asta nu inseamna ca, de exemplu, solutiile la "mvc" si "interzis" nu mi s-au parut evidente, dar stiu ca aceste probleme ar fi etichetate cel putin "medii" daca ar fi considerate pentru a fi propuse la olimpiada nationala de informatica - clasele 11-12).

Desi mie imi plac problemele challenging, cred ca sunt partial de acord cu parerea exprimata de Vman intr-un post anterior. Cred ca daca unele probleme ar fi in mod evident mai simple (ori efectiv mai usoare, ori in mod direct mai clasice -- nu ca in sensul de la "mvc" ca se pot reduce la ceva mai standard, ci sa fie "pe fata" ceva clasic/standard), mai multi concurenti s-ar simti incurajati sa participe. In plus, la astfel de probleme mai simple si munca comisiei ar fi mai usoara (existand sanse mai mici sa greseasca la limite, teste, etc.).

Anyway, este doar la latitudinea echipei infoarena sa decida formatul si dificultatea problemelor propuse la Algoritmiada.


In incheiere, arunc si eu o parere personala (pe care am mentionat-o si acum mai multi ani conducerii infoarena de atunci). Cred ca concursurile de pe infoarena ar beneficia de o participare mult mai mare daca enunturile ar fi propuse in lb. engleza (asta ar implica si faptul ca o parte a site-ului sa fie in lb. engleza). Cred ca un exemplu foarte bun este Codeforces, care are continut in rusa si engleza si are foarte multi utilizatori internationali. Bineinteles, nu stiu cat de fezabila ar fi o astfel de idee (ca volum de munca) sau cat de dezirabila (acum mai multi ani mi s-a spus ca infoarena e gandita pt elevii din Romania, astfel ca o sectiune in lb. engleza nu si-ar avea rostul avand in vedere "publicul tinta" -- am parafrazat eu, caci nu mai tin minte cuvintele exacte).
45  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Combinatorics shortlist : Decembrie 19, 2012, 18:57:22
A bit more explanations for problem 17:

Let's consider that our sequence consists of N positions numbered from 1 to N. Each position can be colored either white (0) or black (1). Thus, there are 2^N different sequences. However, some of them are equivalent by rotation. We are only interested in counting the number of equivalence classes.

According to Polya's lemma (or Burnside's lemma or the Cauchy-Frobenius lemma), we must first find out the group of permutations which decide if two sequences are equivalent (sequence A is equivalent to sequence B according to a permutation P if A(1)=B(P(1)), A(2)=B(P(2)), ..., and A(N)=B(P(N))).

Obviously, the permutation 2 3 4 ... N 1 is the main such permutation (which means that two sequences A and B are equivalent if: A(1)=B(2), A(2)=B(3), ..., A(N-1)=B(N) and A(N)=B(1) -- in other words if B is equal to A rotated by 1 position).

However, this is not the only such permutation: 3 4 ... N 1 2 is another one and, in general, every permutation corresponding to a rotation by a number of positions may decide the equivalence of 2 sequences. Because it is a group of permutation, the identity permutation 1 2 ... N must also be used (which simply says that any sequence is equivalent to itself).

Thus, there are N permutations which define the equivalence classes (one for each rotation from 1 to N-1 plus the identity permutation -- note that the identity permutation can be considered as an N-position rotation).

According to the lemma, the answer to our problem is the average number of fixed points of all these permutations.

Let's consider one of the permutations and let's assume that it has C cycles. Then, a fixed point for the permutation is a sequence A such that A=P(A). This implies that all the positions of A which are part of the same cycle must have the same value. Since we have two distinct possible values (0 and 1) for each position, a permutation with C cycles has 2^C fixed points.

Let's see now how many cycles a k-position rotation permutation has. Such a permutation implies that positions 1, k+1, 2k+1, ... are part of the same cycle, 2, k+2, 2k+2, ... are part of the same cycle, and so on. The number of such cycles is equal to gcd(k, N)  (note that this also works for the identity permutation which is an N-position rotation permutation).

Thus, the total number of fixed points is FP=2^gcd(1,N) + 2^gcd(2,N) + ... + 2^gcd(N,N). Since there are N permutations, the average number of fixed points is FP/N (I am not really sure  why FP is divisble by N, but it is Smile ).
46  infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2013 / Răspuns: Interzis : Decembrie 16, 2012, 10:00:34
In cazul L=0 avem un subsir nul. Este acesta subsecventa a oricarui sir format din "a" si "b" ?
(s-a mai pus intrebarea asta ceva mai devreme din cate vad, dar nu s-a raspuns inca)
47  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Combinatorics shortlist : Decembrie 14, 2012, 23:33:25
17) I solved that problem many years ago Smile  Since I don't have my source code nearby, I will give it a shot at rediscovering the solution. Here's my wild guess Smile

(2^gcd(1,N) + 2^gcd(2,N) + ... + 2^gcd(N,N)) / N

The main tool for solving the problem is this: http://mathworld.wolfram.com/Cauchy-FrobeniusLemma.html  (also known as http://en.wikipedia.org/wiki/Burnside's_lemma)
48  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Combinatorics shortlist : Decembrie 14, 2012, 23:12:52
15) Since the exponent k for which a permutation becomes the identitiy permutation is the lowest common multiple of its cycle lengths, we could use dynamic programming to solve this:
kmax[i,j] = the maximum k for a permutation with j elements and using only the first i prime numbers

the idea is that the cycle lengths are always prime numbers or powers of prime numbers (or 1 - yes, it may make sense to have cycles of length 1 in the solution : this only means that the answer is max{kmax[*,j] 1 <= j <= N})

kmax[0,0] = 1
kmax[i,j] = max{ prime(i)^q * kmax[i-1, j - prime(i)^q | 1 <= q <= qmax such that prime(i)^q <= j }

Note that kmax[i,j] is a large number. I don't currently know how to solve the problem without using large numbers (i.e. without using large numbers during the algorithm ; the answer itself will always be a large number, unless you simply ask for a permutation which maximizes k, like in the infoarena problem)

This problem was also used in:
* "Bursele Agora" (Agora scholarship) contest -- the 1st edition (1999-2000) if I recall well, and
* Olimpiada online (2001) -- it was a problem with dancing butterflies or something
49  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Combinatorics shortlist : Decembrie 12, 2012, 22:26:43
At problem 6) (counting the number of ways of covering a 3xn rectangle with dominoes - let's assume 3 = number of rows and n = number of columns) I personally prefer using dynamic programming with 2^3 states (i.e. compute nways[i, conf] = the number of ways of covering the first i columns such that: the first i-1 columns are fully covered and column i is in state conf -- where a 1-bit denotes that the cell on that row is covered and a 0-bit denotes that the cell on that row is empty ; 0 <= conf <= 2^3 - 1). The answer would either be in nways[n, 7] or in nways[n+1, 0].

A nice thing is that this problem can be solved even for large values of n (e.g. n <= 10^18) by raising an appropriate matrix to an appropriate power.
50  Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Combinatorics shortlist : Decembrie 12, 2012, 17:08:47
Hm... Since I forgot that the post was in English, I will restate my comment in English

1) 9! / (3! * 3! * 3!) = 1680
or
Comb(6,3) * Comb(9,3) = (also) 1680
[ Comb(n,k) = n choose k ]

2) Fibonacci(n)  (considering Fibonacci(0) = Fibonacci(1) = 1)
Pagini: 1 [2] 3 4 ... 6
Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines