JOIN Match Editorial
SRM 395
Wednesday, March 26, 2008

## Match summary

In division 1, coders were faced with an easy problem that required careful case analysis, and DP-based medium and hard problems. Smylic made a charge to take the lead with three successful challenges during the challenge phase, but system tests took down his hard problem. SnapDragon seeked out his 42nd victory in a very close match. Gassa came in second, only 10 points behind, followed by kia only 7 points behind him.

Division 2 coders faced a reasonably straightforward set. 22 coders were able to successfully complete all three problems correctly, with nikkitousen taking home the SRM win. BoramMan and index took home second and third place, respectively.

# The Problems

SquareDigitNumbers  Used as: Division Two - Level One:
 Value 250 Submission Rate 428 / 496 (86.29%) Success Rate 385 / 428 (89.95%) High Score KnightOfTheSun for 248.43 points (2 mins 15 secs) Average Score 195.04 (for 385 correct submissions)

The constraints for this problem allow for a brute force solution to run in time. We start at k=0, and increment a counter when we find a number containing only the digits 0, 1, 4, and 9. When our counter is equal to N, we return the value. See nikkitousen's code for a clean implementation of this.

An asymptotically faster solution instead relies on writing the number in base 4 (just using the digits 0, 1, 4, and 9 instead of 0, 1, 2, and 3). See UNKNOWN USER's code for a very nice implementation of this approach.

