Honour Code discussion

1

Contest Link : Contest Page | CodeChef

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
2

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
3

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
4

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…

5

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

2 Likes
6

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

1 Like
8

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

2 Likes
9

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?

10

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

1 Like
11

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

1 Like
12

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

2 Likes
13

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…

15

We will upload the editorials in a few days.

1 Like
17

Yes @aryanc403, now i realized this.

1 Like
18

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
20

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

23

Thanks!

24

I simply wrote 1 3 4 and realized why the intuition thing is not correct cuz the second guy can do things which are much better and optimal and he can actually win, so in 2-3 minutes, I was sure that this is wrong and xor should be the way to go. But then I saw the polygon problem and went there because things were more straightforward there , but calculation was a bit more.(also haven’t touched game theory in a long time as its not asked often maybe)

27

For Problem 2, refer these two videos on game theory
game theory
sprague-grundy theorem

I didn`t knew anything about how to approach problems in game theory, just saw these videos during the contest, got an intuition and coded it and it got accepted, pretty fantastic feeling :grinning:

Kudos to JAlgs for these videos

3 Likes
28

How did you solve the secondlast problem? The one where balls collide…