Wednesday, March 26, 2008 Match summaryIn division 1, coders were faced with an easy problem that required careful case analysis, and DPbased 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 ProblemsSquareDigitNumbersUsed as: Division Two  Level One:
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. StreetWalkingUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 + (XY)*walkTime; else if((X+Y)%2 == 0) return X*sneakTime; else return (X1)*sneakTime + walkTime; Of course in the above code, one must ensure that you use 64bit variables to handle cases where overflow may happen. TriviaGameUsed as: Division Two  Level Three:
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. SkyscrapersUsed as: Division One  Level Two:
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 (N1, L1, R). Similarly, if we place the building on the right, we can move to the new problem (N1, L, R1). In the remaining N2 cases to place the building, we can't see this building, and so move to (N1, 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(N1, L1, R) + (long)dp(N1, L, R1) + (long)(N2)*(long)dp(N1, L, R)) % 1000000007); return dptable[N][L][R]; } Using combinations, it is actually possible to solve the problem in O(N^{2}) time. See msg555 and neal_wu's code in the practice rooms for implementations of this. PubTriviaUsed as: Division One  Level Three:
Due to the large constraints, we need an algorithm that runs faster than O(N^{2}). To explain the concept, we will create a 2D array called dp. dp[cur][0] represents the maximum score we can achieve after answering the curth question without receiving the bonus. dp[cur][1] represents the maximum score we can achieve by receiving a bonus on the curth question. The recurrence relation can then be seen as follows (ignoring outofbounds errors):
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[itokensNeeded][1] term), or we can get question (itokensNeeded) wrong (and thus take the best value from question (itokensNeeded1) ). In equations above cumsum[cur] means the total number of points for consecutive tokensNeeded questions between (curtokensNeeded+1)th and curth, 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[i1] + points[i]; int[] cumsum = new int[N+1]; for(int i=tokensNeeded, i<=N; i++) cumsum[i] = cs[i]  cs[itokensNeeded]; 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). 
