Honour Code discussion

Contest Link : https://www.codechef.com/HOCO2020/

First problem could be done using strings…

How did you guys solve 2nd and 3rd one ?

I used prefix sums in 3rd one which fortunately worked out(AC) and thought something for 2nd which turned out to be wrong(WA) :frowning: So, how do we determine who wins the game in 2nd problem ?

Edit:- Realized the basic xor nim was the answer for the 2nd problem which I completely ignored :stuck_out_tongue: , but it is not that easy/straightforward as mentioned by

@aryanc403

4 Likes

I can’t figure out what’s wrong with my solution for HCODE04. Is it possible for the testcase files to be made public?

1 Like

For the 2nd problem, bruteforce grundy nimbers for small piles (that’s what I did), and notice that grundy(n) = n - 1. Then take xor of nimbers of all piles.

2 Likes

Thanks :slight_smile:
Also, in the third problem, I think, setter should have mentioned something like:-
"Don’t worry, all calculations will give integer or .5 values , cuz area can be anything like float,etc… after doing so many area calculations, the final area might not be an integer…also…that modulo 1e9+7 is annoying, its not needed at all, as 10^18 is the max area possible…

It can be proven that area * 2 is always an integer.

2 Likes

Yup, but how??? Like for any convex polygon…:sweat_smile:

1 Like

You can split a polygon in triangles and twice the area of any triangle with interger coordinate is an integer.
Proof lies in area of triangle using determinant.
\frac{1}{2}(x1(y2-y3)+x2(y3-y1)+x3(y1-y2))

4 Likes

Shoelace formula used to calculate (twice of)area is itself a simple product of two integers!

2 Likes

I think the 2nd question can be solved by counting how many of the numbers are greater than 1.
And if count is even 2 wins, else 1 wins. Is it correct?

I did it and it gave wrong answer. :frowning:
Xor nim is the only correct solution.

1 Like

When you do calculation it will be overflow 1<<66 though the final answer may be or may not in range 1e18.

1 Like

No, it wasn’t. It has already been explained by @rahul_g.

2 Likes

I did the calculation without mod, and just put mod in the final line and it gives AC, so the area is in range 10^18, cuz just take a square with extreme co-ordinates like (1,1)…bottom left and , and (10^9,10^9)…top right…now find the area,it gives 10^18…

The maximum area will be a square of side 1e9 and it will fit into long long int.
1≤x,y≤10^9 area of this square is (10^9-1)^2.

1 Like

We will upload the editorials in a few days.

1 Like

“Taking Notes” was a nice problem.

Summary

This isn’t a sarcastic comment which I often make.

2 Likes

Yes @aryanc403, now i realized this.

1 Like

Is there some way to solve this problem other than bruteforcing the pattern?
I mean any easy way to see its x piles as x - 1 piles in nim game.

2 Likes

Can you help me why that solution doesn’t work. What is wrong with that logic, as it seems correct :expressionless:

Ok. One can prove it.
Proof by induction.
0,1 are losing position => their grundy is 0.
grundy({x,y,z})=grundy(x)^grundy(y)^grundy(z).
grundy(2)=mex(grundy({1,1})=1.

Induction step -
Lets assume grundy(j)=j-1 for j<n.

grundy(n)=mex(grundy({i,j}) for all 1<=i,1<=j and i+j<=n.
Just take i=1 => this set contains all nos <=n-2. => Mex is atleast n-1.

Now lets prove that grundy({i,j})<=n-2.
Note that i+j=(i xor j) + 2*(i and j) Because (i and j)>=0 => (i xor j) <= (i+j)

grundy({i,j})=(i-1)^(j-1) for i,j >=1.
(i-1)^(j-1) <= i-1 + j-1 <= n-2.

5 Likes