SRM 520

Match Summary

Round Overview
Discuss this match

Welcome to the SRMEditorialPhase of SRM 520! This is the first match after TCO 2011 Championship Round. The onsite coders still had the mood to compete because most of them participated in this match. Single Round Matches prove to be very popular among competitive programmers, as there were 1980 coders that showed their best in this match even with delayed email reminders. The theme of this SRM is SRM itself, featuring 5 problems about 5 different phases of a typical SRM. What a recursive contest!

In Division 1, the coders faced 3 problems about arranging their best strategy in coding phase, counting the number of different room summaries, and reconstructing the challenge phase. Only 2 coders were able to solve all 3 problems. The first place went to lyrically, who did a successful 1000-250-500 strategy. wata earned the second spot thanks to his 250-1000-500 strategy. Finally, the third place went to tourist who showed us an outstanding speed in solving the 250- and 500-pointers.

Division 2 coders faced an equally interesting set of problems. It was about counting tougher competitors in their room, arranging their best strategy in coding phase, and counting the number of different division summaries. jpaulson won this Division 2 SRM thanks to his consistent speed in 3 problems. The second place went to lilingxiao. mr.white.cobra earned the third spot and immediately became a yellow coder. Congratulations to all winners!

I would like to thank to mystic_tc for helping me finalize the problems, rng_58 for testing the problems, and PabloGilberto for correcting language errors in problem statements. I am also very excited to know that this is the first SRM [[rng_58]] moderate as our new algorithm admin!

SRMRoomAssignmentPhase

Used as: Division Two - Level One:

This problem is pretty straightforward. It is an example of a simulation problem. Just sort the ratings and then simulate the room assignment exactly as described in problem statement, in descending order of the ratings, and you are done. Here is a sample code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int countCompetitors(int[] ratings, int K) {
  int N = ratings.length;
  int myRating = ratings[0];
  Arrays.sort(ratings);

  int[] room = new int[N];

  int k = 1;
  int myRoom;
  for (int i = N - 1; i >= 0; i--) {
    if (ratings[i] == myRating)
      myRoom = k;
    room[i] = k;
    k++;
    if (k > K)
      k = 1;
  }

  int res = 0;
  for (int i = 0; i < N; i++)
    if (room[i] == myRoom && ratings[i] > myRating)
      res++;
  return res;
}

This is sufficient to solve the problem. Of course, there is an elegant solution.

The Elegant Solution

Let X be the number of coders who have greater ratings than yours. Then, the answer is simply X/K, rounded down.

Why? Essentially, this problem asks for your rank (0-indexed) in your room. Let’s have the ratings sorted in descending order. If we simulate the room assignment as described, then coders in indices 0 through K-1 will be the highest (rank 0) rated coders in their rooms, coders in indices K through 2K-1 will be the second highest (rank 1) rated coders in their rooms, and so on.

In other words, we can split the input into blocks of K coders each, except possibly the last block which may contain less than K coders. All coders in the same block have the same rank in their rooms. Notice that the expression X/K is equal to the block number (0-indexed), which is identical to your rank.

1
2
3
4
5
6
7
public int countCompetitors(int[] ratings, int K) {
  int X = 0;
  for (int i = 1; i < ratings.length; i++)
    if (ratings[i] > ratings[0])
      X++;
  return X / K;
}

Exercise

Your rank is X/K. What is your room number?

SRMCodingPhase

Used as: Division Two - Level Two:

Used as: Division One - Level One:

Like other usual D1-Easy/D2-Medium problem, the key to solving this problem is the old, magical brute force!

Suppose you have decided which problems you want to solve. So, the problem that remains is how to distribute the points of luck such that you can solve all of them in 75 minutes. There are at least two ways to do this.

The Greedy Way

First, note that the best strategy is to use all points of luck, unless the time to solve each problem has been reduced to 1 minute. How to distribute the luck, then? Remember that:

• 1 minute in the first problem costs you 2 points,

• 1 minute in the second problem costs you 4 points, and

• 1 minute in the third problem costs you 8 points.

