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

×

# Editorial of Guess it Right and Manhattan Rectangle Feb long challenge

 0 1 Consider the two cases for understanding basic pattern in this problem.The first case is that chef has 5 moves and have N = 10 and k = 10 which means he has 15 boxes in front of him and 10 boxes will be added after every choice now chef is making moves. For describing the chefs move I will use 0 if he chooses any box and 1 if he is removing xk boxes where xk

 0 Hi @faizan2700 what do you mean by excluding the first in some cases in Guess It Right explanation? We know that N < K for all test cases. It's a given constraint and on the last move we will definitely have to choose a box. Also can you explain in detail how GP sum comes into play? answered 14 Feb, 02:28 1●1 accept rate: 0%
 0 hi all here is a solution given by rajput1999 answered 14 Feb, 18:00 30●4 accept rate: 9%
 0 u r ossom answered 14 Feb, 19:28 3★pool123 1 accept rate: 0%
 0 the optimal string is 1010101010 to maximize the probability because if he chooses any other move pattern he will end up increasing the number of boxes or the denominator so much that the probability will decrease drastically. But can you prove it? I solved the problem after convincing myself with some experiments but I couldn't prove the optimality of the moves. answered 15 Feb, 20:44 167●6 accept rate: 25% Its easy. Take a page and frame the equations. I proved that its not optimal to make $2$ or more random guesses in a row if $K+N >2*N$ which roughly translates to $K>N$. The maths required is simple equation framing, inequalities and perhaps quadratic depending on what result you want. Give it a try, if still not clear, ping someone. (15 Feb, 21:56) If you mean as in the editorial, I don't think the proof is complete as it doesn't consider the "tail probabilities" and I don't think applying induction is so straightforward. (19 Feb, 16:01) Basically, if the probability of removing boxes and then taking a guess is greater than or equal to probability of applying $2$ guesses in a row, I removed boxes. This led to condition of $N>K$. I dont understand the "tail" probabilities, but we can see that after removing boxes, the other probabilities will only increase and not decrease w.r.t. making $2$ guesses a row. (19 Feb, 16:54) I get the general proof strategy. My issue is that when you guess you add very little probability but, at the same time, you make very probable to guess wrong and to take the "tail probability" with one move less. Call $p(N + K, M)$ the prob with $N+K$ boxes. With two guesses this becomes $1/(N+K) + ((N+K-1)/(N+K)) * (1/(N+2K) + ((N+2K-1)/(N+2K)) * p(N+3K, M-2)))$. With one remove and one guess this becomes $1/N + ((N-1)/N) * p(N+K, M-2)$. You want to prove the second is greater than the first. The editorial addresses the main part of the inequality but not the "tail+multipliers" part imho. (19 Feb, 20:02)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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
×1,424
×477
×189

question asked: 13 Feb, 16:18

question was seen: 1,171 times

last updated: 19 Feb, 20:04