
Match Editorial 
SRM 354Thursday, 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. II 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

II 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[N1][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[i1][7];
d[i][1]=d[i1][2]+d[i1][4];
d[i][2]=d[i1][1]+d[i1][3]+d[i1][5];
d[i][3]=d[i1][2]+d[i1][6];
d[i][4]=d[i1][1]+d[i1][5]+d[i1][7];
d[i][5]=d[i1][2]+d[i1][4]+d[i1][6]+d[i1][8];
d[i][6]=d[i1][3]+d[i1][5]+d[i1][9];
d[i][7]=d[i1][4]+d[i1][8]+d[i1][0];
d[i][8]=d[i1][5]+d[i1][7]+d[i1][9];
d[i][9]=d[i1][6]+d[i1][8];
d[i][0]=d[i1][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 Breadthfirst 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;
}
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[N1][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[N1][M1][K1] (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[N1][M2][K2] (we can't put other rooks on the first row and on the columns with the placed rooks) multiplied by M*(M1)/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[N2][M1][K2] (we can't put other rooks on the rows and the column with the placed rooks) multiplied by M*(N1) (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[N1][M][K] +
A[N1][M1][K1] * M +
A[N1][M2][K2] * M * (M1) / 2 +
A[N2][M1][K2] * M * (N1)
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