Each point of luck saves you 1 minute and saves you either 2, 4, or 8 points. It is obvious that you want to save the largest points. So, you can always spend the point of lucks on the problem with the largest cost until the time to solve the problem is decreased to 1 minute, or until you run out of points of luck. If there are remaining points of luck, use them on the problem with the next largest cost, and so on. It is optimal. See bmerry’s in-contest solution for a sample implementation.

The Brute Force Way

Didn’t I say that the key to solve this problem is brute force? If you read the constraints carefully, you will notice that the maximum points of luck is just 100. There are only 3 problems, so you can just brute force all ways to distribute the points of luck; there are at most roughly 100^3 ways which will fit in the time limit easily.

--

Okay, back to the original problem. The only remaining problem is how to choose which problems to solve. Remember the key: brute force. There are only 3 problems. On each problem there are two options: either you solve it or not. So, there are 2^3 ways to choose which problems to solve. Overall, the complexity is O(2^N x M^3), where N is 3 and M is 100 in this particular problem.

Note that because we use brute force in both steps (choosing problems and distributing points of luck), we can swap the steps and still get the same result, but with cleaner code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int countScore(int[] points, int[] skills, int luck) {
  int best = 0;

  for (int a = 0; a < skills[0] && a <= luck; a++)
    for (int b = 0; b < skills[1] && a + b <= luck; b++)
      for (int c = 0; c < skills[2] && a + b + c <= luck; c++) {
        int t[] = {
          skills[0] - a,
          skills[1] - b,
          skills[2] - c
        };
        int w[] = {
          2,
          4,
          8
        };

        for (int mask = 0; mask < 1 << 3; mask++) {
          int totalTime = 0, totalScore = 0;
          for (int i = 0; i < 3; i++)
            if ((mask & (1 << i)) > 0) {
              totalTime += t[i];
              totalScore += points[i] - w[i] * t[i];
            }
          if (totalTime <= 75)
            best = Math.max(best, totalScore);
        }
      }
  return best;
}

I don’t Like Brute Force

If you are tired doing brute force and want “more interesting” algorithm to solve this problem, don’t worry, there is a DP solution. Let’s define dp[P][T][L] as the maximum score we can obtain considering the first P problems, such that there are T minutes left and L points of luck left. The DP recurrence is left as an exercise for the readers. If you get stuck, please consult Chmel_Tolstiy’s solution.

Warning!

Don’t let this problem mislead you! To decrease the amount of time you need to solve a problem in real SRMs, you have to practice a lot, instead of relying on your luck. Really!

SRMSystemTestPhase

Used as: Division Two - Level Three:

This is a counting problem. Problems of this type, i.e., counting the number of objects, are usually to be solved using dynamic programming. To solve a DP problem, we must define its state and recurrence.

The DP State

Consider the way the coders are sorted in a scoreboard. They are sorted in decreasing order of the number of passed solutions, and if tie, in ascending order of the number of challenged solutions. Intuitively, we must keep track how many passed and challenged solutions so far. It turns out to that to decide the outcome of the solutions for a coder, we only have to keep the number of passed and challenged solutions for the coder in the previous rank.

Let’s formalize the state of a subproblem. We define dp[i][p][c] as the number of different scoreboards considering only coders [i … N-1], such that the (i-1)th coder has p passed solutions and c challenged solutions. The answer to the original problem would be dp[0][3][0]. Why? Because in any valid scoreboard, the ordering is still valid when we insert a dummy coder with 3 passed solutions and no challenged solutions above the first ranked (0-th) coder.

The DP Recurrence

Back to dp[i][p][c]. We have fixed the outcome of the solutions for the (i-1)th coder. Now, enumerate all possible outcomes of the solutions for the i-th coder. For example, if description[i] is “NYN”, then all possible outcomes for this coder are (X, passed, X), (X, failed, X), and (X, challenged, X). However, only several of them are valid, depending on the number of passed and challenged solutions for the (i-1)th coder (which are p and c). Let p’ be the number of passed solutions for the i-th coder, and c’ be the number of challenged solutions for the i-th coder. According to the rule, the outcome is valid only if p’ < p or (p = p’ and c’ ? c).

