fivedemands's blog

GCJ 2020 Round 2 Discussion
By fivedemands, history, 4 years ago, In English

Let's discuss about this software development competition.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve C?

I tried an $$$O(n^3)$$$ solution: enumerating all possible initial direction $$$(dx,dy)$$$,(which is $$$O(n^2$$$)) and then checking how many holes are lying in the same direction: $$$(x_i-x_j,y_i-y_j)=\alpha \cdot(dx,dy)$$$.

The holes lying in the same direction can always be reached because we can use a zig zag path to connect them.

And we can add two more additional holes as the start and end.

I thought it should work, but I got an WA for that. Is there anything wrong in my solution?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Suppose you have an even chain with a bunch of independent singletons. The optimal solution is to start from a singleton and traverse the whole chain (and you cannot pick anymore singletons in this case).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      I see, I just misunderstand the problem statement.

      I thought the ball could pass through the normal hole rather than stop :(

      Thx!

      → Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Somehow they managed to make a round 2 which is even more boring than last year.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    For me, a contest is only boring if I solved all the problems (not only if). Else there are always something to learn.

    → Reply
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I wonder what possible explanation there is for the correlation between the platform change and the quality drop in the contests.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -98 Vote: I do not like it

    Are you that upset about not noticing a case in B-small?

    Something tells me it's not the competition's fault...

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -39 Vote: I do not like it

      Why the heck is this being downvoted? I mean, just because you consider the round to be such-and-such doesn't mean others do too.

      Or is just the herd instinct?

      → Reply