infoarena

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

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.

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

Alex, no, it's not 2 sqrt n

"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."

That was my first ideea too but it's not corect.
If you want to create a cluster, the new minimum should be at a distanve of at leaste 1
For example N .. 1
N updates but 0 clusters.

In this case the answer would've been 2sqrt
Because it's the expected value of "increasing sebsequene"

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.

I thought that a cluster if formed when 2 or more cars are stuck together  :'(
Sorry.

Indeed, I got to the same result.
First car has a probability of 1 to be the head of a cluster.
The second car has a probability of 1/2 to be the head of a cluster. It's a head of a cluster only if it's smaller then car 1.
The third car has a probability of 1/3 to be the head of a cluster. It's a head of a cluster only if it's smaller then car 1 and car 2.
...
so the result is 1+1/2+1/3+...1/N, since all clusters need heads (they are not zombies, are they).

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).

The problem’s been solved, but I’d like to post some insight into how you can do a Fermi-type estimation here:

The slowest car will block all other cars behind it, so about half of the cars are probably stuck in the biggest cluster. Since picking the largest cluster at each step removes a percentage of the total amount of cars (the percentage doesn't even matter), the answer is in the order of O(logN), which is ok to use as a rough approximation when the real answer is ~lnN (the value of the sum equals this when N is infinite).

Of course it’s always better to do the math, since it's just intuition that can be wrong, but this type of analysis is useful when it’s impractical to do the math or you just want a gut feeling if something is possible. If for instance you're removing chunks of something in the order of sqrt(N) cars at a time, then you'd be done in O(sqrt(N)) iterations, which was the case in Alex's assumption.

Let vmax the maximum posible car speed, v(1), v(2), ..., v(N) the car speeds and p(N,k)=probability that k is the number of clusters. Than we have:

p(N,k)=v(N)/vmax*p(N-1,k-1)+(1-v(N)/vmax)*p(N-1,k)

I guess i was wrong . Sorry !