After determining an outcome for the i-th coder, there is a subproblem left, i.e. counting the number of different scoreboards considering only coders [i+1 … N-1], such that the i-th coder has p’ passed solutions and c’ challenged solutions. This is exactly dp[i+1][p’][c’]. So, the final recurrence for this DP is:

1
2
3
4
dp[i][p][c] = sum {
    dp[i + 1][p_j][c_j], where p_j < p or(p_j == p and c_j >= c)
  },
  for 1 <= j <= M

where M is the number of possible outcomes, p_j is the number of passed solutions in the j-th outcome, and c_j is the number of challenged solutions in the j-th outcome.

The base case is:

1
2
dp[N][a][b] = 1,
  for 0 <= a <= 3, 0 <= b <= 3

because those states represent an empty scoreboard, and there is 1 way to create an empty scoreboard: do nothing.

The Implementation

The tricky part in implementing this DP is how to enumerate all possible outcomes for the i-th coder efficiently. You could create a separate recursive function to visit all possible outcomes, but I find it is simpler to use three nested loops, each iterating from 0 to 2, inclusive. If description[i][k] = ‘Y’, they represent the 3 possible outcomes for each problem (passed, challenged, or failed). If description[i][k] = ‘N’, simply ignore the second and the third iteration. Please consult the below code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int countWays(String[] description) {
  int N = description.length;
  int[][][] dp = new int[N + 1][4][4];
  for (int p = 0; p <= 3; p++)
    for (int c = 0; c <= 3; c++)
      dp[N][p][c] = 1;

  for (int i = N - 1; i >= 0; i--)
    for (int p = 0; p <= 3; p++)
      for (int c = 0; c <= 3; c++) {
        int[] opt = new int[3];
        for (opt[0] = 0; opt[0] < 3; opt[0]++)
          for (opt[1] = 0; opt[1] < 3; opt[1]++)
            for (opt[2] = 0; opt[2] < 3; opt[2]++) {
              // 0 : passed / not submitted
              // 1 : challenged
              // 2 : failed

              int p_j = 0, c_j = 0;
              boolean valid = true;

              for (int k = 0; k < 3; k++) {
                if (description[i].charAt(k) == 'Y') {
                  if (opt[k] == 0) p_j++;
                  else if (opt[k] == 1) c_j++;
                } else if (opt[k] != 0)
                  valid = false;
              }

              if (!valid) continue;

              if (p_j < p || (p_j == p && c_j >= c))
                dp[i][p][c] = (dp[i][p][c] + dp[i + 1][p_j][c_j]) % MOD;
            }
      }
  return dp[0][3][3];
}

SRMIntermissionPhase

Used as: Division One - Level Two:

Similar to SRMSystemTestPhase, we need dynamic programming approach to solve this problem. Unlike the previous problem, this problem requires two DPs. Both DP states should be quite easy to spot by high-rated coders. However, most coders found that the implementation is quite tricky and not that easy.

To simplify the DP implementation of this problem, we assume that points, description, and each element of description are 1-indexed.

Ready? Let’s begin with an obvious DP state.

The First DP

Define dp[i][j] as the number of different scoreboards, considering only coders [i … N], such that the i-th coder had total score of j. There are many ways for the i-the coder to have total score of j, call it ways[i][j]. Now, consider the (i+1)th coder. According the rule, since all scores are different and the coders are sorted in descending order of their total scores, the possible total score for this coder is between 0 and j-1, inclusive. After determining the total score of the i-th coder, what remains is to count the number of different scoreboards, considering only coders [i+1 … N], such that the (i+1)th coder has total score of 0 through j-1. So, the value of dp[i][j] is:

1
dp[i][j] = ways[i][j] * (dp[i + 1][0] + dp[i + 1][1] + ...+dp[i + 1][j - 1])

