Awesome problem!

For each entry at time t we calculate Prev[t] = previous position of the user at that timestamp t (easy to calculate by maintaining a hash table). For first-time elements Prev[t] = -1.

Now the number of distinct users between [start, end] is equal to the number of values with start <= t <= end and Prev[t] < start. This is a 2d range query if every point is (t, Prev[t]). We can use any data structure for 2d queries like range trees (w/fractional cascading) which can do it on O(N log N) space and O(log N) per query.

I don't know if by "online" you mean that we can get queries intermingled with more log lines, if so since points we are adding are always to the right, we only need to update the right-most branch in the range tree (O(log N) nodes). Without fractional cascading we can just maintain a BST in each range tree node and that makes the update and query time O(log^2 N). It may possible to maintain fractional cascading information for O(log N) time but it must be tedious.

Alex's interpretation is an interesting variant. If we want to only count clusters of 2+ cars:

a(N) = sum(i = 2 to N) (1/N * (1 + a(N-i)))

The difference is the missing a(N-1) term for i=1: if the first car is the minimum, no cluster will form.

This comes out to a(N) = 1/N [ 1 + a(N-2) + (N-1)a(N-1) ]
which makes sense: if the second car is the slowest (prob 1/N), it will form a cluster with the first car so the answer is (1 + a(N-2)), otherwise (prob (N-1)/N) we can ignore the first car (it will either be alone, or it will be part of the same cluster with the second car), so just a(N-1).

First cluster happens at the minimum speed value, and for the cars ahead of that we have a similar smaller problem. Say a(N) is the expected number of clusters for N cars. For each car i, the probability that the i'th car is the slowest is 1/N. So
a(N) = sum(i=1 to N) 1/N * (1 + a(N-i))

By looking at Na(N) - (N-1)a(N-1) we get a(N) = 1/N + a(N-1) = sum(i=1 to N) 1/i

We could have also derived that directly by just looking at the first car: the probability that the first car is the minimum is 1/N, if it is it will form a cluster; if it is not this car won't matter. So a(N) = 1/N * (1 + a(N-1)) + (1 - 1/N) * a(N-1) = 1/N + a(N-1).

This is pretty much equivalent to the question of how many times you update the minimum so far when going through a random permutation, going from the first car to the last: each time you find a new minimum, that will be a separate cluster.

When you are interested in guaranteeing relative error, doesn't it make more sense to use the geometric mean as the midpoint, i.e. sqrt(low*high) ?   (equivalent to "regular" binary search of ln(x))

punem originea in A1 astfel incat A1=(0,0,0)  B1=(1,0,0)  D2=(0,1,1)
A1D2 are ecuatia parametrica v = (0,t,t)        (pentru orice t de la 0 la 1)
A2B1 are ecuatia parametrica w = (s,1-s,0)    (pentru orice s de la 0 la 1)

distanta intre doua puncte date de un s si t e: d^2 = s^2 + (1-s-t)^2 + t^2.  Ca sa gasim minimul functiei din dreapta, derivatele partiale trebuie sa fie 0.
Si anume 2s-2(1-s-t) = 0 si 2t-2(1-s-t) = 0.  Rezolvam si da un minim la s=t=1/3 cu distanta sqrt(3)/3.

Sper ca exista un mod care necesita mai putina analiza haha

