http://www.infoarena.ro/blog/cups-and-marbles

Dan, I was thinking of the same idea. Use eratosthenes sieve and each time I run out of prime numbers, double the array and run the sieve again.

Tomek has a solution that is not amortized which does log n log log n work for each number.

Neat, I was thinking about amortized . But I guess one can do it as fast and not amortized .

Is it amortized?

Yes

http://www.infoarena.ro/blog/primegenerator

Good job Lucian. That's the step I was waiting for!

C++ has

— Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

as a builtin function. Some processors also have it as a built in function so the algorithm now has O(1) time per query/update.

@Szilard Yes it can. Good comment. I'll update the question.
@Dan Pretty good! That's the idea, but you can make that binary search step a bit more efficient. Also you meant log 32 not log log 32 right?

http://www.infoarena.ro/blog/resourcehog

Doua alte interviuri cu mai multe intrebari legate de Spark

http://softwareengineeringdaily.com/2015/08/03/apache-spark-creator-matei-zaharia-interview/

https://www.reddit.com/r/IAmA/comments/31bkue/im_matei_zaharia_creator_of_spark_and_cto_at/

Si cateva sfaturi pentru concursuri de programare
http://people.csail.mit.edu/matei/programming_contests/

http://www.infoarena.ro/blog/matei-zaharia

http://www.infoarena.ro/blog/balance

http://www.infoarena.ro/blog/hill-climbing-shortlist

1. O(n) remains unsolved.
2. O(n log k) solved.
3. O(n log k) solved.
4. Solved in O(n log k) and O(k). One can actually solve it in O(n) time and O(k) additional space: http://www.infoarena.ro/blog/problema-saptamanii-stream-solutie
5. See 9.
6. Solved in O(k log k). One can actually solve it in O(k) (http://www.sciencedirect.com/science/article/pii/S0890540183710308)
7. O(n) solved.
8. Solved.
9. Solved in O(k log k) but one can solve it in O(k) (http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf)
10. Remains unsolved. An O(k) solution is fine.

Good job so far.

http://www.infoarena.ro/blog/heaps-shortlist

http://www.infoarena.ro/blog/how-to-get-promoted

The first solution is a good attempt, but sigma can be big and you can improve on that.

I didn't understand much in your second solution. (right isn't defined)

http://www.infoarena.ro/blog/snippet

Alex, the two problems are equivalent.

If A is the array of numbers in the min = a[ i] problem, then reverse(A) is the set of speeds in the car problem (if cars are going from left to right and A[0] is the last car).

On your example A = N .. 1 - n updates, reverse A = 1 .. N - n clusters

BTW 2 sqrt(n) is the average length of the LONGEST increasing subsequence, while here it's not the longest one.

Alex, no, it's not 2 sqrt n

@Radu I should put the puzzles when Boston sleeps and Romania is up so it's not solved as quickly .

http://www.infoarena.ro/blog/cars

http://www.infoarena.ro/blog/talentbuddy

Ciao,
  imi pare rau pentru disconfortul cauzat. Sper ca poti edita si sterge numele.

Poti sa ii adaugi daca sunt interni anul asta.