Nodul 1, 2, ..

Problema are acum feedback partial. Puteti submita din nou sa vedeti borderoul. Vom reevalua si sursele trimise pana acum in noaptea aceasta, pentru a nu incetini evaluatorul.

Da

Ai dreptate, am schimbat acum enuntul legat de acel typo.

• Padurari - grea de abordat, dar foarte faina si neasteptata solutia in final
• RangeMode - pentru ca m-am chinuit mult la ea, iar tehnica se intalneste des acum
• Peluza Nord - dinamica pe cifre
• Ciocolata2 - tabla de sah + cuplaj, draguta
• Poveste - pentru ca a intrat ceva inspirat din Method of Four Russians
• Number of Paths - problemele ca asta sunt 10/10
• Centrale Nucleare - foloseste arborele de intervale ca un graf compresat
• Sokoban - pentru ca e cu biconexe pe matrice
• Ghiozdan - bounded knapsack + Hirschberg's algorithm
• Cabane - pentru solutia ingenioasa

@Bogdan, ) misto. Ma lasa memoria , stiam ca am mai vazut-o si pe infoarena .

Ma bucur . Ar fi trebuit sa o mentionez din primul post, pentru ca de acolo o stiam. Contributia mea a fost extinderea pentru varianta online. Intre timp au tot aparut problemele unde se poate folosi aceasta idee, precum unique, calafat sau pq.

The same idea is used to solve distincte or DQUERY on SPOJ, which are the same problem as this one. Perhaps the editorial for distincte will shed some light over this.

Let's map every user_id to a smaller value, but do it in such way that we maintain their order (we normalize them). Every timestamp query characterizes a substring in our log, therefore we can replace the timestamps with array indexes according to our log.

We can solve the problem offline first. Let's sort these modifies queries (which are of type (left, right) -> count the number of distinct user_ids in the [left, right] substring) by the right index, increasingly. We can process them like this:

Cod:

j = 0
for i in range(0, q):
  while (j <= query[i].right):
    if (last_position[value[j]] != -1):
      BIT.add(last_position[value[j]], -1)
    BIT.add(j, 1)
    last_position[value[j]] = j
    j = j + 1
  answer[query[i].original_index] = BIT.query(query[i].right) - BIT.query(query[i].left - 1)

Suppose value contains the normalized user_id's in their initial order and BIT is a binary indexed tree. Time complexity is O((Q + N) * log(N)).

We can improve this idea to handle online queries. The idea is really similar. Suppose segTree is a persistent segmented tree, which handles set update on position and query on interval.

Cod:

for i in range(0, n):
  if (last_position[value[i]] != -1):
    segTree[i] = segTree[i - 1].update(last_position[value[i]], 0)
  else:
    segTree[i] = segTree[i - 1]
  last_position[value[i]] = i
  segTree[i] = segTree[i].update(i, 1) 

for i in range(0, q):
  print segTree[map(query_right)].sumOfRange(map(query_left), map(query_right))

At every update O(log(N)) nodes are updated, so the space complexity is O(N * log(N)), but the time complexity is the same as in the offline solution.

Salut,

Eu sunt de parere ca toate problemele ar trebui sa fie open-source. Cred ca mai multa lume are de beneficiat din aceasta schimbare. Multa lume cred ca are de invatat ceva nou, chiar si dupa ce ia punctaj maxim la o problema. Mie personal imi place foarte mult sa ma uit la solutiile celorlalti si consider ca am avut de castigat din asta: am invatat sa citesc codul sursa al altora, am invatat reguli de indentare de la sursele care mi s-au parut cele mai citete si am intalnit idei diferite de ale mele, de la care am pornit in rezolvarea altora probleme. Recomand si celorlalti acest exercitiu, desi cred ca este un obicei comun.