Unfortunately, this recurence seems to exceed the time limit. So, let’s simplify the recurrence. Redefine dp[i][j] as the number of different scoreboards, considering only coders [i … N], such that the i-th coder has total score of *at most* j. There are two cases for the i-th coder:

• He had total score of at most j-1. The number of ways dp[i][j-1].

• He had total score of exactly j. There are ways[i][j] to have this total score. Then, the total score for the (i+1)th coder must be at most j-1. The number of ways is ways[i][j] * dp[i+1][j-1].

Thus, the DP recurrence for this new version becomes:

1
dp[i][j] = dp[i][j - 1] + ways[i][j] * dp[i + 1][j - 1]

This new version of DP runs in O(N x MAX_SCORE) time, which fits in the time limit.

The Second DP

The remaining step is to fill the values for ways[i][j]. We will also use DP for this step. Let’s extend the dimension into ways[i][k][j]. It is the number of ways for the i-th coder to have total score of j, considering only the first k problems. Let minScore and maxScore be the minimum and the maximum possible score for the coder’s k-th problem, respectively. There are two cases:

• description[i][k] = ‘Y’. Then, minScore = 1 and maxScore = min(j, points[k]).

• description[i][k] = ‘N’. Then, minScore = maxScore = 0.

Let the score for the k-th problem of the i-th coder be x. After fixing the score for the k-th problem, what remains is to count the number of ways for the i-th coder to have total score of j-x, considering only the first k-1 problems. This is ways[i][k-1][j-x]. So, the recurrence for ways[i][k][j] is then:

ways[i][k][j] = sum {ways[i][k-1][j-x]} for all minScore <= x <= maxScore

This recurrence will also obviously exceed the time limit. Let’s simplify it in the similar way to our first DP. Redefine ways[i][k][j] as the number of ways for the i-th coder to have total score of *at most* j, considering only the first k problems. There are two cases for the i-th coder:

• He scored at most j-1 on the first k problems. The number of ways is ways[i][k][j-1].

• He scored exactly j on the first k problems. Consider the k-th problem. His score on this problem could be between minScore and maxScore, inclusive. What remains is to count the number of ways for the i-th coder to have total score in [j-maxScore … j-minScore], considering only the first k-1 problems. This is exactly ways[i][k-1][j-minScore] - ways[i][k-1][j-maxScore-1] (prove it!).

So, what is the number of ways for the i-th coder to have total score of *exactly* j? It is ways[i][3][j] - ways[i][3][j-1].

Finally, the full DP recurrences for this problem are:

1
2
dp[i][j] = dp[i][j - 1] + (ways[i][3][j] - ways[i][3][j - 1]) * dp[i + 1][j - 1]
ways[i][k][j] = ways[i][k][j - 1] + (ways[i][k - 1][j - minScore] - ways[i][k - 1][j - maxScore - 1])

And, the base cases are:

1
2
3
4
5
6
dp[N + 1][j] = 1,
  for all j >= -1(assume that there is a dummy last coder with total score of -1, the lowest score)
ways[i][0][j] = 1,
  for all i, j >= 0
ways[i][0][-1] = 0,
  for all i

The Final Answer

The answer for this problem would be dp[1][points[1]+points[2]+points[3]], i.e., the number of different scoreboards, considering coders [1 … N] (all coders), such that the first coder had total score of at most the maximum possible score.

The Implementation

Phew, we have finally define the state and recurrences for our DPs which fit in the time limit. Can we implement them directly? Unfortunately no, because both DP tables require more than 64 MB, the current TopCoder SRM memory limit. Let’s use a small DP technique called rolling table/flying table then. Notice that dp[i][?] only depends on dp[i-1][?]. Similary, ways[?][k][?] only depends on ways[?][k-1][?]. We can keep only the last two values for the corresponding dimension of both tables. We will represent the current index as i&1 and the previous index as (i-1)&1. So, dp[i&1][?] and ways[?][k&1][?] depend on dp[(i-1)&1][?] and ways[?][(k-1)&1][?], respectively.

