JOIN
 Match Editorial
SRM 354
Thursday, June 14, 2007

## 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

Thimbles
Used as: Division Two - Level One:
 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;
}

```

DateFormat
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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.

UnsealTheSafe
Used as: Division Two - Level Three:
 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;
}

```

RemissiveSwaps
Used as: Division One - Level Two:
 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;
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);
}
}
}
}
return res;
}

```

RooksPlacement
Used as: Division One - Level Three:
 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).
Finally, we get a formula:
```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)

```
Here is Petr's solution, which uses the formula above.
```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;
}

}

```

By Andrew_Lazarev
TopCoder Member