## 10529 - Dumb Bones

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### 10529 - Dumb Bones

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?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### Ah~

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?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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,
JongMan @ Yonsei

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
solved @ last
This problem is very interesting !!
JongMan @ Yonsei

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I solved it using the slow DP way. I wonder what ChrisH use for such a fast solution.

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

### dem speedy bones

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
New poster
Posts: 3
Joined: Sun Jul 13, 2003 7:00 pm

### kinda question..

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
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada
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
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
sorry for posting twice... how can i remove this post ?
Last edited by Maarten on Sat Nov 01, 2003 1:26 pm, edited 1 time in total.

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:
Maarten wrote: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.
Sajid Online: www.sajidonline.com

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
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!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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.
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

polluel
New poster
Posts: 6
Joined: Tue Feb 28, 2006 4:20 pm
if somebody needs this:
for |x|<1 :
1/(1-x) = 1 +x +x^2 +x^3 + x^4+...