dojiboy9's blog

By dojiboy9, 11 years ago, In English

Here is a short editorial on TopCoder SRM 605 Medium problem, AlienAndSetDiv1. As mentioned, I would like to share more as I am learning. Maybe this will help me learn better and help others learn as well! Spoiler I hope this is ok!

Since we are counting on an ordered set, this is likely to be a DP problem. We also notice that K is very small (K <= 10), so we might be able to do a Bitmask DP (with a K-bit bitmask). Lastly, suppose we have partially-built sets A and B and want to place element i into one of these sets. Whether we can place it onto A or B depends on which set is bigger, and also depends on which of the last K-1 elements {i-1, i-2, ..., i-(K-1)} have been placed into the bigger set. This is what we use the bitmask for.

This gives a dp of the form:

dp[i][d][s] := the number of ways to place elements i to 2N if

  1. we have already used elements 1 to i-1,
  2. the "bigger" of the sets (A or B) has d more elements than the other, and
  3. the set of items in {i-1, i-2, ..., i-(K-1)} that appear in the last d slots of the "bigger" set is the bitmask s (where bit 0 corresponds to element i-1, and so on.)

Then dp[i][d][s] can be computed from dp[i+1][d+1][s'] and dp[i+1][d-1][s''] for certain s' and s'', depending on a few different cases. I will "leave it as an exercise" to the reader to fill in the rest of the details.

I also posted an in-depth analysis at: http://dojiboy9.atspace.cc/contest/?p=349 for anyone who wants to understand the thought-process behind coming to the right solution.

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