shivansh1102's blog

CodeNite Sept 2023, organized by CodeClub, IIT Kharagpur
By shivansh1102, 16 months ago, In English

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!

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shivansh1102 (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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!

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Game Of Dots?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
          ← Rev. 2   Vote: I like it +15 Vote: I do not like it

          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:

          Problem — Game Of Dots: As given in the problem statement, Alice goes first at the start of the game.

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
            ← Rev. 2   Vote: I like it +4 Vote: I do not like it

            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.

            → Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Game of Dots?

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      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.

      This doesn't look true to me.

      Consider the following initial state on a 4x4 grid:

      Image

      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:

      Image

      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.

      → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problemset. Couldn't solve the last one.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We'll release the editorial soon. You'll be able to see others' solutions after some time.

    → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The editorial has been posted here. Thanks for participating!

→ Reply