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 :- CodeChef: Practical coding for everyone

4 Likes
3

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
4

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 ) CodeChef: Practical coding for everyone

2 Likes
5

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
6

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

7

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.

8

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 CodeChef: Practical coding for everyone

2 Likes
9

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.

10

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
11

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?

CodeChef: Practical coding for everyone

Where is my mistake?

12

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.

13

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
14

@gonecase- (To others, the question he asked is in comment of bansal1232’s answer, just telling so no one gets confused :slight_smile: )

Ah! I see. Its a good question that why we are generalizing our observations. While I am still beginner in game theory type of questions, I will try my best to explain.

We are given that they play optimally. When both the players play optimally, then win and loss are solely decided by starting conditions, which in this case are dimensions of board.

This type of question usually require you to spot the recurring condition whichs are causing loss or win.

Yes, there are MANY possible moves for high matrix, and yes, for some questions you might have to go through all possible moves to find the optimal moves chosen by them. (Hence why we prefer performing it on smaller cases and extend it to larger ones).

While it is possible to symmetrically/mathematically or conceptually prove the wins in this Q, it can get really tough.

Eg- Lets take a case of N and M being odd, and diagonal rule set is to be followed (meaning they can only move diagonally)

Lets say we have a 5x5 grid, and chef starts at 1,1.

The ONLY possible move for Chef is to move from 1,1 to 2,2. Now, YODA wants to win, and after some trials you will find his optimal move is to push it from 2,2 to 3,3. Now poor chef can either go to 2,4 or 4,2 or 4,4. And its easily seen that no matter WHERE he moves, he is going to lose (as after his move, YODA could force the coin to another corner, getting the win.)

What determined who won or not? There were two factors here-

  1. Chef HAD to move from 1,1 to 2,2. No other possible move.
  2. The Size of board favoured YODA when he played optimally.

Now you may want to argue for a 7x7 board.

7X7 BOARD

Chef moves to 2,2. Now YODA would force him BACK to 1,3. Chef would have ONLY 1 POSSIBLE MOVE, i.e. from 1,3 to 2,4. YODA will again make him go to 1,5 , then chef could only go to 6,2 , and then YODA wins by making final move at 1,7.

NOTE- The same strategy could also be followed in 5x5 board. Actually, MULTIPLE winning strategy exist for a particular N and M, and what we found in case of 5x5 was something specific to it, (or perhaps extensible to higher cases, didn’t check…too many possible moves).

NOTE 2 - We can interchange rows and columns here. Meaning If chef moves to 2,2, yoda can follow exact same strategy and move to 3,1 (& etc.) and win, provided that side is also odd.

(Also, I am sorry if I interchanged rows or columns in my explanation, please refer to image for clarity :slight_smile: )

alt text

Here we found the true symmetry, and a concrete proof that at least one winning strategy for YODA EXISTS if both N and M are odd. YODA can play it every time N and M are odd. We can extend it to cases for 9x9,11x11 and so on. (Thus, for this case, extending of our base cases should work.)

And after concluding this, we might be interested in extending our base observations of other conditions to higher N and M. (Eg- When both even, when one even one odd etc.)

You CAN find other symmetries for other cases, but its tough. And problem setters expected us to conclude from observations.

Now, what if it fails? Had it failed, and we would had been unable to extend our base observations to higher ones, then we would be forced to either derive that when does winning strategy exist for CHEF/YODA (like we did above), OR there would be some hidden trick in Q for us to decipher.

I am sorry, I cant afford to go on deriving all possible cases at this moment ( Second Series of Exams from 31st…T_T pray for me :frowning: ), but I hope I quenched your query. BTW, it was a good question you asked, I am sure it would help many other people with similar doubt.

(PS- If you look at the image for 7X7 carefully, you would realize that the same strategy YODA can play if either one of N and M are even (because effectively everything is happening in the 2X7 matrix.) Meaning he can play this and win if N odd and M even. This when DIAGONAL rules are to be followed. When diagonal rules are not followed, we can prove that chef would win. (The strategy he’d use is to go from 1,1 to 1,2 [1 cell down], forcing YODA to go from (2,2) and similarly win. (I thin you must have derived it in 2x2 and 2x3 type of matrices) )

2 Likes
15

Just used some property of logarithms.

Here’s my code

16

For the diagonal move rule (Rule 2), I got the proof of “why does Yoda win when either side of the matrix is odd”. But for the other rule, I didn’t find any solid proof of the winning conclusions. Are they just derived from observations or there is any proof?

17

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

18

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
19

Short and effective.

20

The link that you’ve attached is broken