pe testul din enunt
"Al doilea băiat este de acord cu orice fată" .

Nu doar cu fetele care au frumusetea <=3 ? gen cu a 4-a nu ar vrea sa se cupleze ?

My idea is a combination between the way STL <vector> is built  and the  Erathostene sieve ideea

Lets consider the all numbers in the interval 1..2^32
Lets create 32 bins in the following manner:
The bin with index i holds the values  1..2^i   .( example: bin number 16 holds the values 1,2,3...2^16)


Lets  define the folowing method :

vector<int> Erathostenes (Max_Value)
{
   ..../// here it finds all the primes in the interval 1..Max_Value using the Erathostenes sieve
   .../// it returns a <vector> int with all the primes in the interval 1..Max_Value
}

as we get a new query , we might "move" into a new bin (ie: a bin with a bigger index) (indexes range from 1 to 32)
each time we move in a new bin we refresh our prime list callling the above method

The amortized running time is NlogN.
The worst case is also NlogN , because when we first get into a new bin we do NlogN operations
but all the other numbers that don't belong to the begining of a bin are accesed in constant time

is extra memory allowed?

ce se intelege prin disjuncte? disjuncte ca si string ? sau ca si pozitii?

gen ababa

pozitile 1-3 si 3-5 sunt ok (adica coincid) ??

nice task ! , here is my ideea:

keep (32) or (64)  maps , (ie: map< pair<string,int> > bin[32] , lets call this "bins"

now we map each integer X to the closest bin with index i , such that 2^i <=X
ex: 35 gets mapped to bin[5] because 2^5<=32 . so we do bin[5].push_back(X);

case 1: How we handle an update  , lets say we add 1 new user , now we need to binary search its matching "bin" , but the binary search is on values 0..32 so log(32)~loglog(X)~5-6 operations

case 2: when we update an already present user , we search its "bin" position using the above binary search, we remove it in O(1) since removal from a Map is O(1) using Hashes, then we re-insert it like in the case 1

 NOTE : each time we do an update , we keep for each "bin" a bit which is 0 if the bin is empty or 1 if the bin is occupied by atleast 1 user
 We can store all the values of the bits as a 32 bit integer (as we got a total of 32 bits)
 
 Lets call this integer Q;

case 3: we are facing an query :
 
 what we need to do is to find the bin with the greater index such that its NOT empty
 this relates to finding the least semnificant bit of integer Q  ; lsb(Q)  = (Q ^ (Q-1)) & Q
 so we know the biggest-index "bin" that is not empty , and we can just print any element from it .

 So the query part takes O(1)

 We will be off by a factor of at most 2 because of the way we are mapping the integers.

the complexity is O(log(log(32)))+O(1) ~ is preety close to O(1)

[Editat de moderator]

solutia mea a fost evaluata dar primesc doar 50p pe pretest , asta inseamna ca mai e un pretest sau ca nu am indeplinit decat cerinta

450 - veti primi 50 de puncte

ni ba , daca tot pica inainte de bac algoritmiada r 3 rog propunatorii de probleme sa creeze enunturi care au legatura cu operele de bac
 (enigma otiliei, morometii , floare albastra , plumb , sau ultima noapte ) poate asa o sa trec si eu multumiri .

Oh , yes you dont need the sqrt root trick actualy , i am tired lol

3rd ideea.
Create a List of length T with indices 1...len(T) lets call it V;

sort it using the folowing comparition function pair<T,i> (first we compare by the character and then by the position)

now , when i need "to jump" just like in sol 1 i can binary-search my next position in Vector A;

Time : O(T*P*log(T)) Memory O(T)

Hey,  are 2 of my ideeas, the first one works in T*P time and memory

The second one is slower than the first one , but uses only O(T) memory;

1)

The first ideea is kind of a brute-forces , try to match the string P at every position of T

 the question that arises is :

 i matched X characters of P , and i am at position i now , where is the closest position J such that J>i and P[X+1]=T[J];
 in other words where do i need to "jump" next.

 we can keep a matrix which looks kind of : Next [ T ][ SigmaP ] where is the closest position that i need;
 so that way we can achieve O(T*P) time and memory

2)

  second ideea optimizes the memory but runs slower :
  Again , we try the same thing try to match the string P at every position of T

  How to get rid o matrix Next[][]?

  well first i divide string T into sqrt(n) "chunks"
 
  for each chunk , i create a list of pair<character_at_position,position> and sort the list;
 
  now i can make the folowing query on a chunk , does character C exist in the chunk? if so where is the smallest index that i need (the one that is higher than the character i just mathed)

   this can be done by a binary search
   
The time complexity looks bad  lol , but atleast i improved the memory, i will think of a better ideea later;

e blat

bagati in arhiva probeleme plz

edit: acuma am observat ca erau deja in arhiva  ACM , leam cautat in arhiva de probleme lol)

In cat timp o sa se afiseze rezultatele la varianta online?

o fost dragu problemele chiar daca nu mam prins de iele , felicitrari comisiei, #FLC

o sa fie disponibil si clasamentul pertotal (cele 2 runde) sau e doar pt inspectori ?

nu pricep enuntul , e in baza 2 sau in 10 pana la urma
 
la testul al doilea la un moment dat am impresia ca se adauga o cifra de 7 si se tipareste , cum pot sa ajunga cele doua multimi egale din moment ce primul sir nu are nici o cifra de 7 ?

101 e periodic? (are perioada 2)

Felicitari !!!! aveti valore multa 

multa valuare sa aveti 

5)  Assign to each element a random key , keep a heap with the biggest K pair<key,value> as we iterate trough the elements.

succesuri 

1) If we toss the coin 1/p times we will get a head. If we toss the coin (1/p)/2 we get 50% chance of getting a head so if we toss it 1/(p*2) times and we dont get a head we consider it a 0 otherwise 1.

Also i dont understand 5) what do you mean by stream of integers ? it means that you dont know how many integers you got and you keep reading them?
like a while (f>>X) ?

and also i dont get what problem 6 ) wants . the expected time?

and at problem 7 . I need to come up with a formula or an algorithm ?

My english is no very good so im sorry if this questions look stupid

Im not used to this type of problems so if my solution look bad im sorry lol ))

2. If we substract 1 from the function result we can get a random number betwen 0 and 4 , if we use the function 6 times ,and we get a and we look at the results as a  6 digits number in Base 5 we get a random number betwen  0 and (5^6-1) .  The number (5^6-1) is divisible by 7 so if we take the remainder of the result dividing by number 7 we get a random number betwen 0 and 6 . If we add 1 here is our answer.

3. Generate a random real number between 0 and 2pi , then generate the a random number betwen 0 and R.(the angle and the distance from the point x,y) from here you can find the point using some math formulas wich i dont know .

4.
Lets substract 1 from every element of the permutation for simplicy we will add 1 at the final result to get our answer.

Generate a random number betwen 0 and (n!-1).  Lets call it X.

There are exactly n! permutations and exactly n! X's so for each number X we can map only one permutation.

One way of finding the first element of the permutation is
  A.1= X/(n-1) ! (integer part of it )

once we found the first elemenent we then substract A.1*(n-1)! from X and we repeat the above step till we find all digits.

what do you mean by "fair" 0 and 1 result??

Intrebarea mea e aceiasi ca a lui radu , putem adauga zerouri in fata numarului Ai???