 # Honour Code discussion

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) 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 , 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 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… 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. 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 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