Match Editorial

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

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

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)

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);
  }

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() ;
    }
  }

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.

  // 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.

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.