You are not logged in. Please login at www.codechef.com to post your questions!

×

GUESSRT - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Abdullah Aslam
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Probability, Modular arithmetic and a bit of proof. (Setter says "Proof by intuition").

PROBLEM:

There are initially $N$ indistinguishable boxes, exactly one of them containing one magic pill. You have to find the probability of finding the box containing the magic pill in at least one operation when you can perform operation $M$ times.

In one operation, you can do either one of the following two. - Make a guess. If the chef finds the box, the game is over. Otherwise, $K$ more indistinguishable empty boxes are added every time a guess is made. Let's call it a guess operation. - Remove $i*K$ boxes such that $i \geq 0$ and $i*K \leq X$ where $X$ is the number of boxes present. No guess is made here. Let's call it a remove operation.

Important to notice is that $N < K$.

QUICK EXPLANATION

  • When only one operation is left, it is better to make a guess, increasing the probability of winning.
  • Otherwise, we can always make a remove operation in the current move and guess operation in next move which gives better probability than making two guesses in two moves.
  • To simplify calculating probability, notice that it is easier to calculate the probability of losing and then take its complement.

EXPLANATION

First thing, Let us consider it's the last move. It's obvious that making a guess now is better, than making a remove because making a guess increases your chances of winning. The final number of boxes is useless.

Secondly, At any point during the game, Number of boxes is $X = N+x*K$ for some $x \geq 0$ When performing remove operation, we always choose to remove the maximum number of boxes we can (to maximize win probability), which happens to be $x*K$, leaving $N$ boxes behind. This also implies that if the number of boxes is $N$ before the current move, it makes sense to make a guess, since remove operation cannot remove any box at all. So, strategy maximizing win probability never have two consecutive remove operations.

Remember $K > N$. Let's assume $K = N+d$.

If we have $N$ boxes, it's obvious we make a guess. The number of boxes becomes $2*N+d$.

Now comes the interesting part. Suppose we have more than one move remaining, with $2*N+d$ boxes before the current move, with the second move being a guess move. Now, what is better? The first move to be a guess move or to be a remove operation.

Let's analyze both cases.

In the first case, the Number of boxes before the second move is $N$, winning probability in these two moves is $1/N$.

In the second case, Probability of win = P(win at first move)+P(win at second move) - P(win at both moves). The number of boxes before the second moves is $3*N+2*d$. So, the probability becomes

$\frac{1}{2*N+d} + \frac{1}{3*N+2*d} - \frac{1}{(2*N+d)*(3*N+2*d)} = \frac{5*N+3*d-1}{(2*N+d)*(3*N+2*d)}$. Lets multiply numerator by $N$, we have $\frac{5*N^2+3*d*N-N}{6*N^2+7*d*n+2*d^2}$. It can be seen, that with $N,d \geq 1$, this probability is always less than 1. Dividing both sides with $N$, we have $\frac{5*N+3*d-1}{6*N^2+7*d*N+2*d^2} < \frac{1}{N}$.

Hence, we can see, that it is better to perform a remove operation and then make a guess, rather than making two consecutive guesses when we have $N+K$ boxes available.

So, our final optimal strategy looks like. Make a guess. The number of boxes now is $N+K$. Perform remove and make another guess and so on. But as we noted earlier, the Last move shall always be guessing, which we shall ensure (There is two consecutive guess in the end when $M$ is even).

Now, if $M$ is odd, we are making $(M+1)/2$ guess when at each guess we have $N$ boxes. It shall be complicated to handle inclusion-exclusion here, and the simpler way is to calculate the probability of losing and takes its complement. The probability of losing is just the product of the probability of losing at each turn.

Probability of losing is $\frac{(N-1)^{(M+1)/2}}{N^{(M+1)/2}}$. So, probability of winning become $1-\frac{(N-1)^{(M+1)/2}}{N^{(M+1)/2}}$.

When $M$ is even, we have $M/2$ guesses with $N$ boxes present, and one guess (last one) with $N+K$ boxes. Probability of winning here is $1-\frac{(N+K-1)*(N-1)^{M/2}}{(N+K)*N^{M/2}}$.

Implementation is left as an exercise.

Time Complexity

Time complexity here is $O(log(M))$ per test case due to fast power.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 13 Feb, 23:51

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 16 Feb, 16:55

