CHEFYODA solution

general
1

Hello, how to solve CHEFYODA problem of the long challenge?

1 Like
2

use log to minimise large calculations
My solution :- https://www.codechef.com/viewsolution/12839123

4 Likes
3

Nice! I thought of that, but was not so sure about the precision

4

Hint 1:

The probability of winning any game is independent of the other.

Hint 2:

Once, the rule is chosen, the probability of wining the game is either 0 or 1. Why? Let us draw the game tree i.e. all possible moves by which game can be played. So the first player has either a winning strategy at any one of the branch in the starting or none. Hence, the statement.

Hint 3:

Now the overall probability of any game just depends on the rule being chosen. So, the value of the probabilities are 0, 0.5 or 1.

Hint 4:

For finding the probability of wining any game, consider the following cases. (let us call rule 1 as up-down and rule-2 as diagonal). For simplicity, as cell (1,1) is already visited, let us assume Yoda played the 0^{th} move at cell (1,1).

For diagonal rule, if either sides is of odd length, then the other player(Yoda) will make the Chef move only along the boundary of the grid and win the game. When both of the sides is of even length, Chef will win. You can see this by considering only half of the cases (As moves in down matrix can be replicated in upper matrix by reflection). This will reduce the game state to smaller matrix for which you already know the answer. Here, after Chef make the move, Yoda cannot move across only boundaries as it will lose. So now the game is reduced to matrix of smaller size with side length odd. So, Chef will win in diagonal rule if either side is odd.

For up-down rule, Chef only win when either the sides are even length. The Proof was based on some observations with matrices upto 4 X 4 sizes.

Hint 5:

For calculating the final probability i.e. wining p games out of k games, we can use binomial distribution for calculating the final answer i.e Suppose we want to win i games out of n games, then probability is given by {C}_{i}^{n} {(win)}^{i} {(1-win)}^{n-i}.

So for overall answer, we just sum the values from p to k.

Hint 6:

For efficiently calculating this summation, we first use the recursive formula for calculating combinations as

{{C}_{r}}^{n} = \frac{n}{r} {{C}_{r-1}}^{n-1}.

Then we can calculate the {C}_{r}^{n} on the go in O(n). We can reduce the constant factor by half by noticing that

{{C}_{r}}^{n} = {{C}_{n-r}}^{n}.

Hint 7:

Since, these values grow exponentially, and can easily go out of limits for any data type to hold in C++, i used python. But dealing with large numbers also has an issue related with it in terms on constant factors (For example- multiplying 2 n-bit numbers take O(n^2) time.). So to deal with it, whenever the numerator exceeding a particular limit, ({10}^{40}) in my case, I used the values of the denominator, (powers of 2) to bring the number below the required limit. This trick was also used in SEAGM2 problem in JULY15 challenge.

Corner Case:

This case troubled me for a lot the case is p = 0, when answer is 1, independent of the grid size.

Finally a python implementation of the above said solution : Link

If you fell your question was answered mark it as accepted.

8 Likes
5

I can explain my approach to the problem.
The problem can be broken into two parts

  1. The Optimal solution to the game 1 and 2.

  2. The Probability of chef beating Yoda.

Now to the first part i just applied exhaustive search to find solution for small values of n,m to find a pattern and then formulated the answer based on my findings.

For the second part i broke the problem into 3 parts i.e when chef wins both games P(chef win both) = 1 , when chef losses both games P(chef losses both ) = 0 except when p=0(from problem) and the last part ,when chef wins any one game and losses the second P(chef wins one)

Now the P(chef wins one) is equivalent to tossing a coin k(from problem) of times and getting at least p(from question) head .

I used normal approximation for binomial distribution with continuity correction to solve the above said problem and solved the problem. https://onlinecourses.science.psu.edu/stat414/node/179

I hope this makes sense to you.
My solution ( only 80 points ) https://www.codechef.com/viewsolution/12888678

2 Likes
6

In addition to what the others have said, python has a really good maths library and you can easily calculate the cumulative binomial distribution.
Solution

4 Likes
7

I used simple log properties , solve each C(K,I) / 2^K , by taking log both side
https://www.codechef.com/viewsolution/12865270

8

Since for the third case (the case in which your program failed) had n<=1000 you could have used DP itself for an AC.

