Match Editorial

Match summary

Unlike the previous SRM, the Division I problem set wasn't very hard. The difficulty of the "above average" Easy problem was compensated by the rather easy Hard, which gave more than 50 coders the chance to solve all three problems.

The top of the Division Summary after the Coding Phase was very narrow and the Challenge Phase significantly changed the coders' order. Petr won the match thanks to a last minute blind challenge and continued his majestic conquest of the TopCoder rating: 3753 - another new record! ACRush finished in second and bmerry held on to the third position.

Unexpectedly, a lot of coders in Division II solved a rather difficult Hard problem while the greedy Medium turned out to be a bit tougher. I-I wins, the newcomer Lapro finished second, and huacm16 took third.

The Problems

Value	250
Submission Rate	675 / 716 (94.27%)
Success Rate	650 / 675 (96.30%)
High Score	ashwin_topcoder for 249.10 points (1 mins 42 secs)
Average Score	219.75 (for 650 correct submissions)

The problem was pretty straightforward. To solve it you should process all the thimble swaps and calculate the ball position after each swap. Here is lordbogy's solution, which clearly illustrates this idea:

public int thimbleWithBall(string[] swp) { 
  int tp = 1; 
  foreach(string s in swp) { 
    int s1 = s[0] - '0'; 
    int s2 = s[2] - '0'; 
    if(s1 == tp) tp = s2; 
    else if(s2 == tp) tp = s1; 
  } 
  return tp; 
}

Value	600
Submission Rate	288 / 716 (40.22%)
Success Rate	86 / 288 (29.86%)
High Score	I-I for 579.59 points (5 mins 22 secs)
Average Score	292.15 (for 86 correct submissions)

Value	300
Submission Rate	499 / 574 (86.93%)
Success Rate	275 / 499 (55.11%)
High Score	bmerry for 285.71 points (6 mins 24 secs)
Average Score	187.72 (for 275 correct submissions)

This problem seemed more difficult than the usual Division 1 Easy or Division 2 Medium problem but, in fact, it didn't require a lot of effort to solve. The greedy works and the only nontrivial thing lies in the checking which valid dates can be obtained from the given date.

Let's consider the date "XX/YY" is given in the input. We should check "XX/YY" and "YY/XX" dates for it. The date "AA/BB" is a valid date in the US format if and only if AA is not greater than 12. This fact ensues from the constraint that each date in the input is a valid date in either US format or European format.

The entire algorithm for the problem is as follows: Generate all possible dates from the first date and choose the smallest one. For each subsequent date generate all possible dates from it, and chose the smallest one that is greater than the preceding. You can use bmerry's solution as the reference.

Value	1000
Submission Rate	263 / 716 (36.73%)
Success Rate	236 / 263 (89.73%)
High Score	LiveInSeoul for 969.97 points (5 mins 1 secs)
Average Score	721.78 (for 236 correct submissions)

This problem was a classical illustration of dynamic programming problems. The last digit of the password depends on the preceding digit only. So we can accumulate all passwords of length N ending with a digit D into one object and work with such accumulated objects.

More formally, let A[N][D] be the number of passwords of length N with a digit D on the end. Then A[N][D] equals the sum of such A[N-1][X] for whichever digits D and X are adjacent.

Here is LiveInSeoul's solution, which illustrates this idea:

  long long countPasswords(int N){ 
    long long d[50][20]; 
    int i; 
    for(i=0; i<=9; i++){ 
      d[1][i]=1; 
    } 
    for(i=2; i<=N; i++){ 
      d[i][0]=d[i-1][7]; 
      d[i][1]=d[i-1][2]+d[i-1][4]; 
      d[i][2]=d[i-1][1]+d[i-1][3]+d[i-1][5]; 
      d[i][3]=d[i-1][2]+d[i-1][6]; 
      d[i][4]=d[i-1][1]+d[i-1][5]+d[i-1][7]; 
      d[i][5]=d[i-1][2]+d[i-1][4]+d[i-1][6]+d[i-1][8]; 
      d[i][6]=d[i-1][3]+d[i-1][5]+d[i-1][9]; 
      d[i][7]=d[i-1][4]+d[i-1][8]+d[i-1][0]; 
      d[i][8]=d[i-1][5]+d[i-1][7]+d[i-1][9]; 
      d[i][9]=d[i-1][6]+d[i-1][8]; 
      d[i][0]=d[i-1][7]; 
    } 
    long long ans=0; 
    for(i=0; i<=9; i++){ 
      ans+=d[N][i]; 
    } 
    return ans; 
  }