StreetWalking  Used as: Division Two - Level Two:
 Value 500 Submission Rate 271 / 496 (54.64%) Success Rate 182 / 271 (67.16%) High Score pawel001 for 454.38 points (9 mins 11 secs) Average Score 301.39 (for 182 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 406 / 431 (94.20%) Success Rate 352 / 406 (86.70%) High Score SkidanovAlex for 247.06 points (3 mins 6 secs) Average Score 196.11 (for 352 correct submissions)

It is clear from the constraints of the problem that we need an algorithm better than O(N) to successfully solve the problem. To figure out how to solve this, let us begin by looking at the simplest solution, moving X times to the right and Y times up (without loss of generality, assume X >= Y). We can do these moves in any order, so let us alternate X's and Y's and put any extra X's at the end; thus, the solution can be represented as "XYXY...XYXXX...X". This solution arrives at the destination with no extra distance required. If sneakTime < 2*walkTime, then it is beneficial for us to replace all occurrences of "XY" in this string with sneaking ("S"). In this case, the string then becomes "SS....SSXX...X". Furthermore, in cases where sneakTime < walkTime, we can proceed to sneak twice (as seen in example 2) to replace two X's. In this case, the solution becomes "SS.....S(X)", where the X in parentheses indicates that an X will be left over if the sum of X and Y is odd. Thus, the solution can be written as follows:

```if(X < Y) swap(X, Y);
if(sneakTime > 2*walkTime) return (X+Y)*walkTime;
else if(sneakTime > walkTime) return Y*sneakTime + (X-Y)*walkTime;
else if((X+Y)%2 == 0) return X*sneakTime;
else return (X-1)*sneakTime + walkTime;
```

Of course in the above code, one must ensure that you use 64-bit variables to handle cases where overflow may happen.

TriviaGame  Used as: Division Two - Level Three:
 Value 1000 Submission Rate 71 / 496 (14.31%) Success Rate 32 / 71 (45.07%) High Score nikkitousen for 846.57 points (12 mins 34 secs) Average Score 639.17 (for 32 correct submissions)

This is a classic example of dynamic programming. I'll first describe the solution using recursion with memoization. Let your current state be (cur, tokens), where cur is equal to the current question that you are being asked, and tokens is the number of tokens that you currently have. We will also define dp(c, t) to be the maximum number of points you can additionally score if currently at question c with t tokens. When you are asked the current question, you have two options. If you get the question wrong, then you can score dp(cur+1, tokens) - points[cur]. If you get the question right, then we have two more cases. If tokens+1==tokensNeeded, then you can score dp(cur+1, 0) + points[cur] + bonuses[cur]. Otherwise, you can score dp(cur+1, tokens+1) + points[cur]. Once we know the maximum score for both cases (answering correctly or incorrectly), we choose the maximum value and return it. Thus we have established our DP relation, and need a base case, namely when cur==N (the number of questions). In this case, we can return 0 (there are no more questions to get right). Thus, our answer is simply dp(0, 0).

```int NEGINF = -10000000;    // a negative number we can't reach
int dp(int cur, int t)
{
if(cur==N) // if we've answered all questions
return 0;
if(dptable[cur][t]> NEGINF)    // if we've seen this before
return dptable[cur][t];

// possibility 1 = get the question wrong
int answerwrong = dp(cur+1, t) - points[cur];

if(t+1==tN)    // if we earn the bonus answering the question
answerright = dp(cur+1, 0) + points[cur] + bonuses[cur];
else     // no bonus
answerright = dp(cur+1, t+1) + points[cur];

// pick the choice that earns the most points
}
```

This problem is a very good place to practice dynamic programming from the top down. See BoramMan's solution for a clean version of this code.

Skyscrapers  Used as: Division One - Level Two:
 Value 500 Submission Rate 196 / 431 (45.48%) Success Rate 139 / 196 (70.92%) High Score Gumx for 484.94 points (5 mins 2 secs) Average Score 316.39 (for 139 correct submissions)

There were some complicated ways to solve this problem using combinations, but there was a much simpler solution. Assume we have N buildings left to place, requiring L visible buildings on the left and R visible on the right. We now can decide where to place the smallest building. If we place it in the leftmost location, then it is visible from the left (but not the right). Thus, we can pretend that that building doesn't exist, and solve the simpler problem (N-1, L-1, R). Similarly, if we place the building on the right, we can move to the new problem (N-1, L, R-1). In the remaining N-2 cases to place the building, we can't see this building, and so move to (N-1, L, R). Our base case occurs when N=1; if L=1 and R=1 then we return 1, otherwise we return 0. Java code for the recursion:

```int dp(int N, int L, int R)
{
if(N==1) return (L==1 && R==1) ? 1 : 0;
if(L < 1 || R < 1) return 0;
if(dptable[N][L][R] > -1) return dptable[N][L][R];

dptable[N][L][R] = (int)(((long)dp(N-1, L-1, R)
+ (long)dp(N-1, L, R-1)
+ (long)(N-2)*(long)dp(N-1, L, R))
% 1000000007);
return dptable[N][L][R];
}
```

Using combinations, it is actually possible to solve the problem in O(N2) time. See msg555 and neal_wu's code in the practice rooms for implementations of this.

PubTrivia  Used as: Division One - Level Three:
 Value 900 Submission Rate 88 / 431 (20.42%) Success Rate 23 / 88 (26.14%) High Score janos for 685.13 points (17 mins 4 secs) Average Score 516.43 (for 23 correct submissions)

Due to the large constraints, we need an algorithm that runs faster than O(N2). To explain the concept, we will create a 2-D array called dp. dp[cur] represents the maximum score we can achieve after answering the cur-th question without receiving the bonus. dp[cur] represents the maximum score we can achieve by receiving a bonus on the cur-th question. The recurrence relation can then be seen as follows (ignoring out-of-bounds errors):

1. dp[cur] = points[cur] + max(dp[cur-1], dp[cur-1]);
2. dp[cur] = cumsum[cur] + bonuses[cur] + max(dp[cur-tokensNeeded], max(dp[cur-tokensNeeded-1], dp[cur-tokensNeeded-1])-points[i-tokensNeeded]);

What the above code means is: if we don't want to have the bonus on that question, we take the maximum value (bonus or no bonus) from the previous question and add our score to it. If we want the bonus, we can start having received a bonus exactly tokensNeeded questions ago (the dp[i-tokensNeeded] term), or we can get question (i-tokensNeeded) wrong (and thus take the best value from question (i-tokensNeeded-1) ).

In equations above cumsum[cur] means the total number of points for consecutive tokensNeeded questions between (cur-tokensNeeded+1)-th and cur-th, inclusive. You can precalculate cumsum[cur] in O(N) time using the following code:

```int[] cs = new int[N+1];
for(i=1; i<=N; i++)
cs[i] = cs[i-1] + points[i];
int[] cumsum = new int[N+1];
for(int i=tokensNeeded, i<=N; i++)
cumsum[i] = cs[i] - cs[i-tokensNeeded];
```

The answer is then the maximum of dp[N] and dp[N]. One needs to be careful when solving this problem to avoid index out of bounds issues, for example when tokensNeeded is greater than N (or tokensNeeded==1). See Gassa's solution for this solution, or see SnapDragon's code for a solution using a single DP array (eliminating the need for the Nx2 array). By connect4
TopCoder Member 