In my quest to regain my red color on Topcoder this morning, I failed once again in SRM 523. I'll present a quick summary of the solutions here; the problem set was actually quite easy, but with some tricks and edge cases.

Easy (250)

We can compute the number of values from the arithmetic series as (upperBound - a) / b + 1 if a ≤ upperBound and zero otherwise. Then we simply check all values in the geometric series (only a logarithmic number) to see if they are in the arithmetic series. If not, count them in the result. There is some trickiness with d = 1 and when a, c > upperBound.

Medium (500)

This is a pretty straightforward dynamic programming problem. The approach is to compute dp[i][j] for 0 ≤ i ≤ h and 0 ≤ j ≤ w which is the number of structures of height i and width j. We will also compute the values ways[i] which is the number of ways to get a 1 × i structure with no gaps. The latter is a simple DP, and we can compute dp[i][j] as follows (we will think of this as filling in the bottom row and then using the previously computed values to determine how many structures can exist on top of it):

• dp[i][0] = 1, and for j ≥ 1,
• dp[i][j] = dp[i][j - 1] (position j is empty)
  
• dp[i][j] = dp[i][j] + ways[j] * dp[i - 1][j]
• dp[i][j] = dp[i][j] + dp[i][j - L - 1] * ways[L] * dp[i - 1][L] for 1 ≤ L ≤ j - 1
  

The last two equations are obtained by considering the last contiguous sequence of blocks in the bottom row. If it is j, i.e. the entire row, then we just multiply the number of ways to build a 1 × j structure with no gaps (ways[j]) with the number of ways to build the structure of height i - 1 above it (dp[i - 1][j]). Otherwise, we consider all lengths L with 1 ≤ L ≤ j - 1. We need to leave a gap of one (or else the contiguous sequence might be larger), so there are dp[i][j - L - 1] ways to build everything before the last sequence and ways[L] * dp[i - 1][L] ways to build the 1 × L structure with no gaps and everything above it. Computing all these values gives dp[h][w] as the desired answer.

Hard (900)

We'll start with a simple idea: for each starting location, i.e. grid squares with a letter, just do a DFS to depth 20, keeping track of all letters we have seen so far (as a bitmask). We never visit a cell with a letter we've already seen (so we never visit cells multiple times). This solution has something like n * m * 3^20 running time, which is not fast enough. We can use a clever trick to reduce this to something manageable.

Consider two paths starting from the same cell which see sets of letters A and B, respectively. We'll ignore paths that visit the same letter multiple times and paths which visit the letter c which is in the starting cell (no such paths can be part of a Latin alphabet path). Then we claim that we have a Latin alphabet path if and only if each Latin letter is in exactly one of A, B, and {c}. This is pretty easy to see, as we just start at the end of the first path and go to the end of the second, and for any Latin alphabet path, there is a unique midpoint letter c which splits the path into the corresponding A and B. So instead of computing all paths of depth 20, we just consider all paths of length 10 and for each subset S keep track of count[S], the number of such paths which visit the letters in S exactly. Finally, multiply the results for complementary sets together, i.e. count[A] * count[B] for the condition above, adding up these values for all positions in the grid. Note that each set A will have exactly one complementary set B which is L - A - {c} where L is the set of all Latin letters. This reduces the complexity to something like n * m * 3^10 which runs in time.