Match Editorial

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

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;
}

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)

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.

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)

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).

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

See also Vasyl(alphacom)' solution  for a nice recursive approach.

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.