Here's the statement again:

M marbles are placed in N cups which are arranged in a circle. One move consists in choosing a cup, taking all the marbles within that cup and placing them one by one in the following cups in clockwise order (since the cups are in a circle you might end up putting marbles in the original cup as well).

Given two placements A and B of marbles in cups, how can we tell if we can reach B starting from A.

Solution:

The state with all marbles in the first cup can always be reached. (1)

While we can find another cup with marbles, we apply one move on that cup. Marbles will move around the circle and from time to time fall into the first cup. Since we never make a move on the first cup, eventually all the marbles will end up in it. You guys figured this part in the comments.

Every state A has n outgoing edges (they can be self edges). (2)
We can apply one move on each cup.

Every state A has n incoming edges (self edges included). (3)
Here's an example: Let A be 0 1 2 1 0 0.
We can reach this state from 0 1 2 1 0 0 applying a move on cup 1 (self edge), 3 0 1 0 0 0 applying a move on cup 1, 2 0 1 1 0 0 applying a move on cup 1, 1 0 2 1 0 0 applying a move on cup 1, 0 1 2 1 0 0 applying a move on cup 5 (self edge), 0 1 2 1 0 0 applying a move on cup 6 (self edge)

From (2), (3) the graph is Eulerian, from (1) the graph is also connected. It follows that we have an Eulerian cycle that goes through all edges and nodes. Which means we can reach any state from any other state.

Thanks Andrei Dragus for the neat problem.

Regretăm să vă anunţăm că soluţia oficială a problemei Tembelizor de la Runda 2 a Algoritmiadei este greşită. Mai mult decât atât, nu am reuşit să găsim o soluţie corectă care să rezolve problema pentru restricţiile date în concurs. Ne-am aflat astfel într-o poziţie dificilă, întrucât orice decizie ar fi afectat negativ anumiţi concurenţi. În final, am decis să scoatem problema complet din clasament, runda are astfel un punctaj maxim de 300 de puncte şi nu va influenţa ratingul. În acelaşi timp, pentru a atenua pe cât posibil efectele acestei decizii asupra calificărilor în finală, am hotărât să organizăm şi Runda 4 a concursului, într-o perioadă ce urmează a fi determinată.

Suntem foarte dezamăgiţi de ce s-a întâmplat şi ne cerem scuze tuturor participanţilor pentru dificultăţile create :(.

Andrei Dragus told me this cute puzzle a year or two ago.

M marbles are placed in N cups which are arranged in a circle. One move consists in choosing a cup, taking all the marbles within that cup and placing them one by one in the following cups in clockwise order (since the cups are in a circle you might end up putting marbles in the original cup as well).

Given two placements A and B of marbles in cups, how can we tell if we can reach B starting from A.

Punem în atenţia voastră anunţul comisiei CEOI 2016 în legătură cu propunerea subiectelor, anunţ publicat iniţial pe olimpiada.info.

CEOI 2016 - Call for tasks !

Comisia stiintifica a CEOI va invita sa propuneti probleme pentru competitia ce va avea loc in 2016, la Piatra Neamt! Problemele propuse trebuie sa fie de natura algoritmica, dar pot fi de orice tip: clasice, interactive sau output-only. Pentru a asigura o competitie cinstita, problemele propuse trebuie sa respecte urmatoarele reguli (similare cu cele de la IOI):

- Problemele trebuie sa nu fie sau sa fi fost vazute de vreun potential participant la CEOI 2016.
- Problemele trebuie sa nu fi fost propuse intr-o competitie similara (online sau on-site).
- Problemele trebuie sa fie rezolvabile de concurenti intr-un timp de maxim 5 ore.
- Enunturile trebuie sa fie clare si usor de inteles.
- Problemele trebuie sa fie originale si/sau inovative.

Pentru a fi acceptata, o propunere de problema trebuie sa contina urmatoarele:

- Enunt in limba romana, in plain-text sau PDF;
- Descrierea solutiei care obtine punctaj maxim (preferabil si solutii partiale);
- Adresa de email a autorului;
- CV-ul autorului, care sa contina si un scurt rezumat al activitatii acestuia in domeniul informaticii.

Toate aceste fisiere trebuie arhivate in format .zip (o singura arhiva !)
Daca submisia va trece de selectia initiala, propunatorul va fi rugat sa trimita si:

Sursa care implementeaza solutia optima + surse care obtin punctaje partiale
Teste si generator de teste
Va asteptam sa trimiteti problemele pe adresa ceoi-2016-call-for-tasks [at] googlegroups [dot] com.

Termenul limita este 31 mai pentru CEOI. Problemele trimise inainte de 30 aprilie vor fi luate in considerare pentru CEOI si loturi, in timp ce problemele trimise inainte de 31 martie vor fi luate in considerare pentru CEOI, loturi, ONI si baraj.

Spor la compus! :)