Value	500
Submission Rate	464 / 574 (80.84%)
Success Rate	208 / 464 (44.83%)
High Score	kia for 491.68 points (3 mins 42 secs)
Average Score	396.73 (for 208 correct submissions)

"For every problem, there is a solution that is simple, neat, and wrong." - H. L. Mencken

Initially this problem had a greater upper limit for N. But the "57246" test broke down all the author's approaches and he was forced to reduce limits. The correct answer for the "57246" test is "65410" because we can do the following sequence of swaps: 57246 -> 57316 -> 27416 -> 61416 -> 65410. How to obtain such a result using some 'clever' algorithm? I don't know, in spite of several days of thinking. If you have an idea, you are welcome to post it on TopCoder's forum.

With the reduced constraints the problem can be solved with graph theory and any search algorithm. Another possible solution is a brute force with any reasonable optimization. In this editorial we will describe the first approach.

Let's build a graph where vertexes are the numbers from 0 to 1,000,000. Let's create an edge from vertex A to vertex B if the number B can be obtained from the number A by the one swap operation. The answer is the maximal number that is reached from the vertex N. Here is the Petr's solution that uses Breadth-first search algorithm for the graph bypassing.

public int findMaximum(int N) { 
    bool[] reachable = new bool[12000000]; 
    List<int> queue = new List<int>(); 
    reachable[N] = true; 
    int res = N; 
    queue.Add(N); 
    while (queue.Count > 0) 
    { 
      int cur = queue[queue.Count - 1]; 
      queue.RemoveAt(queue.Count - 1); 
      for (int p10 = 1; p10 <= cur; p10 *= 10) 
        for (int q10 = 1; q10 < p10; q10 *= 10) 
        { 
          int dp = (cur / p10) % 10; 
          int dq = (cur / q10) % 10; 
          if (dp > 0 && dq > 0) 
          { 
            int next = cur - dp * p10 - dq * q10 + (dp - 1) * q10 + (dq - 1) * p10; 
            if (!reachable[next]) 
            { 
              reachable[next] = true; 
              res = Math.Max(res, next); 
              queue.Add(next); 
            } 
          } 
        } 
    } 
    return res; 
  }

Value	900
Submission Rate	131 / 574 (22.82%)
Success Rate	105 / 131 (80.15%)
High Score	Petr for 878.75 points (4 mins 26 secs)
Average Score	556.53 (for 105 correct submissions)

This problem can be solved with dynamic programming. Let's have A[N][M][K] be the answer for the problem with N, M and K parameters. Let's consider the first row of the chessboard. There are four possibilities:

• The first row contains no rooks. In this case the answer is A[N-1][M][K] (we can't put rooks on the first row).
• The first row contains one rook that is not attacked by other rooks. In this case the answer is A[N-1][M-1][K-1] (we can't put other rooks on the first row and on the same column with the placed rook) multiplied by M (number of ways to put the rook on the first row).
• The first row contains two rooks. In this case the answer is A[N-1][M-2][K-2] (we can't put other rooks on the first row and on the columns with the placed rooks) multiplied by M*(M-1)/2 (number of ways to put two rooks on the first row).
• The first row contains one rook, which is attacked by other rook from the other row. In this case the answer is A[N-2][M-1][K-2] (we can't put other rooks on the rows and the column with the placed rooks) multiplied by M*(N-1) (number of ways to put the rook on the first row and select the second rook in the same column).

A[N][M][K] = 
    A[N-1][M][K] +
    A[N-1][M-1][K-1] * M + 
    A[N-1][M-2][K-2] * M * (M-1) / 2 +
    A[N-2][M-1][K-2] * M * (N-1)

public class RooksPlacement { 
  bool[, ,] got; 
  long[, ,] res; 
  const long MODULO = 1000001; 
   
  public int countPlacements(int N, int M, int K) { 
    got = new bool[N + 1, M + 1, K + 1]; 
    res = new long[N + 1, M + 1, K + 1]; 
    return (int) get(N, M, K); 
  } 

  private long get(int n, int m, int k) 
  { 
    if (n < 0 || m < 0 || k < 0) 
      return 0; 
    if (k == 0) 
      return 1; 
    if (n == 0 || m == 0) 
      return 0; 
    if (got[n, m, k]) 
      return res[n, m, k]; 
    long r = 
        (get(n - 1, m, k) + 
        m * (get(n - 1, m - 1, k - 1) + (n - 1) * get(n - 2, m - 1, k - 2)) + 
        m * (m - 1) / 2 * get(n - 1, m - 2, k - 2)) % MODULO; 
    got[n, m, k] = true; 
    res[n, m, k] = r; 
    return r; 
  } 


}