fivedemands's blog

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

Let's discuss about this software development competition.

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

»
6 years ago, hide # |
 
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
  • »
    »
    6 years ago, hide # ^ |
     
    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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
  • »
    »
    6 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      6 years ago, hide # ^ |
       
      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