CodeClub, IIT Kharagpur brings to you CodeNite Sept 2023 sponsored by Coding Ninjas, a competitive programming contest with individual participation to be held on CodeChef. This contest is OPEN TO ALL irrespective of college, year of study, department.
Details are as follows:
Date: Friday, 8th Sept 2023
Time: 9PM to 11:30PM [GMT+5:30]
Platform: CodeChef
Prizes:
1st — Rs. 4000
2nd — Rs. 2500
3rd — Rs. 1500
4th — Rs. 1000
5th — Rs. 1000
Setters & Testers : anubhavdhar, shuklaji1102, anitm, harshith_04, picramide, aryansanghi, gayathri_anant, harshit_jain52
Contest Page: https://www.codechef.com/CONT2023
Register here if you want to take part and be eligible for the prizes: https://forms.gle/eFYL5Fjyqn1kDbju6
Deadline to register: 6PM, 08/09/2023
NOTE — Though everyone is encouraged to participate, only Indian college students are eligible for prizes.
See you all on the leaderboard!
Auto comment: topic has been updated by shivansh1102 (previous revision, new revision, compare).
A Gentle reminder for CodeNite Sept 2023 which is scheduled at 9PM today. Link to the contest page: https://www.codechef.com/CONT2023. If you haven't registered already, you still can do it, register at: https://forms.gle/eFYL5Fjyqn1kDbju6.
See you on the leaderboard!
How to solve Game Of Dots?
We'll release editorial soon. Hint: DFS and and the most common mistake — did not check if number of edges is odd as if it is odd, first turn will be of Bob from the state given.
Should've mentioned Alice and Bob start playing from the blank state, not the input state. Even in samples you have started turn 1 from the input state (not turn 13).
We did write in problem statement that Alice went first in each game. Also in explanation we wrote that since 12 edges have been placed, first turn will be of Alice which was an indication that had it been some other number, first turn could be of Bob. But we do understand that there might have been some confusions so we made an announcement at the 11:10 mark clarifying it after recieving question in comment.
Wishing you luck in future contests and hope you had fun in this one.
Announcements in codechef do not show up as browser notifications so they are pretty useless. You could have just modified the statement.
Also, the announcement is:
This doesn't give any information which isn't already in the statement itself, you should have made it explicitly clear that the turns to achieve the initial state are also taken into account.
Lastly, why doesn't the problem always have alice starting first from the given state anyways? Having to take into account the previous turns is trivial if stated clearly and does not make the problem any more difficult, it's just frustrating and reduces the quality of the problem.
The problem statement and test case explanation were clear in themselves about who went first so that's the reason we didn't modify it. And regarding why Alice isn't starting first, the problem makes more sense when Alice starts first in each game from blank state. Alice starting first always from current state doesn't make much sense as why he started first from blank state when edges were even and not when they were odd. But we do understand the concern, we'll take it into consideration to make our future codenites more fun and a little less confusing. Thank you for your feedback.
How to solve Game of Dots?
Build an undirected graph in which you add an edge between two adjacent cells if their shared grid edge is not in the set of initially added grid edges.
We get some connected components now, in any connected component, if a player adds one grid edge to any of the cells in that component, then the next player can "take" all of the cells in that component, and its optimal for the next player to do so.
So in any turn, bob/alice will take the entire component "made available" to them by the other player in his previous turn, and then add a grid edge to the currently smallest sized remaining component, making this component "available" to the other player in his next turn.
This doesn't look true to me.
Consider the following initial state on a 4x4 grid:
There are two components, of sizes $$$4$$$ and $$$5$$$. Alice moves first.
If Alice adds an edge to the size-$$$5$$$ component, Bob takes it all and she loses — so she must add an edge to the size-$$$4$$$ component.
But then, Bob can add another edge to the $$$4$$$-component without creating a square, ending up in something like:
Now it's Alice's move, who is clearly forced to place an edge in the $$$5$$$-component no matter what is done in the $$$4$$$-component; allowing Bob to take the $$$5$$$-component and win.
Your greedy strategy (and it seems, all AC submissions in the contest) output Alice as the winner, so either the testdata is weak or the intended solution is wrong.
You are correct. It's funny that all ac submissions also used this wrong strat too, I think everyone was influenced by intuition developed by actually playing this game when they were small.
https://discuss.codechef.com/t/gamedots-editorial/111543
The editorial to the Game of Dots question. You are right, greedy strat won't yield the correct answer.
Nice problemset. Couldn't solve the last one.
We'll release the editorial soon. You'll be able to see others' solutions after some time.
Contest is over, please find the result post here. Hope you had fun!
There were some confusions regarding Game of Dots, we're extremely sorry if it caused you any inconvenience & we'll make sure it won't happen again. We'll release editorials after a few days.
Does anyone know the correct solution to game of dots? All AC solutions have a wrong greedy strategy. It is sometimes optimal to not take squares and stall your turn if future turns give advantage.
Pretty funny that this problem exposed me to this solution. Playing this game in my childhood, me and my friends always took the greedy strategy.
https://discuss.codechef.com/t/gamedots-editorial/111543
The editorial to the Game of Dots question.
The editorial has been posted here. Thanks for participating!