There is another issue though. To avoid using cumbersome ifs, we defined index of -1 in both DPs. However, most programming languages don’t allow negative indices, so we shift all indices of the correspending dimension by +1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public int countWays(int[] points, String[] description) {
  // make all inputs 1-indexed

  int[] oldp = points;
  points = new int[] {
    0,
    oldp[0],
    oldp[1],
    oldp[2]
  };

  String[] oldd = description;
  description = new String[oldd.length + 1];
  for (int i = 1; i <= oldd.length; i++)
    description[i] = " " + oldd[i - 1];

  // start the algorithm

  int N = description.length - 1;
  int M = points[1] + points[2] + points[3];

  int[][][] ways = new int[N + 1][2][M + 2];

  for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= M; j++)
      ways[i][0 & 1][j + 1] = 1;
    for (int k = 1; k <= 3; k++)
      for (int j = 0; j <= M; j++) {
        int minScore = 0, maxScore = 0;
        if (description[i].charAt(k) == 'Y') {
          minScore = 1;
          maxScore = Math.min(j, points[k]);
        }
        ways[i][k & 1][j + 1] = (ways[i][k & 1][j - 1 + 1] + ways[i][(k - 1) & 1][j - minScore + 1]) % MOD;
        ways[i][k & 1][j + 1] = (ways[i][k & 1][j + 1] - ways[i][(k - 1) & 1][j - maxScore - 1 + 1] + MOD) % MOD;
      }
  }

  int[][] dp = new int[2][M + 2];

  for (int j = -1; j <= M; j++)
    dp[(N + 1) & 1][j + 1] = 1;

  for (int i = N; i >= 1; i--) {
    dp[i & 1][-1 + 1] = 0;
    for (int j = 0; j <= M; j++) {
      dp[i & 1][j + 1] = dp[i & 1][j - 1 + 1];
      long add = (long)(ways[i][3 & 1][j + 1] - ways[i][3 & 1][j - 1 + 1] + MOD) * dp[(i + 1) & 1][j - 1 + 1];
      dp[i & 1][j + 1] = (int)((dp[i & 1][j + 1] + add) % MOD);
    }
  }
  return dp[1 & 1][M + 1];
}

SRMChallengePhase

Used as: Division One - Level Three:

First of all, I must admit that rng_58, the tester of this round, deserves a partial credit for this problem. This problem was originally meant to have N <= 50. mystic_tc then invented an O(N^3) solution, but rng_58 still thought that the solution was trivial for a Hard, until he finally came up with an O(N^2) solution. Thus, N <= 2500 was implemented. It becomes a quite tough problem as only 2 coders were able to solve this problem.

The explanation below is based on rng_58’s solution.

Coders’ Classification

We can classify each of the N coders into one of:

• A “challenger”, coder that appears only in codersAttempted.

• A “challengee”, coder that appears only in codersChallenged.

• A “supercoder”, coder that appears both in codersAttempted and codersChallenged.

Note that those three weird words are just terms I use in this editorial. Uh, I couldn’t come up with a better terminology.

Learn by Examples

Suppose that there are 4 supercoders named A, B, C, and D, and they are indistinguishable (we still don’t care which is who). The only valid challenge attempt sequence for them is:

• A -> X (successful if X is a challengee, may be successful or unsuccessful otherwise)

• B -> A (successful)

• C -> B (successful)

• D -> C (successful)

• Y -> D (successful, Y is a challenger)

where (a -> b) means coder a attempts to challenge coder b.

If we introduce another challenger, W, into the challenge phase, there are several sequences of sequence attempts. One of them is:

• A -> X (successful if X is a challengee, may be successful or unsuccessful otherwise)

• B -> A (successful)

• W -> B (successful)

• C -> X (successful if X is a challengee, may be successful or unsuccessful otherwise)

• D -> C (successful)

• Y -> D (successful)

We can imagine the above sequence as a 2D table of size P x 2, where P is the number of challengers plus the number of supercoders. This table has these properties:

• Each challenger is present in the first column.

• Each challengee is present in the second column.