A while back Ovidiu Gheorghioiu told me this neat problem:

How would you build an efficient prime number generator?

Let the generator be an object G with the method nextPrime(). When we call it G.getNextPrime() the first time it returns 2. Every time we call it again it returns the next prime number.

So if we do:
G = PrimeGenerator()
print G.nextPrime()
print G.nextPrime()
print G.nextPrime()

We'll get
2
3
5

During this winter break I've spent some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices' by George Varghese. Thanks Vlad Balan for recommending the book. It's fun to see how algorithms are heavily used in real world networking. I've stumbled upon a cute problem that I'd like to share (I might have seen it CLRS as well). Here it is:

IDENTIFYING A RESOURCE HOG

A software or hardware module needs to keep track of resources required by various users. The module needs a cheap way to find the user consuming the most resources. Since ordinary heaps are too slow, the device designers are willing to relax the system requirements to be off by a factor of 2. Can this relaxation in accuracy requirements be translated into a more efficient algorithm?

To paraphrase, the problem asks for a data structure with the following operations

• use_resources(name, quantity) which does resources[name] += quantity (quantity can also be negative)
• get_approximate_max() which returns name1 such that max(resources[name]) / 2 <= resources[name1] <= max(resources[name])

Using a map in combination with heap gives us a solution with O(log n) time for each of the two operations. Can we do better?

Anul 2015 s-a încheiat si m-am gândit ca ar fi potrivit să facem o trecere în revistă a celor mai importante momente din 2015 ale comunităţii informatice din România. Lista următoare este pur subiectivă, şi vă invit să o completaţi în comentarii cu alte fapte, evenimente sau experienţe pe care le consideraţi importante, fie şi din punct de vedere pur personal.

Rareş

Performanţa lui Rares Buhai •darren de a ajunge pe locul 2 în Hall of Fame-ul IOI este fără îndoială de luat în seamă. Am ales să o trec pe prima poziţie a retrospectivei deoarece consider că Rareş va rămâne multă vreme cel mai bun performer al României la Olimpiada Internaţională de Informatică (poate fi doar egalat având în vedere regulile actuale ale Olimpiadei Naţionale). De asemenea, mediatizarea de care a beneficiat ajută la atragerea mai multor elevi spre domeniul informaticii, iar parcusul lui îi va inspira să muncească pentru a obţine, la rândul lor, rezultate frumoase. Tot ce mai putem dori acum este ca Rareş să continue colaborarea cu comunitatea din România, atât cât îi va permite timpul, pentru că sunt sigur că poate contribui cu mai mult decât medalii.

Juniorii

Deşi performanţele României la JBOI au fost dintotdeauna foarte bune, Harsan Razvan •hrazvan , Alexandru Petrescu •alexpetrescu , Ioan Andrei Nicolae •killer301 şi Udristoiu Alexandra Maria •alexandra_udristoiu sunt cei care au adus acasă cel mai bun rezultat din istoria competiţiei - 3 medalii de aur (inclusiv primul loc) şi una de bronz. Tot juniorii ne-au salvat onoarea şi la Shumen , obţinând 2 medalii de aur, 3 de argint şi 3 de bronz. Şi, judecând după curajul unora dintre ei de a participa la categoria Seniori a Algoritimiadei şi, mai mult, după punctajele bune obţinute la această categorie, aş zice că viitoarele rezultate ale României la competiţiile internaţionale vor fi la înălţimea aşteptărilor. Această previziune se va adeveri desigur doar dacă cei menţionaţi mai sus, alături de ceilalţi membri ai lotului, se vor pregăti în continuare cu aceeaşi seriozitate şi nu se vor mulţumi cu medaliile obţinute în anii junioratului.

Demn de menţionat şi plăcut surprinzător este şi că jumătate din lotul restrâns de juniori a fost compus din fete. Le felicităm pentru performanţele obţinute şi le dorim succes pe mai departe.

Seniorii

Nu putem încheia această listă fără a menţiona pe toţi cei care au obţinut medalii din partea echipelor oficiale ale României la competiţiile internaţionale din acest an. Aceştia sunt:

• Rares Buhai •darren - Aur la IOI, Argint la CEOI
• Alex Velea •veleandu - Aur la CEOI, Argint la IOI
• Valentin Harsan •valentin.harsan - Argint la CEOI, Argint la IOI, Bronz la Shumen
• Oncescu Costin •geniucos - Argint la BOI
• Denis Mita •Kira96 - Argint la BOI
• Marian Darius •dariusdarius - Argint la BOI
• Popa Andrei •andreiiii - Bronz la CEOI, Bronz la IOI
• Vlad Rochian •vladrochian - Bronz la BOI

Îi felicităm pe toţi în egală măsură şi le dorim succes în anul care urmează.

2016

La ce ne putem aştepta deci în 2016? Cu plecarea lui Rareş Buhai, Alex Velea şi a lui Valentin Hârşan, lupta pentru calificarea la IOI devine foarte deschisă. Ne dorim desigur ca figurile vechi să îşi îmbunătăţească rezultatele, şi ca cele noi să producă surprize frumoase. Nu în ultimul rând, CEOI 2016 va avea loc în România, iar numărul de locuri rezervat ţării noastre va fi desigur mărit. Aş zice că momentul ales este cum nu se poate mai bun, deoarece lasă loc multor concurenţi cu potenţial de a se afirma la primul lor concurs internaţional de seniori.

În loc de încheiere, reiterez invitaţia de a ne scrie cele mai importante momente ale lui 2015 pentru voi în secţiunea de comentarii, şi adaug o listă de "New Year's Resolutions" cu specific informatic:

• Participaţi la cât mai multe concursuri. Algoritmiada, Codeforces, USACO, COCI, TopCoder şi Mindcoding vă sunt prieteni.
• După ce terminaţi de participat la un concurs, rezolvaţi problemele care nu v-au ieşit în timpul competiţiei, eventual după ce aţi citit soluţiile oficiale. Majoritatea site-urilor oferă această posibilitate, şi doar aşa puteţi progresa.
• Updataţi-vă profilul pe infoarena. Poate că vi se pare inutil, dar din punctul de vedere al unui începător, este mult mai uşor să discute cu un utilizator experimentat atât online cât şi în viaţa reală dacă ştie despre el mai mult decât numărul de probleme rezolvate şi ratingul. Aşa DA: Adrian Budau •freak93 , Eugenie Daniel Posdarascu •eudanip ; aşa NU: Popa Andrei •andreiiii , Mihai Calancea •klamathix .
• Nu mai participaţi de pe conturi fantomă: e o dovadă de maturitate să vă asumaţi pregătirea, succesele şi eşecurile în faţa altora. În plus, dacă toţi procedaţi aşa, puteţi obţine sugestii de probleme pe care să le lucraţi urmărindu-i pe ceilalţi.

Nu în ultimul rând, La Mulţi Ani 2016!

Hour of Code reprezinta sansa de a accesa domeniul IT intr-un mod interactiv si oportunitatea de a cunoaste si controla tehnologia prin tutoriale simple, cu personaje cunoscute tuturor ca Minecraft sau Star Wars.

Acest eveniment sta la baza evolutiei educatiei IT din Romania si alte tari au inteles deja asta: Italia are inregistrate 11.000 de evenimente in timp ce Romania are inregistrate doar 700 de evenimente.

Pentru ca industria IT de maine este responsabilitatea noastra, a tuturor, va invitam sa organizati un eveniment Hour of Code in cadrul institutiei dumneavoastra de invatamant. Nu trebuie decat sa va inscrieti evenimentul pe hourofcode.com/ro, sa alegeti o zi in intervalul 7-13 decembrie si sa parcurgeti impreuna cu elevii tutorialele de pe site-ul ro.code.org .

De asemenea, elevii/studentii la informatica pot sa se transforme in mici profesori si sa predea o Ora de Programare colegilor de la alte profile sau specializari.
Fiecare organizator va primi cate un premiu garantat oferit de partenerii internationali si solutii de securitate software din partea Bitdefender Romania. ADFABER va pune la dispozitie gratuit materialele de care aveti nevoie, efortul organizatorilor fiind unul minim.
Haideti sa facem cunoscut evenimentul Hour of Code si sa promovam Romania ca tara IT!

Link-uri utile:
Materiale necesare aici: bit.ly/Materiale
Facebook (sharing is caring): facebook.com/HourofCodeRo
Inregistrare eveniment Hour of Code (hourofcode.com/ro) - pana pe 4 Decembrie
Participare eveniment ro.code.org

Prima rundă a concursului Algoritmiada 2016 va avea loc Duminica, 6 decembrie, ora 10:00. Mai multe detalii despre formatul şi regulamentul concursului, cât şi despre programul complet al rundelor de calificare puteţi găsi aici.

Vă aşteptăm în număr cât mai mare, cu intenţia ca problemele să fie interesante pentru orice participant, indiferent de vârstă sau nivel de experienţă. Baftă!

Suntem încântaţi să anunţăm extinderea echipei infoarena cu doi noi membri! Aceştia sunt Marian Darius •dariusdarius şi Popa Andrei •andreiiii. Andrei şi Darius sunt veterani ai olimpiadelor de informatică, iar în curând vor fi şi veterani ai comisiilor :). Le urăm bun-venit şi o perioadă cât mai fructuoasă în cadrul echipei, atât pentru ei cât şi pentru comunitatea infoarena.