Lakshi4h's blog

[help] Task Hop COCI 2021 January
By Lakshi4h, history, 3 years ago, In English

I've been trying to solve this problem for few days now but can't think of a solution.

Here's the statement,

In case you need to read the full statement: Problem Link

What I observed so far:

  • worst case is in the form of $$$a^{1} , a^{2} , a^{3} , ... $$$ for some integer $$$a > 1$$$

  • in the worst case $$$i$$$ th element has $$$i-1$$$ in degree and $$$n-i$$$ out degree (1 based indexing)

That's all :(

I can't even prove that there's a solution for the worst case. Can someone help me solve this?

Thank you in advance

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

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Why you didn't read the official editorial?

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

    Now I did. It's really short. Couldn't understand it either. I understand what it does but i don't understand why it works.

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

      Numbers from 0 to 15 in blue and green rectangles

      Let me expand on the formal solution a bit. It is equivalent to the following:

      Group the water lilies in the input according to the position of their leading bit. You have at most 64 groups, marked 0 to 63.

      Then draw blue (frog 1) rectangles around consecutive four, green (frog 2) rectangles around consecutive 16's, and draw one big red (frog 3) rectangle around everything.

      Note that any edge goes between two distinct leading bit groups. Color the edge with the color of the smallest rectangle containing it.

      Can you see why there don't exist four consecutive edges with the same color?

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

        That's a really good explanation. I understood. Thank you.

        → Reply