JOIN
 Match Editorial
SRM 341
Saturday, March 10, 2007

## Match summary

In division 1, the easy problem was easier than usual, so most coders solved it quickly. In the coding phase, only ten coders found the solution to the hard problem, but nine of them failed the testing phase. The yellow coder, xhl_kogitsune, passed the systest and won the SRM for the first time.

In division 2, the hard problem was so tough that most coders failed to solve it. Only a new member, vanessa, managed to solve all 3 problems and won division.

# The Problems

ChangingString
Used as: Division Two - Level One:
 Value 250 Submission Rate 601 / 694 (86.60%) Success Rate 472 / 601 (78.54%) High Score vanessa for 248.25 points (2 mins 23 secs) Average Score 191.83 (for 472 correct submissions)

This is just a greedy problem. Obviously, to gain the minimal possible target the distance between each letter in A, after changed, and the corresponding letter in B must be 0 (if they are different from each other) or 1 otherwise.

We choose K letters in A that have K maximal distance with K corresponding letters in B and change them in that way.

Java code follows:

```public int distance(String A, String B, int K) {
int n = A.length();
int[] a = new int[n];
for(int i=0;i<n;i++) a[i] = Math.abs((int)A.charAt(i)-(int)B.charAt(i));
Arrays.sort(a);
int ans = 0;
for(int i=0;i<n-K;i++) ans+=a[i];
for(int i=n-K;i<n;i++) ans+=a[i] == 0 ? 1 : 0;
return ans;
}
```

KLastNonZeroDigits
Used as: Division Two - Level Two:
 Value 500 Submission Rate 573 / 694 (82.56%) Success Rate 478 / 573 (83.42%) High Score vanessa for 496.21 points (2 mins 29 secs) Average Score 385.37 (for 478 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 539 / 544 (99.08%) Success Rate 497 / 539 (92.21%) High Score mirosuaf for 249.66 points (1 mins 3 secs) Average Score 227.45 (for 497 correct submissions)

This one was easier than the usual Div1 Easy or  Div2 Medium problem. Considering the small constraint of N, most coders were confident in solving this with the iterative approach.

Java code follows:

```public String getKDigits(int N, int K) {
long f = 1;
for(long i=1;i<=N;i++)f *=i;
String s = String.valueOf(f);
while(s.endsWith("0")) s = s.substring(0, s.length() - 1);
return s.length() <= K ? s : s.substring(s.length() - K);
}
```

The problem will be a little tougher if the constraint of N is changed into 10^6.

LandAndSea
Used as: Division Two - Level Three:
 Value 1050 Submission Rate 26 / 694 (3.75%) Success Rate 1 / 26 (3.85%) High Score vanessa for 457.68 points (48 mins 19 secs) Average Score 457.68 (for 1 correct submission)
Used as: Division One - Level Two:
 Value 550 Submission Rate 250 / 544 (45.96%) Success Rate 73 / 250 (29.20%) High Score gozman for 359.52 points (23 mins 28 secs) Average Score 250.35 (for 73 correct submissions)

The solution can be split into two parts - generating a tree with nodes considered as  islands and seas and finding the number of islands of each level. In generating a tree, we will add covering waters '.' as the boundary of the map. We use the flood fill to find all seas and islands. The sea connected with the boundary element is defined as the root of the tree. From each visited sea we will visit unvisisted islands if they have at least one element vertically or horizontally adjacent to any element of the sea. From each visited island we will visit unvisisted seas if they have at least one element vertically, horizontally, or diagonally adjacent to any element of the island.

```                    ...............          000000000000000
xxx.x...xxxxx       .xxx.x...xxxxx.          011101000222220
xxxx....x...x       .xxxx....x...x.          011110000200020
........x.x.x       .........x.x.x.          000000000203020
..xxxxx.x...x       ...xxxxx.x...x.          000444440200020
..x...x.xxx.x   ->  ...x...x.xxx.x.   ->     000466640222020
..x.x.x...x..       ...x.x.x...x...          000467640002000
..x...x...xxx       ...x...x...xxx.          000466640002220
...xxxxxx....       ....xxxxxx.....          000044444400000
x............       .x.............          050000000000000
...............          000000000000000```

In the picture above, connected groups 0 and 6 are seas and connected groups are islands. The root 0 has children 1, 2, 3, 4, 5. The node 4 has a child 6(a sea). The sea 6 has a child 7(an island).

After creating the tree, it is easy to find the number of islands of each level as following. Any island or sea that have no child will be defined as level 1 and 0, respectively. The level of each island is defined as the maximum level of all its own children plus 1 and the level of each sea is defined as the maximum level of all its own children.

See the kalinov' solution for an implementation of this approach.

ValidPlates
Used as: Division One - Level Three:
 Value 1000 Submission Rate 9 / 544 (1.65%) Success Rate 1 / 9 (11.11%) High Score xhl_kogitsune for 395.08 points (59 mins 49 secs) Average Score 395.08 (for 1 correct submission)

If the plates stayed reasonably short, this is a straightforward dynamic programming problem. The example with the very long plate should indicate that a bit more is required, however. Specifically, if we attempt a dynamic programming approach, with our state being the length of the plate and the first character in the plate, and our value being the count of plates with those characteristics, our runtime would be O(length*digits^2) which is too high. Nonetheless it is instructive to examine the dynamic programming solution and see how we can improve it.

The dynamic programming solution is straightforward. Expressed as a recursion, we have:

```long count(int len, char firstdigit) {
if (len == 1)
return 1 ;
else {
long r = 0 ;
for (char d : digits)
if (legal[firstdigit][d])
r += count(len-1, d) ;
return r ;
}
}
```

Like many dynamic programming problems of this sort, the code above is essentially matrix multiplication, with the condition on legal replaced by multiplication by an entry in a matrix that is either 0 or 1. That is, the above code can be rewritten to compute all the digits in parallel using the following code:

```long[][] counts(int len) {
if (len == 1)
return new long[][] {{1}, {1}, {1}, {1}, ..., {1}} ;
else
return matrixmul(legal, counts(len-1)) ;
}
```

where legal is a 0/1 matrix representing the legal sets of digits. Since we're just using matrix multiplication, we can of course convert this to a simple matrix exponentiation routine that will give us the counts at any length very quickly.

We need to avoid iterating over the possible lengths, however, since the final length can be quite high. We'd rather use a binary search. But our count vector contains only the values at a particular length. One way to solve this issue is to introduce an eleventh digit, lexicographically before all the others; we'll use 'X' here. Then, when considering the length three plates, for instance, all length two plates will be included, but preceded by 'X'. Similarly, all length one plates will be included, preceded by two 'X's. If we do this, one computation will tell us the total number of plates of a given length and smaller. We have to extend our "legal" matrix with an eleventh row and column; we do not permit 'X' to come after anything but another 'X', and we never allow an 'X' to precede a '0'.

With this improvement, we can use binary search to calculate the length. When computing the count matrix at a length len, if the number of plates starting with 'X' is greater than our sequence number, we know we're too high. If the sum of plates at that length is greater than our sequence number, we're at the correct length. Otherwise we're too low.

Once we have the length, we can compute the digits one by one by simply iterating over the potential starting digits, determine the starting sequence of the plate with each starting digit by accumulating values from the matrix, and figuring out where our sequence number fits. Then we can subtract the count of plates with all prior digits from our sequence number, and move on to the next digit.