10529 - Dumb Bones

[Observer]

According to the problem description,
"For each case, output the expected number of dominos that will need to be placed before you finish, accurate to two digits after the decimal. "
1. Why is the "number of dominoes" a decimal?
2. What is meant by "before you finish"?
3. How come the "expected number of dominoes" is even greater than n, the number of dominos to place?

Plz explain to me!!! Thx in advance.



P.S. What is the "optimal placement strategy" anyway?

[Observer]

Ah...

So that means if some dominoes are knocked down, you have to put them up again. Thus the "expected number of dominos" can be greater than n.

But why is the last sample output 20.00? Does that mean that "placed" dominoes can also knock down adjacent ones?

[Whinii F.]

I'll try to explain the last test case.

In this test case there are no possibility you will eventually knock down a domino to it's left side. So, it will be the best strategy to place the dominoes from left to right.
That is, if you place the dominoes from right to left, one eventual knockover will make all dominoes collapsed (so you will have to place all of them again). But when placing them from left to right one eventual knowover will cause only one domino to be placed again. (Of course in other cases it will be not this easy to determine the strategy)

So there are possibilities we have to place this single domino,
1.0 + 0.5 + (0.5 ^ 2) + (0.5 ^ 3) + ....

The first 1.0 means we have to place it AT LEAST ONCE.

So the summation of this infinite geometrical series is 2, and the expected cost for this single domino is 2. Therefore we have 2.0 * 10 = 20.00.

I think this explains all of your questions.

Anyway I've been wondering about this problem for a few days but could only figure out the outline....

Any helps would be appreciated!!

Thanks in advance,

[Whinii F.]

solved @ last
This problem is very interesting !!

[Larry]

I solved it using the slow DP way. I wonder what ChrisH use for such a fast solution.

[ChristopherH]

The O(N^2) DP way is fine given the limit N <= 1000 as specified. During the actual Waterloo contest I solved it that way, as I imagine everybody who competed at UVA did.

It's (mathematically) interesting to look at the continuous version of this problem (taking the limit as N goes to infinity). Unfortunately, the discrete version doesn't seem to have a closed-form (ie. O(1)) solution.

There is, however, an O(N) solution. Do some investigation and think about the properties of the function you are minimizing.

[huksy]

i still dont understand how to calculate the probability.

_DxD_

whats the probability of that if you try placing a dom at 'x', when pl=0.1, pr=0.4 ?? and how..

id really appreciate your reply..


i feel so depressed when i cant get through the meaning of the problem..

[ChristopherH]

If you have a situation A_B and you attempt to place a domino into the gap, then the following things may occur:

* with probability Pl, the placed domino will fall left, taking out not only itself but the entire group A
* with probability Pr, the placed domino will fall right, taking out not only itself but the entire group B
* with probability 1 - Pl - Pr, the placed domino will stand, and so will A and B

The term 'expected' is used here in it's technical probability theory sense. The expected value of some discrete random variable X is the sum {over all possible values of X } of P(X == x) * x.

In other words, you have some strategy for placing dominoes, which may be contingent on which dominoes fall (it's like a potentially infinite game tree, for a game played between you and 'nature' which makes random moves). The expected number of dominoes you need to place is the sum { over all the leaves (successful completion of an N-domino block) of your strategy } (distance to leaf * probability of path to leaf).

There are lots of introductions to basic probability theory on the net or in textbooks.

[marian]

Are there any probability theorems that could be directly applied here? I have solved this problem, but I wonder whether it could be solved more elegantly. My approach is as follows:

I compute expected value for n=1. This is infinite sum (1+2(Pl+Pr)+3(Pl+Pr)^2+4(Pl+Pr)^3+...) which is not difficult to compute.

Then I compute expected value for n>1 assuming I have expected values for every lower n. I try to put n-th domino between two blocks of length l and r (r=n-l-1). (For every l) Expected value for such situation is: (1-(Pl+Pr))*((1+E[l]+E[r])+Pl*(2+2E[l]+E[r])+Pr*(2+2E[r]+E[l])+Pl*Pl*(3+3E[l]+E[r])+
Pl*Pr*(3+2E[l]+2E[r])+Pr*Pl*(3+2E[l]+2E[r])+Pr*Pr(3+E[l]+3E[r])+Pl*Pl*Pl(4+4E[l]+E[r])+....
Where E[l] and E[r] are expected values for n=l and n=r, respectively.

So I had to manually (on paper) compute that two infinite sums.

Is there an easier way compute that?

PS: My probability knowledge (and math in general ) is quite poor, so I'm sorry if I'm absolutely missing the point.

[Maarten]

this is a difficult problem for me; I'm surprised 70% solved it correctly. Normally this high percentage means it is an easy problem!

I haven't quite figured out how to calculate the expected number of dominoes to be played given a strategy; but I think the optimal strategy is to always put a domino on the left or on the right, depending on which of P_l and P_r is smaller. (I'm probably wrong here but it's worth a try isn't it?)

[Maarten]

sorry for posting twice... how can i remove this post ?

[Sajid]

this is a difficult problem for me; I'm surprised 70% solved it correctly. Normally this high percentage means it is an easy problem!

All the time, percentage of Accepted Solutions is not the correct way to consider a problem's difficulty level. Bcoz, there is only 207 total submissions. Hence, the problem is not so easy as you think.

[Maarten]

I solved the problem.. but I'm still wondering how I can do faster. My current program runs in 2.578 seconds. The problem is indeed very interesting!

[..]

Could anyone get AC give me a help?

For this problem, I get the following recursive formula:


I have checked the official solution, they use a much simpler formula in the form like

(As I don't want to post the answer direclty, I use f_x to represent the coefficient.)

I am very very cursios to know, is there anyway to derive the simple formula directly instead of simplifying the complicate fomula. As it is extrmely painful to simplify my complicate formula to the simple form.

[polluel]

if somebody needs this:
for |x|<1 :
1/(1-x) = 1 +x +x^2 +x^3 + x^4+...