Tuesday, June 21, 2005 Match summary Turnout was high for SRM 248, as for the first time in a couple of years, there was money up for grabs in a TopCoder SRM! This match broke the previous record of most reds in an SRM. Tonight's final count, 44, exceeded the previous record of 32 from SRM 227. In the coding phase, SnapDragon came out of quasiretirement and led a large group of Division 1 coders who solved all 3 problems. However, the challenge phase provided lots of activity with tomek picking up 5 successful challenges to pull ahead and win Division 1. Rounding out the top 5 were SnapDragon, krijgertje, antimatter and Yarin. In Division 2, firsttimer yuhch123 took first place honours followed by nikola_borisof1, relic, firsttimer hou and sorinelm. The ProblemsSyllableCounterUsed as: Division Two  Level One:
To determine the number of syllables in a word, we have to identify groups of vowels. This is easy to do with a single loop over the letters in the word. If you encounter a vowel, increment the count of syllables, and skip to the first letter after this group that's not a vowel. In pseudocode: for i:1 to length word if word[i] is a vowel increment numSyllables while word[i] is a vowel && i ≤ length word i++ It is possible to solve this problem in one line of Java code. I'll leave someone to start a "Shortest SRM 248 Div 2 250" thread to deal with this issue. WordPatternUsed as: Division Two  Level Two: Used as: Division One  Level One:
This problem provided the greatest challenge material, as a number of coders forgot to handle the case when the input was only 1 character long in their closedform solutions. For those coders who chose to solve the problem using simple memoization or a BFS, this turned out to not be an issue. As mentioned in the problem statement, the procedure to create the actual pattern was part of the problem. This isn't very difficult. The pattern is constructed as follows: write the word and it's reverse, overlapping the first character word = word[2..length word] // i.e. remove first character for iter:1 to length word  1 write down word and it's reverse, overlapping the first character as the first and last row in the pattern word = word[2..length word] // i.e. remove first character Then, the number of ways to spell out the original word can be found by doing a very simple Breadth First Search (BFS). Starting at the center of the pattern, work outwards toward the fringe. At each location, the number of ways of getting to that location is simply equal to the sum of the number of ways of getting to the one or two locations that could be predecessors. For instance, in the upper right quadrant, the number of ways of getting to a location is equal to the sum of the number of ways of getting to the location to its left and the number of ways of getting to the location below it. Finally, the return value is simply the number of ways of reaching all the fringe squares. Many people discovered the closedform solution to this problem. This is given by: if word.length < 2 return 1 else return (1 << (length word + 1))  4; The proof is left as an exercise for the reader. :) BitStringsUsed as: Division Two  Level Three:
It may appear that this problem can be solved in a greedy manner. Two simple approaches come to mind. First, always attempt to form the shortest strings possible before attempting larger strings. However, this approach is flawed. Consider the case where 2 0s and 5 1s are available, and we have to make strings from the set {00, 011, 0111}. Then, if we were to greedily form the first string "00", we wouldn't have enough 0s to form any other strings, and our solution would return 1. Clearly, we can do better, by forming the second and third strings. Another greedy approach is to always attempt to form strings that consume the least number of the digit which are in shortest supply. That is to say, if you have less 0s than 1s, you would attempt to construct strings that use a minimum number of 0s and in case of ties, break by the number of 1s. This approach is also flawed. Consider the case where you have 5 0s and 4 1 at your disposal, and the string list is {100000, 110, 110}. Noting that you have fewer 1s than 0s, you would construct the string "100000", since this consumes the least number of 1s. But now, you have no 0s left to construct the other strings. The task can be solved with Dynamic Programming. First, we process the set of strings given to us and for each string, we store the number of 0s and 1s that appear in that string. In pseudo code, for i:1 to number of strings for j:1 to length string[i] if character j in string i = 0 C0s[i]++; if character j in string i = 1 C1s[i]++; Then, consider an array A, with dimensions [MAX_ZEROES][MAX_ONES]. The i,j entry of A represents the number of bitstrings that can be formed using i 0s and j 1s. So our algorithm is as follows (Note that we need to use an auxilliary array, B): Initialze A to all 0 for i:1 to number of strings Initialize B to all 0 string s = strings[i] // Consider s alone if C0s[i] ≤ numZeroes and C1s[i] ≤ numOnes B[C0s[i]][C1s[i]] = 1 // Now, try making string s from everywhere we have previously reached for n0:0 to numZeroes for n1:0 to numOnes if A[n0][n1] > 0 // We can get here if n0 + C0s[i] ≤ numZeroes and // We have enough 0s n1 + C1s[i] ≤ numOnes and // We have enough 1s A[n0][n1] + 1 > A[n0 + C0s[i]][n1 + C1s[i]] Update [n0 + C0s[i]][n1 + C1s[i]] in B Copy B into A The idea is to attempt to form new strings from positions that we can already reach from previous strings. So, if we can make X strings using i 0s and j 1s, and we're considering a string with u 0s and v 1s, it is obvious that we will reach the cell i + u, j + v in the array. Then, we only update the cell at that position if making this string actually improves the answer we already have stored there. The runtime of the above algorithm is on the order of MAX_STRINGS*MAX_ZEROES*MAX_ONES. Note that with the constraint of 20 strings, this problem could actually be solved using simple bruteforce, by using bitmasks and iterating from 0 to 2^(# of bitstrings), which is the approach taken by most coders who solved this problem. ContractWorkUsed as: Division One  Level Two:
Once again, it may appear that a greedy approach could work, but this is incorrect. Consider a simple example of only 3 tasks and 2 companies, with the following cost table: {"1 1 1", "10 10 100"}. If one attempts to perform each task greedily, i.e. choosing the cheapest company for each task, then tasks 1 and 2 would be assigned to company 1, since it has a cost of 1 for each of those tasks, which is less than what company 2 will charge. But now, we are FORCED to contract task 3 to company 2, since company 1 has already performed 2 consecutive tasks. Thus, we incur a cost of 100, bringing our total cost to 102. It is obvious that the correct minimum cost here is 12 (company 2 must be given either task 1 or 2, and the remaining tasks are performed by company 1). To solve this problem, we can use memoization. Create an array cache[NUM_TASKS][NUM_COMPANIES][NUM_COMPANIES] and used the following function: int getAnswer(int curTask, int beforePrev, int prev) if curTask == NUM_TASKS return 0 if cache[curTask][beforePrev][prev] > 1 return cache[curTask][beforePrev][prev] // Obviously, check range int best = INF for i:0 to NUM_COMPANIES if beforePrev == prev && prev == i continue; // 3 in a row best = min(best, cost[i][curTask] + getAnswer(curTask + 1, prev, i) cache[curTask][beforePrev][prev] = best The idea here is as follows: If you can discover a function to return the optimal cost of performing the current task, then it is easy to use the same function to determine the total cost. So we just try all the possibilities for performing the current task and recursively calculate the optimal answer for the remaining subproblem. Naturally, we use memoization to speedup the process. This problem can also be solved using a DP approach, using straight iteration rather than a recursive formulation. ClockManagementUsed as: Division One  Level Three:
By lbackstrom double recurse(timeLeft, diff, curTeam){ double ret = 0 foreach(number of seconds to set up i){ d = probability of curTeam winning (or tieing in the case of team B) if curTeam shoots after i seconds ret = max(ret,d) } return ret }As you can see, when it is A's turn to make a decision, A maximizes the return. When it is B's turn to make a decision, B minimizes the return. However, this is only the beginning of a solution. To make it work, we have to figure out how to determine d, add the base case, and then make it run fast. Calculating d above requires 3 recursive calls, based on the three possible outcomes of a shot: scoring, missing and getting a rebound, missing and losing possession. If we let a value of 0 represent team A, and 1 represent team B, and put the probabilities in 2D arrays p and r (for percentage and rebound), then we can calculate d as follows: //in order, the calls correspond to scoring, missing, and missing and rebounding d = (1recurse(timeLefti,diff+(curTeam==A?2:2),1curTeam)) * p[curTeam][i2] + (1recurse(timeLefti,diff,1curTeam)) * (1p[curTeam][i2]) * (1r[curTeam][i2]) + recurse(timeLefti,diff,curTeam) * (1p[curTeam][i2]) * r[curTeam][i2]Notice that the recursive function returns the probability of curTeam coming out on top. As a result, when the ball changes possession, you must subtract the probability from the recursive call from 1. For instance, the first recursive call above correlates to curTeam scoring, and the recursive call returns the probability that the other team will win (or tie for B). To convert this to the probability that curTeam will win, simply subtract it from 1. Next we have to add our base case. This is simply a matter of returning 1 when the game has 0 or 1 seconds left and curTeam is going to win, and 0 if curTeam is going to lose: if(timeLeft <=1){ if(diff > 0 && curTeam == A  diff ≤ 0 && curTeam == B)return 1; else return 0; }Finally, to make the solution run fast enough, we need to use memoization to cache the results. This amounts to saving the result of a recursive call for a particular (timeLeft,diff,curTeam) triple after it has been computed. Then, if the recursive function is ever called again with the same arguments, the results can be looked up in the table. antimatter's solution follows the approach outlined here quite closely. 
