Dar nu inteleg un lucru. Sa luam ca exemplu datele din enunt. Un sir A_0...15 si un sir B_0...3. Sa presupunem ca la inceput toate elementele acestor siruri sunt egale cu 0. Apoi facem update pe intervalul [ 4, 7 ]- sa zicem ca crestem elementele din intervalul asta cu 2- apoi cautam sa gasim suma elementelor din intervalul [ 6, 8 ]. Acest interval are prima parte ( [ 6, 7 ] ) in intervalul [ 4, 7 ] si a doua parte ( [ 8,8 ] ) in intervalul [ 8, 11 ]. Acuma daca vom cauta elementele 6 si 7 in sirul A, acestea vor fi 0, nu? Cand am facut Update pe intervalul [ 4, 7 ] am crescut cu 2 doar B₁, elementele din A au ramas nemodificate. Un astfel de exemlu poate fi gasit si cand intervalul a carui suma o cautam contine un interval de forma [ k sqrt(n), (k+1) sqrt(n) ]. Unde gresesc? Din enuntul articolului si din ce ati spus voi nu imi dau seama.

LA "Smenul lui Batog" unde se imparte intervalul in bucati de sqrt ( n ) cum se face query-ul?

Cred ca se refera la ceea ce apare uneori ca si inmultirea sau compunerea unei permutari.
Daca avem

p1=

1 3

2 1

3 5

4 4

5 2

si

p2=

1 4

2 2

3 5

4 3

5 1

atunci daca compunem p₁ cu p₂ avem

p1*p2=

1 4

2 1

3 2

4 5

5 3

unde (p₁*p₂)(x)=p₁(p₂(x))
Si cred ca daca compui p₁ cu p₂ se mai numeste ca aplici p₁ peste p₂.
Pentru detalii despre permutari si compunerea acestora poti sa verifici un manual de clasa a 11-a.

Se pare ca peste tot in liceu se "invata" C++, dar la sfarsit cam toata lumea stie doar C.
Supraincarci operatorii:

Cod:

void add(int A[], int B[])
{
      int i, t = 0;
      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)
              A[i] = (t += A[i] + B[i]) % 10;
      A[0] = i - 1;
}
struct BigInt{
   int a[128];
   void operator += ( BigInt x ){
        //cod pt adunare
          add(a,x.a);
  }
};
BigInt m, n;
int main(){
       m.a[0]=3;
       m.a[1]=2;
       m.a[2]=8;
       m.a[3]=4;
       n.a[0]=3;
       n.a[1]=6;
       n.a[2]=1;
       n.a[3]=9;
       m+=n;
       return 0;
}

Scuze ca nu am spus care e problema la algoritmul acela: dupa rulare uvec[2] va fi +4 in loc de -4.
Se pare ca gresisem. Verificam daca multimea il contine pe i in loc de max in linia a treia de la inserare.

Multumesc de raspuns(uri). Dar mi se pare ca e o problema in codul tau ( al doilea post ). Eu am presupus ca uvec e zona de memorie data in enuntul problemei, ca la inceputul rularii algoritmului tau max e egal cu 0 si ca presupunerea facuta de tine legata de marimea intregilor tine de marimea intregilor care pot fi memorati in zona de memorie, iar nu de marimea intregilor care vor fi inserati/testati de apartenenta(astia incep de la 0 si se duc pana la U-1) si ca i din algoritm e intregul care e inserat sau testat daca apartine multimii. Apoi am testat algoritmul tau pe urmatorul set de date de intrare:

Cod:

insereaza 2
insereaza 3
insereaza 4
test 3
test 4
test 2

Si nu mi-a dat prea bine... Instructiunea test x testeaza daca x a fost adaugat in multime.
Sper ca nu am gresit cand am "rulat" algoritmul.
Si legat de ideea de a folosi faptul ca nu se specifica dimensiunea intregilor care pot fi memorati in zona de memorie data sa stii ca nu prea imi "place"-dar asta e legat strict de preferinte. As fi interesat sa vad un algoritm care accepta si urmatoarea restrictie: intregii memorati in zona de memorie sa fie in intervalul inchis [0,U-1] sau macar zona de memorie sa fie continua si sa contina U bucati de cate 1+[log (U-1)] biti. Si [y]=parte intreaga din y. Nu merge cu x.

M-am gandit si eu la aceasta solutie, dar nu mi s-a parut ok. Pe aceasta structura de date trebuie sa se execute operatii "de initializare, adaugare si verificare a incluziunii" in timp constant cu O(n) memorie aditionala. Daca primim doar un sir de astfel de operatii nu o sa stim numarul final n de elemente. Si astfel nu stim cata memorie trebuie sa alocam pentru vectorul nostru. Si nu putem sa alocam memorie pe masura ce adaugam elemente la sirul nostru, cum e, de exemplu la vector din stl ( in c++ ), pentru ca, din cate stiu eu, asta e O(1) amortizat. Liste nu putem sa folosim, pentru ca avem nevoie de indexare. Gresesc undeva?
L.E.: Nu stiu in Python cum sunt implementate array-urile alea.
L.L.E.: Acuma am vazut ca se presupune stiut numarul de elemente adaugat de dinainte. Nasol. 

Numarul n e dat separat sau are stream-ul o metoda gen size()? Sau trebuie sa il aflam parcurgand o data streamul? Si cand ajungem la capatul streamului ce putem face ca sa il mai parcurgem odata?
Este vreo metoda gen setp()? Vreun reset ceva?
L.E.: Scuze, prea multe semne de intrebare.

In "Introducere pentru algoritmi"  este un capitol destul de detaliat despre sortare si statistici de ordine:
http://zhuzeyuan.hp.infoseek.co.jp/ita/partii.htm. Wikipedia ajuta de asemenea, daca vrei sa cauti notiuni ca stable, in-place etc.