De multe ori m-am aflat in pozitia in care am rezolvat o buna parte de problema, insa nu am avut inspiratie sa o inchei cu succes. In lipsa de idei, ajung la spamez evaluatorul cu bulaneli, strict pentru a afla acea idee de incheiere (care poate sa fie foarte folositoare pe viitor). Niste exemple care imi vin acum in minte: optimizarea memoriei la problema reg (imi facusem prostul obicei de a crede ca felul in care sunt generate numerele este strict pentru a nu face departajare intre o sursa care parseaza si alta care nu), diferenta intre O(N*sqrt(N)*log(N)) si O(N * sqrt(N)) la problema rangemode (idee care poate fi folosita cu succes si la alte probleme, cum ar fi solutia de 70p la problema calafat data la nationala anul trecut), iar mai nou o solutie online draguta  .

Cum a spus si @depevlad, mai nou se apeleaza la surse precum cautarea numelui problemei pe pastebin, github, si nu vad rostul. Daca vreti sa ajutati novicii care poate nu stiu ca defapt pe ei se pacalesc copiind solutii fara sa le inteleaga, puteti face asemenator arhivei "Gym" de pe CodeForces, unde doar utilizatorii cu un nivel ridicat pot sa vada sursele fara a rezolva problema, in Coach mode, insa asta ar presupune sa updatati rating-urile mai des. Tin sa adaug ca arhiva cu principalele probleme este open-source pentru toata lumea, pe langa faptul ca majoritatea problemelor au un editorial destul de bine punctat (dar asta e de inteles, pentru ca este intretinuta de propunator, iar editorialul face parte din pregatirea unui concurs, in urma caruia este platit) pe site-ul mai sus mentionat.

Asadar, incurajez sursele si testele open. Nu este nimic de ascuns pe o platforma educationala. Cei care se pregatesc in marea parte a timpului singuri vor avea mult de castigat. Cei care se pacalesc pe ei copiind surse ca atare voi continua sa o faca asa indiferent de aceasta schimbare.

O seara faina si felicitari ca ati adus in discutie acest aspect!

Aici se dorea o solutie cu complexitate O((M / 4) ^ 3 * N)? 

Aaah, care e mai exact problema ? 

M-am gandit la o dinamica acum cateva zile, care merge bine in medie, dar pe testul acesta e O(N^3), iar azi am consultat sursele oficiale de pe github si ambele iau TLE (cam 60 de secunde cu -O2) pe acest test.

Există vreo restricție în problemă care face ca acest test (arborele linie pentru N și K maxime) să nu fie unul valid?

Edit: se pare ca se incadreaza in timp cu memoizare 

Ma poate ajuta cineva cu o idee? Am o solutie in O(3 * 10 * MAX_SUMA_CIFRE ^ 3 * NR_CIFRE).

Buna ziua, am o sursa in O(nlogn) care ia 80p cu TLE pe 2 teste. Nu imi pot explica de ce o sursa in care calculez rezultatul, dar nu il afisez, are timpul de executie mult mai mic decat cea in care afisez rezultatul.

LE: Imi imaginez ca toata secventa de calcul a rezultatului a fost optimizata de compilator (pentru ca nu il mai foloseam dupa), dar intrebarea ramane deschisa: ce trebuie sa modific pentru a se incadra in timp?

LLE: Am luat 100 cu mergesort modificat, se descurca mult mai bine decat AIB-urile pentru aceasta problema.

Nu m-am uitat foarte atent in sursa ta, dar iti sugerez sa compari numerele reale folosind epsilon.

[nu]

Infoarena foloseste compilatorul G++ care nu suporta %I64d.

Da, altfel ar fi cam inutil... ca si ratingul 

Normal, am intrebat pentru ca am trimis o sursa la problema ccount care sa foloseasca mai putina memorie si sa modifice clasamentul, dar nu s-a intamplat asa.

+1 pentru submit cu copy paste si link aferent sursei in clasament. O intrebare, statisticile la o problema se reimprospateaza dupa fiecare solutie de 100p trimisa?