2:
Thread 1 reads value 0
Thread 2 does 9 iterations, thread 3-5 all their 10 iterations (the ordering doesn't matter)
Thread 1 writes value 1
Thread 2 reads value 1
Thread 1 reads and writes etc until it completes all its iterations
Thread 2 writes value 2

Basically what t3st said, he was just missing "thread 1 completes the rest of the iterations" before thread 2 does the final write.

Nu, tot gresita. Cel putin aici: "|R(i)|=r(1)+..+r(N)=N^(N-1)" nu e adevarat, sunt doar N^(N-2) w-uri posibile si multimile r(1)..r(n) formeaza o partitie. Also, fiecare element din r(i) corespunde a N vectori in care jucatorul 1 raspunde corect, deci sunt N^(N-1)/N = N^(N-2) elemente.

Am eu o demonstratie clara si corecta care incepe ca a ta da o scriu intuitiv de la inceput:

------

Fiecarei configuratii pe care un jucator dat i raspunde corect ii corespund alte N-1 configuratii pe care raspunde incorect (pentru cele N-1 alte valori pt jucatorul respectiv). Daca ne gandim un pic, e clar ca multimile astea sunt disjuncte, deci un jucator raspunde corect pe maxim 1/N din numarul total de configuratii. Deci ca sa fie toate "acoperite", in fiecare configuratie exact un jucator trebuie sa raspunda corect. [asta e prima jumate din demonstratiile lui digulescu, spus fara --verbose]

Acum construiesc o configuratie pe care juc 1 si 2 ghicesc corect: iau o configuratie oarecare pentru jucatorii 3,..N, sa zicem toti 1. Notam cu x ce ghiceste juc 1 cand vede toti jucatorii 3..N cu valoarea 1. Notam cu y ce ghiceste juc 2 cand vede ca juc 1 are x si juc 3..N au 1. Configuratia x y 1 1 1 .. 1   este ghicita corect de ambii jucatori. QED

------

Mircea, in notatia ta, eu doar construiesc configuratia F1(w)  F2(F1(w) w)  w.  Cheia constructiei e jucatorul 2, pentru ca el vede tot ce vede si jucatorul 1, plus valoarea lui 1.

Ca sa nu va obositi, nici demonstratia asta nici cea precedenta a lui Digu nu e corecta IMO (pana si autorul lor e de acord ca sunt cel putin incomplete).

Adapting silviu's solution for the unknown initial switch state: each prisoner (except the designated) turns the switch on-to-off the first _two_ times they see it "on". The designated prisoner waits until she has counted 2(P-1)-1 on-to-off transitions and then declares everyone has been in the room. The idea is that if the switch is on in the beginning, whoever goes in first will turn it off, and we have "lost" one in the count. But that's ok, since 2P-3 counts are (in all cases) sufficient for us to know for sure all other P-1 prisoners were in the room at least once.

Nu, ai 124 de carti diferite. Cu alte cuvinte, primul jucator primeste 5 numere distincte intre 1 si 124, iar al doilea jucator trebuie sa ghiceasca al 5-lea numar vazand 4 dintre ele intr-o anumita ordine. (Si in toate astea de 3 lucruri tine cont, 2 platane si 1 microfon.)

Apropo, combinari de 124 luate cate 5 este exact egal cu aranjamente de 124 luate cate 4. Asta inseamna (pe langa ca 124 e cel mai mare nr pentru care problema asta e posibil sa aiba solutie), nu poate fi nimic redundant in codificare, si toate aranjamentele aratate trebuie sa fie "valide". De ex. in solutia mea cand 3+ carti au aceeasi culoare, nu toate valorile intre 1 si 6 sunt valide; insa, pentru varianta cu 124 de carti, orice aranjament trebuie sa fie cuplat cu exact o combinare (o bijectie).

Se poate in teorie scrie un program care sa determine un cuplaj complet intre cele 225M aranjamente si combinari, si asta ar gasi o solutie la problema (atata timp cat exista o solutie). But that would be cheating haha

Eu am asta in .bashrc:

bind '"\e[A":history-search-backward' 2>/dev/null
bind '"\e[B":history-search-forward' 2>/dev/null

Face ca sageata sus si jos sa caute intre comenzile care incep cu ce litere ai scris pana acum (ca in matlab). Iti schimba viata haha

Da, e mai usor asa. Cu alte cuvinte alegi diferenta mai mica modulo 13 (ori y-x<=6 ori 13-y+x <= 6).

Mama ba ce intrebari/idei puteti sa aveti. Evident ca nu poti sa te uiti in pachetul de carti, care ar mai fi problema? Nu, nu poti sa folosesti felul cum asezi cartile (unghiuri, spatii, orientari), nu poti sa ii faci cu ochiu in timp ce le arati, si nici nu poti sa ii trimiti un SMS. Singura informatie pe care o transmiti sunt cele 4 carti in ordine.

Frumoasa problema. Cred ca am o solutie.

Sa zicem ca setam o ordine globala pentru carti si putem sa ne referim la ele ca numere de la 1 la 52.

Impartim cele 52 de numere in 4 "binuri" de cate 13 carti. Din cele 5 carti primite vor fi neaparat cel putin 2 carti in acelasi bin.

Alegem o astfel de pereche de carti. Una din aceste carti va fi a 5-a carte ascunsa, iar cealalta carte va fi prima carte aratata din cele 4 (deci al doilea jucator va sti imediat binul cartii ascunse). Celelalte 3 carti aratate vor fi folosite pentru a "transmite" un numar intre 1 si 6 (a cata permutare din cele 6 posibile, ca si ordine relativa).

Cele doua carti fac parte din acelasi bin. Sa numerotam cartile din binul respectiv de la 1 la 13 in ordine crescatoare, si sa zicem ca cele doua carti au valorile x si y intre 1 si 13, cu x < y. Putem alege care din x sau y va fi aratata. Alegem asa: daca diferenta (y-x) e para, aratam cartea cea mare (y); altfel o aratam pe cea mica (x). Sa ne gandim ce inseamna asta pentru al doilea jucator, care vede prima carte cu valoare sa zicem z. El stie ca cealalta carte ori e mai mica si diferenta e para (deci z-2, z-4, etc) ori e mai mare si diferenta e impara (deci z+1, z+3, etc). Daca z e par, sunt (z-2)/2+(14-z)/2 = 6 posibilitati. Daca z e impar sunt (z-1)/2+(13-z)/2=6 posibilitati. Deci in toate cazurile, dandu-se prima carte aratata, sunt exact 6 carti posibile, si celelate 3 carti aratate pot indica valoarea necesara intre 1 si 6.


Edit: m-am grabit sa absractizez haha, in loc de "binuri" putem sa ne gandim la culori (deci prima carte aratata are aceeasi culoare cu a 5-a carte; apoi determinam numarul cum am spus)

La marimea arrayurilor: un bug specific un pic mai subtil a fost la dimensionarea arrayului pentru arbori de intervale: l-am facut 2*N, dar trebuia sa fie 2*<o putere de 2 cel putin N>. (N era 100000 si trebuia dimensiunea > 262144, eu am pus 200002).

@cristi8, da, deci in cazul cu 1/2 si 1 demonstratia nu e suficienta pentru a alege unul din aceste rezultate. stim doar ca e unul din ele. trebuie demonstrat altfel ca X < 1 (practic asta nu e demonstrat de recurenta ta).

cristi8, cred ca ai dreptate.

Matei Tene, tu aici gresesti:
= P (furnica incepe de la 2 si ajunge prima data la 0 in i-1 pasi)
= P (furnica incepe de la 2 si ajunge prima data la 1 in i-1 pasi, iar apoi urmeaza un pas -1)

In primul rand ai vrut sa zici i-2 pasi in linia 2 (nu conteaza asta, ar da la fel), dar nu este corect: poate furnica ajunge prima data la 1 mai repede (in j < i-2) pasi, apoi dupa inca i-2-j pasi ajunge iar la 1, apoi urmeaza un pas -1.

cristi8,

daca X e "probabilitatea sa fi ajuns cel putin odata pe pozitia 1, fiind la inceput pe pozitia 2", asta include drumuri care ajung la 1 apoi pleaca iar inspre 2 si se intorc la 1

dar tu cand faci X * X "numeri" drumurile astea de doua ori; adica daca X deja include posibilitatile in care ai fost in 1 si ai plecat inapoi in 2 si ai venit iar in 1, deci de ce mai inmultesti cu X, in loc de doar 1/3 (ar fi X = 1/3 + 2/3*X*1/3 = 3/7).

alta chestie e, "probabilitatea sa fi ajuns cel putin odata pe pozitia 1, fiind la inceput pe pozitia 2" include drumuri care ajung si in pozitia 0? Daca da, si drumrule astea sunt numarate de mai multe ori..

Nu prea inteleg care e treaba cu optimizarea. Se poate sa iti iei teapa si sa te uiti la O(N) drumuri si numai primul drum sa fie folositor. Ceea ce ar lua O(N^2) in loc de O(M) pentru fiecare BF.


Un exemplu limitat ar fi un graf  1->2->3->.. -> N-1 si muchii de la 2->N, 3->N etc. Si sa zicem ca muchia 1->2 are capacitate 1 si restu muchiilor au capacitate mai mare.

Daca faci fara optimizare faci un BF, gasesti un drum si gata, ceea ce e O(N). Daca faci cu optimizarea, o sa incerci toate drumurile (care se termina in 2->N, in 3->N, in 4->N, etc.) si e degeaba ca oricum dupa primul drum nu o sa mai gasesti nimic - si asta ar lua O(N^2).

Stiu ca oricum nu prea conteaza ca e fluxul 1 da sunt sigur ca s-ar gasi exemple similare mai dramatice (in care s-ar gasi alte drumuri dar chiar esti nevoit sa faci un BF nou de fiecare data).

Dpdv teoretic nu cred ca se poate demonstra ca optimizarea reduce numarul de BF-uri in toate cazurile.. Deci complexitatea teoretica creste la O(N^3*M) in loc de O(N*M^2)..

Poate nu inteleg eu ceva..

Nice, foarte misto solutia

Haha, m-am gandit ceva la aia Cosmin.

Imi e destul de clar ca daca ai doua perechi de drumuri poti sa le modifici astfel incat drumul pentru primu robot sa coincida cu drumul pentru primul mobil si care inca sa aiba proprietatile date. Si atunci e clar ca la un moment dat al doilea mobil se va intalni cu al doilea robot daca iti imaginezi drumurile in acelasi timp, ceea ce e contradictie.

Cam singura problema e cand drumu mobilului o ia in cealalta directie fata de drumul robotului, caz in care fie perechea de mobile, fie perechea de roboti o ia inapoi. Da pare foarte greu de formalizat.

Sunt sigur ca e o idee mai usoara care imi scapa, sunt curios sa o aud daca o stii.

hai sa luam g(x) = integrala de f de la x la x + 5 minute. adica distanta parcursa in cele 5 minute dintre x si x+5
stim ca g(0) + g(5) = 1000 si g(x) e continua
fie g(0) = g(5) = 500 caz in care e clar deja
sau g(0) < 500 < g(5) ori g(5) < 500 < g(0) caz in care trebuie sa fie un y intre 0 si 5 cu g(y)=500 pt ca g e continua

f nici nu trebuie sa fie continua; g va fi continua chiar daca f nu e.

Inca o idee: in loc sa folosim cate un numar pentru cele <max> valori, putem folosi grupuri de numere.
De exemplu, daca stim ca U > 2N, putem sa folosim cate doua numere:

Atunci de exemplu uvec[0] si uvec[1] au cate un bit rezervat sa arate daca 0 respectiv 1 sunt in multime (sa zicem semnele), si apoi raman 2logU-2 biti pe care putem sa-i folosim ca primul numar din "lista" noastra. Deci

Cod:

extra_storage(i) = abs(uvec[2*i]) * U + abs(uvec[2*i+1])

test(i) = DA daca:
* i < 2*max si uvec[i] < 0
* i >= 2*max si 0 <= uvec[i] < max si extra_storage(uvec[i]) = i

inserare(i):
daca i < 2*max, uvec[i] = -abs(uvec[i])
daca i >= 2*max:
* flag1 = test(2*max)
* flag2 = test(2*max+1)
* uvec[2*max] = i / U
* uvec[2*max+1] = i % U
* daca flag1 sau (i == 2*max) atunci u[2*max] = - u[2*max]
* daca flag2 sau (i == 2*max+1) atunci u[2*max+1] = -u[2*max+1]

Deci atata timp cat 2N < U, ne ajung numere de max(logN, logU/2+1) biti.

Fie ca iti "place" sau nu, in practica marimea numerelor nu e o problema cand e vorba de un singur bit in plus (de exemplu daca avem U numere pe 32 de biti, va fi mai mult decat suficient in aproape orice situatie).

Cand expui un contraexemplu, spune exact ce nu iti da bine, si eventual problema algoritmului pe care crezi ca ai gasit-o.

Eu unul nu vad problema. Presupunerile pe care le-ai facut sunt corecte. Dupa insertii vom avea
max = 3
uvec[0] = 2, uvec[1] = 3, uvec[2] = -4
uvec[3] = 1, uvec[4] = 2

test 3: 3 >= max si uvec[3] = 1, abs(uvec[1]) = 3 deci DA
test 4: 4 >= max si uvec[4] = 2, abs(uvec[2]) = 4 deci DA
test 2: 2 < max si uvec[2] este negativ, deci DA

A, scuze, problema e ca nu are voie sa fie amortizat. Interesant..

Am putea in loc sa folosim memorie suplimentara, sa folosim tot memoria in care incap U intregi.

Presupunem ca intregii din uvec sunt destul de mari, sa zicem cel putin max[log(2N)+1, log(U)+1] biti, deci pot tine numere de la -2N la +2N sau de la -U la U.

Tinem max ca la solutia initiala.

Intregul i e in multime daca:

Cod:

* i < max si uvec[i] este negativ
sau
* i >= max si 0 <= uvec[i] < max si abs(uvec[uvec[i]]) = i

Deci ideea e ca folosim primii max intregi ca storage, si mai folosim un bit (semnul negativ) pentru numerele din zona asta.

Inserare:

Cod:

* daca i < max:  uvec[i] = -abs(uvec[i])
* daca i >= max:
   - flag = contains(max)    // verificarea de mai sus, O(1)
   - uvec[max] = i; uvec[i] = max;
   - daca flag sau (i == max): uvec[max] = - uvec[max]
   - max = max +1