A implementat cineva algoritmul lui Fleury? Nu prea stiu cum sa determin daca o muchie e punte(sau critica...) dupa update in mod eficient.
L.E.: Niciun test nu contine un graf care nu este conex?

Eu sunt curios ce asteapta angajatorii de la tine cand iti dau o asemenea problema. Eu vad doua variante: ori stii de dinainte problema ori gasesti solutia in 10-15 minute(pb de interviu). A doua varianta mi se pare prea putin probabila pentru cea mai mare parte a angajatilor. Chiar si pe un site pentru olimpici cred ca s-au gasit putini rezolvitori. Asa ca nu cred ca oamenii astia care fac angajarile cauta sa le dai raspunsul. Dar ce asteapta de la tine? Daca sunt persoane informate, le rog sa raspunda. Daca sunt offtopic, imi cer scuze.

Da e bun. Eu am intrebat si acolo. Mersi totusi. Nu stii cum pot modifica titlul topicului? Am introdus un '|' din greseala in titlu.

Are cineva vreo idee la problema E? Dau plus la karma  
http://acm.ro/prob/probleme/E.pdf

Way cool: http://infoarena.ro/forum/index.php?topic=4965.0 

Daca esti din Iasi dute in Bucuresti, daca esti din Bucuresti dute in Iasi, desi eu sunt convins ca tu esti de pe undeva de langa Iasi sau chiar din Iasi...
Oricum eu sunt convins ca diferenta in pregatirea ta in informatica nu va fi facuta de una dintre aceste doua universitati, ci de tine. (Diferenta intre cele doua universitati e suficient de mica incat sa puna oameni ca tine in cumpana).

Iacata, avem unul. Cred ca e Bogdan Tataroiu http://infoarena.ro/utilizator/bogdan2412 dupa handle. Azi am participat pentru prima data si eu la un srm si desi am facut doar prima problema si 2 chalenge-uri reusite am luat ratingul 1400. Sper sa ma mentin, ba chiar sa cresc. Totusi nemultumirea ta e nejustificata. Tu ce culoare ai pe TopCoder? Ce vreau sa spun e ca de fapt romanii nu prea participa pe TopCoder, desi sunt destui care sunt buni(vezi utilizatorii acestui site). Poate li se pare prea complicat. Mie asa mi s-a parut pana azi. Desi am cont pe Topcoder de peste 2 ani, abia azi am participat pentru prima data la un rated event. De fapt nu e asa complicat. Daca se doreste, miscarea pro topcoder poate fi reluata.

Poate ai depasit memoria. Din cate stiu un bool ocupa un byte, iar bitset implementeaza, cred eu, mai eficient dpdv al memoriei lucrurile. Cu vector <bool> se iroseste 7/8 din memoria alocata.

Poate ar trebui adaugata si problema postasului chinez? http://en.wikipedia.org/wiki/Route_inspection_problem
Astazi am intalnit-o din nou dupa ce am facut-o in semestrul intai la facultate si ma gandeam ca ar intra la "clasice". Daca vreti ma ocup eu, ca oricum sunt in vacanta.

Urmatoarea problema e clasica in teoria numerelor:
Sa se rezolve ecuatia:
ax = b ( mod n )
unde a, b, n sunt numere intregi cu n > 0. (Sa se rezolve ecuatia la info ar insemna sa se gaseasca toate numerele x (0<=x<n) care satisfac echivalenta)

Stie cineva vreun link spre aceasta problema intr-o arhiva de probleme cu evaluator online?

Am generat teste random si totul imi pare ca merge bine, dar as vrea sa incerc si alte teste, daca e posibil pe un eval online. Multumesc!

Daca e urgent urgent sa fie! Poti sa incerci backtracking (generezi permutari). Vezi http://en.wikipedia.org/wiki/Rook_polynomial

Cred ca trebuia sa incluzi si factorul timp. O problema pusa in arhiva de o luna nu e asa de "rezolvata" ca si una pusa in arhiva de 5 ani, chiar daca au dificultatea asemanatoare.
+ la karma.

Mai citeste enuntul: "Rezultatul se afiseaza modulo ..."

MaxS e prea mic sau N*N e prea mare?

Eu consider ca orice olimpic care se respecta ar trebui sa aiba in biblioteca sa macar varianta tradusa in romana ( varianta cea mai buna ar fi originalul - adica in engleza ). Tine de statut. Aceasta carte reprezinta excelenta - a fost creata ca o baza pentru studentii care participa la concursurile ACM(, nu?) - simplul fapt ca ai cumparat aceasta carte spune ceva despre tine. Cat despre faptul ca nu avem nevoie de aceasta carte e la fel de adevarat ca si faptul ca nu avem nevoie de un ceas de mana(ne putem uita pe telefon?!, vezi http://pmircescu.blogspot.com/2010/04/am-auzit-pe-cineva-spunand-la-ce-mi.html). Se poate sa scrii soft foarte bun si chiar sa creezi algoritmi tari fara carti. Dar e mult mai usor daca urmezi o cale deja parcursa(In loc sa stai cateva zile(saptamani, ani) pana sa inventezi un algoritm de flux, de exemplu, poti sa petreci cateva ore studiind algoritmii deja dezvoltati, iar dupa aceea daca chiar vrei sau trebuie - lucrezi in cercetare - poti si sa iti tocesti neuronii scotocind algoritmi noi). Parerea mea...

Sa nu fim rai, totusi Poate ca acele cazuri au fost alese special astfel incat sa mearga doar o solutie corecta.
Stiti cum se zice... Esentele tari se tin in sticlute mici
L.E.: