"Up to linear in half the distance between first and last (in terms of actual swaps)." (http://www.cplusplus.com/reference/algorithm/next_permutation/)

Deci O(N/2), care poate fi aproximat la O(1) (pentru N <=8).

Poti participa neoficial (nu ti se schimba ratingul).

Nu e deloc corect sa compari punctajele pe toate clasele (generatii diferite, subiecte diferite, este foarte relativ). Tinand cont de ceea ce s-a zis si, cel mai bun sistem ar fi cel de la gimnaziu (X participanti la fiecare clasa, sistem care de altfel a fost dovedit de-a lungul anilor ca unul foarte bun). Bine inteles multi o sa zica ca nu e corect pentru cei de clasa 9-a, lucru adevarat dar care poate fi rezolvat prin distribuirea locurilor pe clase in mod neuniform. La clasa a 9-a cei mai multi, la clasa a 10-a mai putini iar la clasele 11-12 si mai putin Bineinteles, gasirea unor coeficienti buni este destul de dificil, dar asa pare cel mai ok.

Ma refeream la situatia in care fiecare judet are un numar fix de locuri, iar distributia se face in cadrul judetului.

In cazul in care nu este impusa aceasta conditie, atunci mi se pare ok selectia primilor X participanti in clasamentul general la fiecare clasa, iar locurile libere din fiecare judet (in caz ca exista) sa fie ocupate prin decizia inspectoratului scolar.
In prezent, exista posibilitatea ca intr-un judet sa apara elevi care au lucrat mult in cursul anului si au crescut ca nivel, dar care sa nu poata participa toti la ONI datorita numarului redus de locuri ale judetului respectiv. Daca s-ar aplica sistemul recomandat de tine, ei ar avea posibilitatea sa fie clasati intre primii X in clasamentul general, aducand un surplus de locuri judetului din care fac parte (asa cum este si logic).

Sistemul curent de distribuire a locurilor / judete mi se pare cam ineficient, deoarece exista judete care au avut rezultate bune in trecut, au acumulat un numar mare de locuri, iar in prezent obtin in general rezultate slabe, si exista judete care au un numar mic de locuri, si elevi buni, dezavantajati de rezultatele generatiilor anterioare. Desigur, numarul de locuri se echilibreaza treptat, astfel incat sa reflecte rezultatele din trecutul apropiat, dar cred ca aceasta echilibrare are loc intr-un ritm prea lent.

Sistemul de selectie propus ar asocia fiecarui judet un numar fix de locuri, in functie de rezultatele anterioare, + un surplus care reflecta rezultatele obtinute la OJI in anul curent. In acest mod, chiar si un elev de clasa a 9-a poate aduce locuri in plus judetului din care face parte, fara sa fi participat in trecut la vreo nationala.

În multe județe locurile sunt distribuite neuniform. De exemplu in Bucuresti la clasa a 11-a au fost prea puține locuri în timp ce clasa a 9-a a avut 10 locuri.

Sunt de acord in legatura cu distributia locurilor pe clase, dar nu cred ca este implicata direct comisia care organizeaza ONI. In judetul meu, inspectoratul judetean a decis repartizarea celor 4 locuri, singurul criteriu de departajare fiind punctajul obtinut (s-au calificat la ONI primele 4 punctaje, indiferent de clasa). E de asteptat ca diferiti algoritmi de departajare sa fie de preferat in defavoarea altora, dar totul ramane la latitudinea inspectoratelor judetene.

De exemplu dacă anul trecut un județ a avut rezultate bune la a 10-a, anul următor clasa a 11-a va avea locuri in plus. La clasa a 9-a cred că ar trebui sa fie făcută o medie a rezultatelor județului din anii trecuți de la clasa a 9-a. Din câte știu eu în ultimii doi ani dintre cei care au fost in lot in anul precedent cel putin doi oameni nu au mai trecut de oji. De aici ne dăm seama că selecția pentru oni sau selecția loturilor (sau ambele  ) nu sunt făcute cum ar trebui.

Cred ca cel mai in regula (si simplu) ar fi sa se distribuie locurile in functie de punctajul obtinut indiferent de clasa. Daca exista 3 elevi buni la clasa a 12-a care au punctaje foarte mari, iar la restul claselor punctajele sunt mici, atunci cei 3 ar trebui sa se califice chiar daca sunt in aceeasi clasa. In cazul unor punctaje apropiate, ar fi de preferat calificarea unui elev din clasele 10-11-12, in defavoarea unuia de a 9-a (clasa la care se obtin punctaje mari cu un nivel mai scazut de cunostinte).

Din moment ce la olimpiadele și concursurile internaționale exista feedback parțial mi s-ar părea normal ca și la selecția pentru ele să existe feedback. Mi se pare o prostie sa iei 0 puncte pe o problemă pentru că ai MLE sau pentru că nu ai respectat cu strictețe formatul fișierului de ieșire. Totuși aici sunt subiectiv pentru că am fost în ambele situații.

Si in aceasta privinta sunt de acord. Cateva teste de feedback date de comisie, in formatul celor de la Algoritmiada, ar putea reduce numarul de esecuri datorate unor astfel de greseli. Chiar daca testele de feedback nu vor face parte din setul final pe care vor fi evaluate sursele, faptul ca participantii pot vedea cum se comporta evaluatorul comisiei cu sursele lor le asigura un anumit grad de siguranta.

Cred că problema asta s-ar putea rezolva destul de ușor la oji din moment ce toate calculatoarele dintr-o școală sunt conectate la o rețea. La oni ar exista două soluții: Evaluator local care ar cripta(hashui)  fișierul .out si verificator in caz că sunt mai multe răspunsuri posibile sau o rețea de calculatoare la oni. Rețeaua ar necesita o investiție dar pe urmă ar putea fi folosită la mai multe ediții.

In cazul in care testele de feedback nu fac parte din cele definitorii, nu ar fi nevoie de criptarea lor, usurand astfel munca comisiei.

O problemă destul de mare mi se pare că e selecția lotului. În ultimii doi ani după noua metodă de selecție în care se ține cont și de rezultatul de la oni mulți de clasa a 9-a sau a 10-a îi depășesc pe cei mai mari datorită coeficientului. Mi se pare nedrept să departajezi elevi după subiecte diferite și relativ față de ceilalți din generația lor. Cred că ar fi mult mai potrivită înlocuirea zilei de pauză cu o probă de baraj sau un set de probleme mai numeros.

Cred ca singurul motiv pentru care ar merita pastrat coeficientul de la ONI este pentru a usura calificarea in lot a unui elev bun, care s-a descurcat la cele doua probe, dar care se intampla sa aiba o zi proasta la proba de baraj.
Reintroducerea celei de-a 2-a probe de baraj ar rezolva de la sine atat problema pe care incearca sa o rezolve coeficientul, cat si problemele pe care acest sistem le atrage de la sine (calificarea in lot a prea multor elevi din clasele 9-10). In plus, un set de 6 probleme (in comparatie cu 3) permite un grad mult mai ridicat de variatie, motiv pentru care ar creste si nivelul de acuratete al departajarii.

Totuși chiar și cu 3 probleme s-ar putea face o departajare bună dacă comisia ar prezenta un set de probleme cu teste bine realizate și cu probleme bine calibrate ca și dificultate.

Din nou, introducerea a 2 probe de baraj ar rezolva aceasta problema.

În plus atât timp cât nu exista feedback nu sunt de acord cu problemele interactive deoarece nu prea ai cum să-ți dai seama că interacționezi corect cu programul comisiei. De exemplu anul ăsta au fost foarte multe punctaje de 0 (http://oni2013.info.tm/r_b.pdf) la o problemă la care era destul de simplu sa iei 40 puncte din cauză că uita să citească un 1 afișat de programul comisiei, iar exemplul de pe foaie nu era prea cuprinzător.

Si in acest caz, cred ca ar trebui introdus un mini-set de teste de feedback, sau chiar programul comisiei care ruleaza in paralel cu executabilele participantilor, pentru a putea simula interactiunea dintre cele 2.


In legatura cu evaluarea in formatul IOI, cred ca ar fi bine sa fie aplicata cel putin in cazul probei de baraj, daca nu chiar pentru toate probele de concurs.

Se va face un update de rating pentru ultima runda .com si cea de astazi?

@Vlad Costin: din cate stiu, primii 10 / grupa de varsta, + cei de pe locul 10, in caz ca exista punctaje egale.

Pentru ultimul test (cel de la oni e de forma: 1, 3, 5 6 7 ... 20000 20001 20002, si tind sa cred ca si aici e acelasi) poate sa imi explice cineva de ce raspunsul corect la cerinta a 2-a este 3? 

In cazul asta, exista 3 partide, primul format dintr-un singur parlamentar, al doilea la fel, si al 3-lea din 19 998 de parlamentari.
Coalitiile posibile ar trebui sa fie: P1+P2+P3 si P2+P3. Coalitia P1+P2 nu cred ca ar trebui sa fie numarata, pentru ca cele 2 partide au impreuna 2 parlamentari, numar mult mai mic jumatate din numarul total de parlamentari (10 000).

Atat solutia in O(n log n) pe care am trimis-o, cat si brutul in O(n^2), dau raspuns incorect la cerinta a 2-a...

http://infoarena.ro/problema/combinari - e problema din arhiva educationala, sunt disponibile sursele de 100 de puncte.

Cred ca Project Euler are utilitate mai mare ca hobby, si ca imbunatateste mai mult atentia si gandirea matematica decat cea algoritmica. M-a ajutat sa imi formez bazele cand am inceput sa invat python (dupa ~50 probleme rezolvate am inceput sa scriu destul de fluent, lucru care mi-a fost de folos in cateva competitii de pe Codeforces, unde viteza de implementare e esentiala).

Cat despre timus, arhiva de probleme e ok, majoritatea problemelor au indicii de rezolvare pe forum, astfel ca te poti descurca si atunci cand nu ai nicio idee. Singurul dezavantaj ar fi frecventa redusa a concursurilor (pana acum am participat la un singur concurs, in formatul ACM-ICPC).

Da, trebuie afisate in ordinea crescatoare a valorii lor, deoarece mutarea elementului VAL in dreapta elementului VAL-1 implica automat ca elementul VAL-1 sa fie amplasat corect, si asta nu-i neaparat adevarat daca nu tii cont de ordine...

Problema e foarte asemanatoare cu asta: http://codeforces.com/contest/270/problem/D, diferenta fiind ca aici trebuie sa afisezi si operatiile propriuzise.
Pentru ca numarul de operatii sa fie minim, incerci sa alegi un subsir cat mai lung a.i. elementele din el sa poata ramane la pozitiile lor si sa nu trebuiasca mutate (adica sa fie deja in ordine crescatoare), ceea ce coincide cu gasirea celui mai lung subsir crescator. Astfel ca numarul minim de mutari este egal cu N - L, unde L = lungimea celui mai lung subsir crescator.
Pentru a determina operatiile, se introduc intr-un vector toate valorile care nu fac parte din subsirul crescator maximal (adica valori care trebuiesc mutate de la pozitiile lor), si se parcurg in ordine crescatoare (ar trebui sa functioneze si o parcurgere in ordinea in care apar). Pentru fiecare valoare VAL, ea trebuie mutata la dreapta valorii VAL-1, astfel ca fiecare operatie este de forma "VAL VAL-1". Complexitatea finala O(N log N). Sper ca ti-am fost de ajutor!

Mi se pare cea mai buna runda de pana acum. Felicitari comisiei!

Eu am scos o(n log n) cu o sortare si cautare binara a termenilor ce fac parte din progresii aritmetice cu ratia (2*pi*r / k). Pe testul 7 am 148ms. Se poate demonstra corectitudinea solutiei in o(n)?

Am trimis la queue o sursa goala care ia 100: http://infoarena.ro/job_detail/860763
Rog un admin sa se uite peste problema...

Cod:

4: read(5) pop(2) push(1,2) push(1,5)

aici, tu il citesti pe 5 (wr = 5), apoi scoti varful din stiva 2 (wr = varful = 2), il introduci pe wr (=2) in prima stiva, dupa care incerci sa il introduci si pe 5 (numarul citit initial) in aceeasi stiva.
ultima operatie nu respecta restrictia scrisa mai sus, pentru ca functiei push() ii poti da ca parametru doar valoarea actuala a variabilei wr, iar tie ti se pierde acea valoare.

corect ar fi cam asa:

Cod:

4: pop(2) push(1,2) read(5) push(1,5)

De ce este gresit output-ul acesta ?
[...]
Nu inteleg .

nu e gresit, si sursa mea da exact acelasi output pe exemplu, si ia ok pe testul de feedback.
ai grija la restrictia "O operatie de push efectuata pe una dintre stive se considera valida daca valoare folosita se afla in WR."

mie mi se vad ok toate, nu stiu ce greutati intampinati voi.

1 ≤ N < 10^100, ceea ce inseamna ca nu ai cum sa-l ridici la puterea N, si nici macar sa stochezi numarul intr-un tip de date numeric (depaseste cu mult long long). citeste comentariile anterioare, incearca sa vezi daca te poti folosi doar de o mica parte din cifrele numarului dat. sper ca ti-am fost de ajutor

O mica greseala, e 12 ianuarie, nu decembrie.

O(N * Suma_lungimi) este si complexitatea oficiala.

@Andrei1998: Cu O(N * Suma_lungimi) s-ar putea sa ai nevoie de putina optimizare, la fel cum am avut eu, dar se poate rezolva problema si in O(100*suma/2), complexitate care intra mult mai lejer in timp.

observ ca tu iei toate intervalele in ordinea crescatoare a capatului superior, si la fiecare pas cumperi o secventa din intervalul actual. exista posibilitatea ca aceeasi secventa (sa zicem [0, k-1], cat e cea pe care vrei sa o acoperi initial) sa poata fi cumparata din mai multe intervale, cu costuri diferite, si atunci nu are sens sa le folosesti pe toate.
in plus, pentru n = k (sau pentru valori apropiate), si intervale de genul [0,1] [0,2] [0,3], ..., [0,n], algoritmul tau parcurge si cumpara toate intervalele mici, oprindu-se doar cand a acoperit intreaga secventa [1,n]. in cazul asta e clar ca poti cumpara doar ultimul interval in intregime, cu un cost mult mai mic decat suma tuturor. aceeasi idee si pentru alte valori ale lui k: solutia nu consta intotdeauna in intervale alaturate, ci intr-o submultime formata din intervale care nu au neaparat legatura ca pozitie in sirul ordonat.

algoritmul meu se bazeaza pe o idee asemanatoare, doar ca incep constructia de la pozitia n, si folosesc sirul sortat descrescator. initial, e sigur ca exista cel putin un interval din care sa pot cumpara o secventa ce se termina pe pozitia n (altfel nu ar exista solutie). in caz ca exista mai multe astfel de intervale, il aleg pe cel cu costul minim si cumpar din el o secventa de dimensiune k (nu are rost sa cumpar una mai scurta).
la pasul urmator, voi avea de cumparat o secventa care se termina pe pozitia n-k, alegand-o din mai multe intervale. din nou, aleg intervalul cu costul minim, cumpar de acolo secventa de lungime k, pozitia noua pe care va trebui sa o acopar va fi n-2k. de aici se repeta tot procedeul.

mai trebuie avut grija la marcarea intervalelor folosite, ca sa nu cumperi 2 secvente din acelasi interval.
sper ca te-am putut ajuta. 

cu un algoritm brut in o(n*k) am luat 2 tleuri. solutia tinea doar de optimizare?

s-ar putea sa primesti eroarea cand numerele din fisier.in sunt pe aceeasi linie.

Cod:

#include <iostream>
#include <fstream> //ai nevoie de biblioteca asta ca sa functioneze lucrul cu fisiere text
using namespace std;

int main() {
  ifstream f("adunare.in");//declari o variabila pe care o asociezi cu fisierul de intrare
  ofstream g("adunare.out"); //aceeasi idee, dar pentru fisierul de iesire

  int a, b;
  f>>a>>b;        //pentru citirea de pe ecran foloseai cin>>a>>b;, pentru fisiere, "cin" se inlocuieste cu variabila asociata fisierului de intrare
  g<<a+b<<"\n"; //la fel, "cout" se inlocuieste cu "g", adica variabila asociata fisierului de iesire; "\n" tipareste si o linie noua in fisier

  f.close();        //inchizi fisierele; din cate stiu, poti omite liniile astea 2, si o sa se inchida fisiere automat la sfarsitul executiei programului
  g.close();
  
  return 0;
}

pe langa citirea cu streamuri (exemplul de mai sus) exista si citirea standard din C ca alternativa, dar nu o folosesc.

sunt curios care era solutia la subset2...  poate posta cineva ideea de rezolvare?

da, fiecare numar din [1,N] apare cel mult o data in subset