Monday, January 30, 2006 Match summary Single Round Match 286 presented a problem set headed by hard 1000pointers, which decided most part of match standings and were solved by few coders in each division. Division 1 was a land of challenges and failed solutions. Only six coders passed their solutions for the hard problem, out of 85 submissions. Petr, with the fastest correct submission for that problem, won by over 300 points over the second position, with three successful challenges for his record. kalinov followed, and 130 points later came marian, Eryx and tomek in a close group. In Division 2 only three coders scored above over 1000 points. Newcomers lapsedbird and NauCoder lead, very close each other, with 130 points over the next group: butler, mitnickcbc and Knith. The ProblemsCuttingPolesUsed as: Division Two  Level One:
The algorithm to implement was already described in the statement and all a solution needed just to implement it. Using a sort function to keep poles sorted by height (time constraints are generous for so little input) and using the fact that the average height of poles is an integer, a solution could be: int countCuts(int[] poles) { int avg = 0; for (int i=0; i<poles.length; i++) avg += poles[i]; // result is guaranteed to be an integer avg = avg / poles.length; Arrays.sort(poles); int cuts = 0; while (poles[poles.length1] > avg) { // plenty of execution time, iterate cutting & resorting poles[0] += poles[poles.length1]  avg; poles[poles.length1] = avg; Arrays.sort(poles); cuts++; } return cuts; }ExtraBall Used as: Division Two  Level Two: Used as: Division One  Level One:
We need to know what patterns have already been paid at the end of the game; and then compute the probability of matching each of the remaining prizes with just one ball to be released. The probability of winning the ith pattern in that ball can be obtained as 1/(75�balls.length)*prizes[i] for those patterns with exactly one unmatched cell, or zero otherwise (either because they have been already paid or they would need more than one ball to be released). To compute matched and unmatched cells a simple iteration could be performed, or bitmasks could also be used. Java code follows: double expectedPayout(int[] card, int[] balls, String[] patterns, int[] prizes) { Arrays.sort(balls); int maxpayout = 0; for (int i=0; i<patterns.length; i++) { int missing = 0; for (int j=0; j<card.length; j++) if (patterns[i].charAt(j) == 'X' && Arrays.binarySearch(balls, card[j]) < 0) missing++; if (missing == 1) maxpayout += prizes[i]; } return (double)maxpayout / (75.0balls.length); }MonomorphicTyper Used as: Division Two  Level Three:
Regardless the extension of the statement, the problem should be easily understood by anyone familiar to programming: it asked for inferring the type of an expression in a (typed) programming language, based on certain assumptions given as the �definitions�. Any compiler of a typed language (as all languages currently used in TopCoder competitions) performs this task for each constant, function call, operator application, etc. in a piece of source code. A great part of the problem complexity comes from parsing of the expression, which can be seen as a tree where function calls are nodes (with one or more children), and constants are its leaves. Parsing such an expression is a common example of use of stack automatas, and can be implemented either using recursion or a stack to keep track of depth in the tree that represents the expression (parenthesis nesting). Inferring the type of the expression requires to check each function and constant name against the definitions, and recurse this task to typecheck each of the subexpressions. For a constant to have type, it has just to be declared in the definitions. For a node to have type, it must hold that:
In Type Theory, these two rules are usually part of a monomorphic type system, usually being the simplest rules in typechecking.
The following is a concise and clear recusrive solution contributed by radeye: public class MonomorphicTyper { String[] tokens, defs; int at = 0 ; void msplit(String s) { StringTokenizer t = new StringTokenizer(s, ":(),!", true); tokens = new String[t.countTokens()]; int i = 0; while(t.hasMoreTokens()) tokens[i++]=t.nextToken(); } String mustMatch(String s) { for (String d : defs) if (d.startsWith(s)) return d.substring(s.length()) ; return "" ; } String eval() { String r = tokens[at++] ; if (tokens[at].equals("(")) { r += tokens[at++] ; while (true) { r = r + eval() + tokens[at++] ; if (tokens[at1].equals(")")) break ; } } return mustMatch(r+":") ; } public String infer(String expression, String[] definitions) { msplit(expression+"!") ; defs = definitions ; return eval() ; } }BallGift Used as: Division One  Level Two:
To know the best place to seat in if all we have as input is the number of sheets of each color, we could enumerate all possible configurations computing which position wins the gift in each case, and then return the position with most winning configurations. The only parameters needed in a recursive function to perform the computation are the number of red, green and black sheets  note that the number of players in the given moment can be inferred as the total number of players minus the number of black sheets already used. Its return value can be a collection including a count of winning configurations for each sitting position (its size will be the number of players still playing). We can make the first position in such return value to represent the player that holds the ball in that turn, and subsequent positions enumerated in the order the ball is being passed by. The function will then we rearrange the return values from recursive calls depending on the colors that can be use in current turn: for instance, a green sheet will rotate one position the values in that collection. A na�ve recursive function will timeout with the given constraints, but memoization or a dynamic programming approach will work. One additional warning is that 32bit integers would overflow in the largest inputs. Once the right parameters are chosen for this recursive function, the "only" difficulty is to properly combine each of the results from recursive cases  find the details in the following Java solution: // parameters: int players, int green, int red, int black long dp[][][][]; dp = new long[green + 1][red + 1][black + 1][players]; for (int g = 0; g <= green; g++) { for (int r = 0; r <= red; r++) { for (int b = 0; b <= black; b++) { int pl = players + b  black; if (r + g + b == 0) { // if no sheets in the ball, player at position 0 wins dp[g][r][b][0] = 1; for (int i = 1; i < pl; i++) dp[g][r][b][i] = 0; } else { if (b > 0) { // players are copied from recursive call, // but current gets eliminated from circle dp[g][r][b][0] = 0; for (int i = 0; i < pl  1; i++) dp[g][r][b][i + 1] += dp[g][r][b  1][i]; } if (g > 0) // the counts for all players are just cycled // with 1position shift for (int i = 0; i < pl; i++) dp[g][r][b][(i + 1) % pl] += dp[g  1][r][b][i]; if (r > 0) // the circle order is reversed, so the array with counts for (int i = 0; i < pl; i++) dp[g][r][b][i] += dp[g][r  1][b][pli1]; } } } } // All we need to complete this solution is to return the least index that gives // a maximum in dp[green][red][black][p] for p=0..players1.InfiniteSoup Used as: Division One  Level Three:
This problem required to solve two different tasks. The first and easier step was to realize that the 200*200 possible rays actually describe much fewer different sequences in the grid g: two rays crossing (x1,y1) and (x2,y2) will spell out the same sequence if and only if x1=x2 mod c and y1=y2 mod r, where c and r are the number of columns and rows in g, respectibely. Many coders quickly found this fact and were tempted to submit really fast solutions, in which words were searched on the sequences generated using string search functions provided by their standard libraries. However, such functions usually implement a search with O(nm) runtime, where n is length of sequence and m the length of word being searched. Such runtime timed out for large inputs in the problem, and that is the reason why so many solutions failed and only 7% out of a relatively high count of submissions passed system testing. An efficient method for this type of search is to use infer some information on the structure of the word being searched, so as to avoid �backtracking� to the beginning of the string every time a character is not matched. A well known solution for this task is known as KnuttMorrisPratt algorithm: it bases the search on knowing the how suffixes of initial parts of the string are actually initial parts of the same string. This allows to, when finding a mismatch while walking on the sequence, to recover the search from any of the other possible points where search could be, if starting from some an index greater than the one already failed. For those familiar with theory of languages, an instance of KMP algorithm for a given search word can be seen as a (deterministic) finite automata, or DFA, with one state for each letter in the word. Each state in this DFA has to exits: one for the matching character corresponding to that state, and one to jump back to a previous state, which depends on the abovementioned string prefixes  this replaces the backtracking to the beginning of word in the quadratic algorithm mentioned, and must be performed as long as current letter still do not match, up to the beginning of the word. Thinking a nondeterministic automata (NFA) approach, that DFA can be seen as a translation from the straightforward NFA solution deterministic version. The Wikipedia contains several search algorithms. A very clear explanation of KMP algorithm can also be found here See also tomek's as for a solution written during the contest. 
