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
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.
I like your analysis, there is just a slight problem in the explanation of the 250 (I noticed because it is the same mistake I made during the contest, making my 250 fail.. :( ). When you say that the number of arithmetic terms is max(0, (upperBound - a) / b + 1), this would evaluate to 1 if, for example, upperBound = 5, a = 6, and b = 7, which is incorrect. Maybe it would be better to say that the number of arithmetic terms is (upperBound >= a ? (upperBound-a)/b + 1 : 0).
Notice you should split dp[i][j - L - 1] * ways[L] * dp[i - 1][L] operation in two since we're computing the answer by the modulo of 100000007, and 100000007 * 100000007 * 100000007 will cause long long type overflow.