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
- we have already used elements 1 to i-1,
- the "bigger" of the sets (A or B) has d more elements than the other, and
- 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.