Very neat! I would have never thought of self-edges.

(3) seems non-trivial (unless I miss something). I will try to sketch my idea of the proof:

1. Assume there is at least one 0.
Let X be the number of 0s and (N-X) the number of non 0s.
There are X self-edges (positions with 0 marbles).
Any Y consecutive non 0s give Y incoming edges  - the previous 0 position could have had 1..Y marbles. So in total N-X incoming non-self edges.
That gives a total of "at least" N incoming edges. If we consider (1) we get "at least" == "exactly".

2. There is no 0.
Let MIN=the minimum number of marbles in any cup.
Subtract MIN marbles from each cup (that's N*MIN marbles in total), apply 1. and add N*MIN marbles to each starting position for a move.

Cosmin, did you have a similar idea in mind?

I tried looking for an invariant but then I noticed that from any position I can transition to a configuration where all the marbles are in the first bin (so I cannot easily eliminate any combination). If I could only find a way to go backwards from any position to the same "everything in one bin" configuration that would be great...

Mihai, I believe that having no limit on M makes the problem more interesting (and harder). Do you already have a solution for M <= N?

Later edit: for M <= N it is possible to create one big stack of marbles in one bin, distribute them and then take them one by one (from "right" to "left" modulo N) to form the second pattern.

Wow, ce a trecut timpul! 10 ani de la primul concurs http://www.infoarena.ro/preoni-2004/runda-1, mi-au trebuit multe luni dupa concurs ca sa aflu cum se rezolva toate problemele.

La multi ani!

Nu ai putea folosit lower_bound (http://www.cplusplus.com/reference/stl/multiset/lower_bound/) in loc de cautare binara?

Mie mi se pare foarte valoroasa cartea asta.
M-am apucat sa o rasfoiesc in anul 4 de facultate, vrand sa imi aduc aminte anumite chestii si am fost uimit sa descopar o gramada de lucruri noi, la care nu m-as fi putut gandi singur( cu alte cuvinte nu as fi stiut ce sa 'caut pe net').
Cred ca este o resursa foarte buna pentru cei care se pregatesc singuri si au nevoie de o oarecare indrumare.

Colierul este circular? Adica se poate incepe secventa la sfarsitul sirului si sa se continue la inceput?

Sa inteleg ca se cauta solutie in O(1) pe element in cel mai rau caz? Adica daca am o solutie in O(N) timp total si totusi un element poate fi accesat de O(N) ori nu este ok?

Probleme interesante , organizare fara probleme. 
Super ideea de a baga si un concurs pentru studenti.( chiar daca probabil ar trebui organizat undeva intre 11 seara si 3 dimineata ca sa participe mai multi studenti )

http://www.youtube.com/watch?v=2ya2M6gLRDI
_{patrat rosu}

Super tare articolul.
Am vazut insa in finalul articolului recomandarea folosirii algoritmilor in O(N) memorie, dar cu toate astea nu am gasit nicaieri in articol cum se face asta. Ar trebui poate explicat cum se calculeaza toate LCP-urile consecutive in O(N) folosind doar ultima linie din matricea P, reducand astfel memoria la O(N).

Pentru cei care stiu cat de cat franceza si vor sa participe la un concurs weekend-ul asta pe site-ul de pregatire ( chipurile pt IOI) al francezilor: http://www.france-ioi.org/concours/index.php
La ultimul concurs au fost interesante problemele( puteti sa le gasiti in arhiva) insa e posibil ca acum sa fie ceva mai usor din cauza numarului de participanti si a rezultatelor din vara
Site-ul are o gramada de probleme, dar din cate am vazut cele mai interesante pot fi vazute doar cu invitatie.
Edit: am uitat sa zic ca inscrierea la concurs( deschisa oricui) se face trimitand un mail organizatorilor cu id-ul de pe site. Este recomandat daca participati( sau vreti) sa trimiteti cat mai repede mail-ul pentru ca acces-ul la probleme nu se face automat.

Acum ca m-am oprit din ras nu pot sa o tin doar pentru mine..
http://youtube.com/watch?v=MRH4wq0LeFw

Sper ca am nimerit in locul potrivit...
Vroiam sa il felicit pe domino pentru calificarea la finala TCCC 2007 ( inca neoficiala, dar nu prea vad ce s-ar mai putea intampla). Multa bafta in finala.
Si o urare de final: la mai multi rosii romani!

Ai demonstrat tu ca ai destula memorie pentru solutia ta indiferent de test? Sau te-ai bazat pe faptul ca testele sunt generate aleator si pentru anumite grupe de numere ai o gramada de submultimi cu aceeasi suma? Caz in care tot ciucuiala se cam numeste programul...

De ce nu ar merge, daca esti asa de sigur pe simetria aia? Apuca-te de ea( mai mult de 10-15 linii nu ar trebui sa scri la ea) si in caz ca nu iese stai si o sa faci sa mearga... daca dupa multe ore de munca nu reusesti nimic( adica te dai batut) poti intreba pe forum...