• Each supercoder is present in both columns. Moreover, if supercoder A is present in row x, column 1, then the supercoder must be present also in row y, column 2, where y > x.

Let’s tackle this problem by first counting the number of ways the supercoders can be placed in the table.

Yet Another DP Approach

In how many ways we can place the supercoders? We need dynamic programming to solve this. Let dp[a][b] be the number of ways to place b supercoders in an a x 2 table. Consider the first row in this table. There are 2 cases:

• The first row, first column doesn’t contain s supercoder. The number of ways is dp[a-1][b].

• The first row, first column contains a supercoder. We must place this supercoder again in the right column in one of the next (a-1) rows. This table also contains (b-1) other supercoders, so there are (a-b) available positions for this supercoder in the right column. The number of ways is (a-b) * dp[a-1][b-1].

The DP formula is then:

1
2
3
4
dp[0][0] = 1
dp[0][b] = 0,
  for all b > 0
dp[a][b] = dp[a - 1][b] + (a - b) * dp[a - 1][b - 1]

Putting Them Together

Suppose that the input contains Cr challengers, Ce challengees, and S supercoders. Note that if Cr < Ce, then it is impossible and we should return 0.

There are (Cr+S) challenge attempts in a sequence. There are dp[Cr+S][S] ways to place S supercoders in the sequence. So, assume that S rows of the (Cr+S) x 2 table have been filled with supercoders in the right column. That means S coders in the left column already have their challenge targets. Cr coders in the left column still don’t have their challenge targets. We can place Ce coders in the right column as their challenge targets in C(Cr, Ce) ways.

After that, Cr-Ce coders in the left column still don’t have their challenge targets. We have run out of challenge targets, so each of these coders unsucessfully challenged one of the other N-1 coders. There are (N-1)^(Cr-Ce) ways. Finally, we can arbitrarily permute the challengers, challengees, and the supercoders independently. The final answer for this problem is:

1
dp[Cr + S][S] * C(Cr, Ce) * (N - 1) ^ (Cr - Ce) * Cr! * Ce! * S!

Here is a sample resulting code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public int countWays(String[] codersAttempted, String[] codersChallenged) {
  String attempted = "";
  for (int i = 0; i < codersAttempted.length; i++)
    attempted += codersAttempted[i];
  String challenged = "";
  for (int i = 0; i < codersChallenged.length; i++)
    challenged += codersChallenged[i];

  int N = attempted.length(), Cr = 0, Ce = 0, S = 0;
  for (int i = 0; i < N; i++)
    if (attempted.charAt(i) == 'Y' && challenged.charAt(i) == 'Y')
      S++;
    else if (attempted.charAt(i) == 'Y')
    Cr++;
  else if (challenged.charAt(i) == 'Y')
    Ce++;

  if (Cr < Ce)
    return 0;

  int[][] comb = new int[N + 1][N + 1];
  for (int i = 0; i <= N; i++) {
    comb[i][0] = 1;
    for (int j = 1; j <= i; j++)
      comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
  }

  int[][] dp = new int[N + 1][N + 1];
  dp[0][0] = 1;
  for (int a = 1; a <= N; a++)
    for (int b = 0; b <= N; b++) {
      dp[a][b] = dp[a - 1][b];
      if (b > 0) {
        long add = ((long) dp[a - 1][b - 1] * (a - b)) % MOD;
        dp[a][b] = (int)((dp[a][b] + add) % MOD);
      }
    }

  long res = dp[Cr + S][S];
  res = (res * comb[Cr][Ce]) % MOD;
  for (int i = 1; i <= Cr; i++)
    res = (res * i) % MOD;
  for (int i = 1; i <= Ce; i++)
    res = (res * i) % MOD;
  for (int i = 1; i <= S; i++)
    res = (res * i) % MOD;
  for (int i = 1; i <= Cr - Ce; i++)
    res = (res * (N - 1)) % MOD;
  return (int) res;
}

Epilog

The main character in problem statements is Mr. Dengklek, who really introduced me to the world of programming contest. Who is the first person to introduce you to this exciting world? Please, thank to that person.