chrome's blog

Topcoder Single Round Match 659
By chrome, 9 years ago, translation, In English

Hi there!

Today at 04:00 MSK will be held Topcoder SRM 659.

Let's discuss problems after contest.

Editorial for problems.

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

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

Is there anyone who solved Div. 1 Medium with complexity better than O(n * 3m)?

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

    Sure, O(nm2m).

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

    Wait, can you actually make that pass?

    Edit: Ignore that, it is discussed in the editorial blog.

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

      Can you please explain any of the states that have been discussed in the editorial?

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

        I find it easier to think in terms of a n × m grid. You are supposed to place a 1 × 2 tile or 1 × 1 tile or cover two cells of the same colour in adjacent rows, and we have to find the number of ways to tile the grid. You just run across the grid in row-wise order choosing how the next cell is tiled. If we choose the special tiling(same colour in adjacent rows), then we have to remember to not tile the next occurrence of this colour(that is, the occurence in the next row). So, it is natural to keep a set(a bitmask) of the colours that we have to ignore as we run across. So, the dp state is (x, y, colours that you ignore). Now, if the next cell is one of the colours that I ignore, update the set and continue forward. Otherwise, we choose how to tile the current cell. If it is going to be tiled by a 1 × 1 tile, you continue forward. If it is a special tile, you update the set asking to ignore the next occurrence of this colour. Finally, if it is a 1 × 2 tile, you have to make sure that the next 2 cells(the current one and the next one) are in the same row and that you cannot ignore the next 2 cells. If so, tile that way. Check out Endagorion's clear implementation for the same.

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

          Thanks for your amazing explanation!

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

Does anyone know where can I find topcoder SRM editorials? I searched exhaustively with no success.

→ Reply