Блог пользователя fivedemands

GCJ 2020 Round 2 Discussion
Автор fivedemands, история, 5 лет назад, По-английски

Let's discuss about this software development competition.

  • Проголосовать: нравится
  • +191
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится -98 Проголосовать: не нравится

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

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

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -39 Проголосовать: не нравится

      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?

      → Ответить