Match Editorial

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

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.

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)

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.

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];

    int answerright;
    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
    return dptable[cur][t] = Math.max(answerwrong, answerright);
}

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.

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(N²) time. See msg555 and neal_wu's code in the practice rooms for implementations of this.

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(N²). To explain the concept, we will create a 2-D array called dp. dp[cur][0] represents the maximum score we can achieve after answering the cur-th question without receiving the bonus. dp[cur][1] 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][0] = points[cur] + max(dp[cur-1][0], dp[cur-1][1]);
2. dp[cur][1] = cumsum[cur] + bonuses[cur] + max(dp[cur-tokensNeeded][1], max(dp[cur-tokensNeeded-1][0], dp[cur-tokensNeeded-1][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][1] 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][0] and dp[N][1]. 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).