Match Editorial
SRM 286
Monday, January 30, 2006

Match summary

Single Round Match 286 presented a problem set headed by hard 1000-pointers, 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 Problems

CuttingPoles
Used as: Division Two - Level One:
 Value 250 Submission Rate 324 / 360 (90.00%) Success Rate 252 / 324 (77.78%) High Score lei0883 for 249.29 points (1 mins 31 secs) Average Score 200.81 (for 252 correct submissions)

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.length-1] > avg) {
// plenty of execution time, iterate cutting & resorting
poles[0] += poles[poles.length-1] - avg;
poles[poles.length-1] = avg;
Arrays.sort(poles);
cuts++;
}
return cuts;
}
```

ExtraBall
Used as: Division Two - Level Two:
 Value 500 Submission Rate 214 / 360 (59.44%) Success Rate 168 / 214 (78.50%) High Score DaiYan for 448.50 points (9 mins 51 secs) Average Score 290.20 (for 168 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 314 / 324 (96.91%) Success Rate 282 / 314 (89.81%) High Score John Dethridge for 242.62 points (4 mins 59 secs) Average Score 181.70 (for 282 correct submissions)

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 i-th 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.0-balls.length);
}
```

MonomorphicTyper
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 46 / 360 (12.78%) Success Rate 5 / 46 (10.87%) High Score lapsedbird for 643.64 points (24 mins 9 secs) Average Score 523.20 (for 5 correct submissions)

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:

• there is a definition for that name,
• the parameter count in that definition matches the actual usage in the expression, and
• recursively each of the nodes have type and match the type declared for each parameter in the definitions.

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[at-1].equals(")")) break ;
}
}
return mustMatch(r+":") ;
}
public String infer(String expression, String[] definitions) {
msplit(expression+"!") ;
defs = definitions ;
return eval() ;
}
}
```

Used as: Division One - Level Two:
 Value 600 Submission Rate 115 / 324 (35.49%) Success Rate 44 / 115 (38.26%) High Score Egor for 512.80 points (12 mins 8 secs) Average Score 333.45 (for 44 correct submissions)

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 32-bit 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 1-position 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][pl-i-1];
}
}
}
}
// 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..players-1.

```

InfiniteSoup
Used as: Division One - Level Three:
 Value 1000 Submission Rate 85 / 324 (26.23%) Success Rate 6 / 85 (7.06%) High Score Petr for 807.70 points (14 mins 36 secs) Average Score 617.61 (for 6 correct submissions)

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 Knutt-Morris-Pratt 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.

By ged
TopCoder Member