admin's gravatar image

0★admin ♦♦
19.8k350498541


I couldn't think much for this problem, I don't know why, though I asked some of my friends (after the contest ended) how they solved it. Almost everyone noticed a pattern in the numerator part of the probability, but I couldn't.

I figured out that the denominator will definitely be $N^{\lfloor\frac{(M + 1)}{2}\rfloor}$, but couldn't really find a direct formula for the numerator part, obviously because I was thinking way more than what was needed. But I did figure out what was the "Optimal Move" for this game, at a very early stage of my solution building, that helped me move in the right direction (still it took a lot of time to do it, so silly of me).

So, I started seeing it differently. I found a recurrence relation for the numerator and built a Dynamic Programming solution for this problem (I knew it will fetch me only 40 points). The point I noticed for the formation of my recurrence was this:

For every Guess move, the winning probability becomes:

$\frac{A\times N + B - A}{B \times N}$, where $\frac{A}{B}$ was the winning probability just before this move

Also, for the first Guess move, the probability would be $\frac{1}{N}$

$\therefore$ for every $i^{th}$ Guess move, the numerator can be expressed as a recurrence function $f(i)$ (which I figured out is)

$f(i) = (N - 1) \times f(i - 1) + N^{(i - 1)}$

And the denominator will be $N^{i}$ for every $i^{th}$ Guess move

After solving this recurrence (using the characteristic equation method), I found out that

$f(i) = N^{i} - (N - 1)^i$ (when $N = 1$, winning probability is also $1$)

And for the last move when $M$ is even, I used the formula, $\frac{A\times N + B - A}{B \times N}$ (as mentioned above).

So I solved it directly with this formula, by literally calculating everything on paper and not observing it in front of a screen!
Just wanted to share my approach as it felt very strange to me that even though I didn't notice such an easy pattern, Discrete Mathematics just helped me out. When you don't find a way, mathematics is there for you, now my belief has become even stronger. It felt really good to solve it mathematically.

link

answered 16 Feb, 20:20

ankushkhanna's gravatar image

4★ankushkhanna
254
accept rate: 25%

edited 16 Mar, 14:07

Considering I understood in correctly, I found some errors in the testing. An example should be the test N=21 K=2 M=2. The first move we should make in this scenario is removing 20 boxes, a multiple of 2, from the 21 we have. In the next and last move, there's only one box so the answer is obviously 1. However, I've tested around 20 sources and all of them were doing 2 guesses ( sources marked with 100 points ). My source, which does the right thing has only 1 correct test ( not sure if it doesn't have flaws in other areas ) . Isn't it the answer 1 in the test 21 2 2 ? Am I understanding the problem in the wrong way ?

link

answered 17 Feb, 01:47

neutralove's gravatar image

2★neutralove
1
accept rate: 0%

1

You did not read the question properly. Firstly, $N< K$ always. Next, lets leave it as an exercise :p

(17 Feb, 03:04) vijju123 ♦♦5★
1

Blast! I wasted so much time on this. Thanks for the clarification.

(17 Feb, 04:46) neutralove2★

proof of taking xoxox... if m%2==1 or xoxo.. if m%2==0 and not xxxx

where x stands for operation of type 1 and o stands for operation of type 2

link to proof

link

answered 18 Feb, 23:16

rajput1999's gravatar image

5★rajput1999
3716
accept rate: 0%

edited 18 Feb, 23:18

How do you handle the "tail probability" in the proof? If you take a guess you change the probability for all the following moves. If you just use induction, the math is harder because the 1/N side has a lower multiplier for the tail probability, i.e. (N-1)/N, while the remove-and-guess side has a higher multiplier, i.e. (2N+d-1)/(2N+d). So it is harder to prove in general that the 1/N side is larger.

Has anybody worked out the math?

link

answered 19 Feb, 15:59

gil_vegliach's gravatar image

3★gil_vegliach
1676
accept rate: 25%

edited 19 Feb, 15:59

Any article or blog of probability theory for cp?

link

answered 20 Feb, 23:01

titin_'s gravatar image

3★titin_
133
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,722
×252
×189
×129
×17
×12

question asked: 13 Feb, 23:51

question was seen: 1,364 times

last updated: 16 Mar, 14:07