Also I tried solving this using the normal approximation but I could not get it in the 4th case and went for log properties.

1 Like
9

Short and effective.

10

This question is simple as it looks! The Matrix N * M is been given to check your presence of mind! If you give attention for few minutes then you wil find that-

  • If N and M will be odd then answer
    will be 0 (Chef can not win the
    game).
  • if N and M both will even then answer is 1 as chef
    will always will the game whatever set he will choose.
  • The main problem will occur when
    Matrix size is not both even or odd.
    Means when only one of them is even
    or odd in value of N and M.

So how to solve this part! It simple as you will see chef will win only in first set of rule. So by using combinatorics you will find that the answer will be given as ∑(i=p to i=k) (kCi / 2k ) i.e, (kCi + kCi+1 + … + kCk )/ 2k.

Now the question boils down how to find such value for the range upto 106 ?

So here we will use the logarithm approach to avoid overflow and store all these value in dp[] array like… n! = n * (n-1) * (n-2) * (n-3) * … * 3 * 2 * 1. As we will store the factorial of n by taking log2() on both sides as log(n!) = log(n) + log(n-1) + log(n-2) + … + log(3) + log(2) + log(1).

Now when we need factorial of any number then we just use this precomputed value. How?

Suppose if we wanna find the value of kCi then we can write it as dp[k] - dp[k-i] - dp[i]. but we have extra factor of k from 2^k so we will subtract it from this value. and the result will become as res= dp[k] - dp[k-i] - dp[i] - k. Now this result is in log2() form so to get actual value we will convert to result as 2res

for(i=p;i<=k;++i)
   {
    res=dp[k]-dp[i]-dp[k-i]-k;
    ans+=pow(2.0, res);
 
   }

Tada! Now your question has been solved!

Just see my solution part to know more about how it is working. Click

If anyone have still query then please feel free to ask.

11

The answer to the solution is cumulative sum binomial distribution. So you can calculate nC(r+1) from nCr from simple math calculation. You can store answer in long double but if it becomes greater then some limit like e.g 1000 then divide it by 2 until it become less than 1. Here is my solution AC in 0.19 seconds https://www.codechef.com/viewsolution/12837179

2 Likes
12

I got the logic that when chef wins in exactly one of the strategies we need to find the cumulative binomial probability . But I am facing some issue in the logic to find whether chef has a winning strategy for a given board dimension.

When I am at coordinate (i,j) and turn t (1 (chef) , 0 (yoda)) , I mark that coordinate and If current turn is chef then either one of the adjacent move should lead to a optimal game or else I loose . If the current turn is yoda then all adjacent move he takes chef should win or else yoda will take that move and chef will lose .

My Code : https://www.codechef.com/viewsolution/12806209

Can someone help me in finding my mistake.

13

We can also use incomplete beta function for computing cumulative binomial distribution. The winner of the contest used it.
You can read more about this function here -

http://www.it.uom.gr/teaching/linearalgebra/NumericalRecipiesInC/c6-4.pdf

1 Like
14

My approach is this: if the matrix dimensions are both even, then Chef wins with both of the rules, if they’re both odd - Yoda wins with both of the rules, otherwise - there’s a 1/2 probability.
Then I divide the number of favourable combinations (i.e. where Chef win at least p times) by the total number of combinations.

For subtasks 1 and 2 I get AC, why is the code wrong in subtask 3?

https://www.codechef.com/viewsolution/12831429

Where is my mistake?

15

The link that you’ve attached is broken

16

Sorry! It’s fixed now.

17

bhisma probably taking a few test and drawing them out: cases of odd * odd, odd * even and even*even matrices of small sizes could help in understanding the result of a game.
Problem then reduces to finding kCi/pow(2,K) where p<=i<=k which can be done using log as others have mentioned.

18

Instead of using log, we can keep dividing by 10 and store the exponent separately.

here is my solution

Please upvote, thanks :slight_smile:

1 Like
19

@bansal1232 , Could you please explain logic that you used to decide that if N, M are even/odd, Chef/Yoda will be the winner. I tried to draw a 4 x 4, 4 x 5 grid, etc, to understand why, but couldn’t figure out what the logic was because there are so many moves possible.

20

Don’t start with 4x4 or 4x5!

Start with 1x1 and slowly proceed till 3x3. Try it once, and if its still unclear, I can help. :slight_smile: