Match Editorial

Match summary

Division 1 was won by ACRush who showed the best time on both the 500-pointer and the 1000-pointer. The second place went to marek.cygan, and the third was gained by Petr, thanks to his two successful challenges. andrewzta and krijgertje came in fourth and fifth, both regaining a rating of 3000+ and a target sign.

Division 2 was won by Ripatti, who was closely followed by leohoyee and emotionalBlind. Along with gajcz and Blue.Mary, those are the only five contestants who were able to solve all three problems correctly.

In Division 1, during both the challenge phase and the system tests, a lot of 500-pointer and 1000-pointer solutions failed the tests with maximal possible inputs (N=200000 for the medium, and N=10¹⁸ for the hard). Let this be a reminder for all of us to check our solutions on "max tests" every time.

The Problems

Value	250
Submission Rate	728 / 776 (93.81%)
Success Rate	704 / 728 (96.70%)
High Score	dinoj18 for 248.74 points (2 mins 1 secs)
Average Score	210.63 (for 704 correct submissions)

The average lifetime of the candies is the sum of their lifetimes divided by the number of the candies. The natural approach for this problem is to calculate these two values. In can be done by iterating over the given array eatenCandies just once. The following Java code is a correct solution for the problem:

private final int[] months = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

public double getAverage(int[] eatenCandies) {
    int lifetime = 0;
    int sum = 0;
    int number = 0;
    for (int i = 0; i < 12; i++) {
        lifetime += months[i];
        sum += eatenCandies[i] * lifetime;
        number += eatenCandies[i];
    }
    return sum * 1.0 / number;
}

Value	500
Submission Rate	197 / 776 (25.39%)
Success Rate	36 / 197 (18.27%)
High Score	WeiYi for 460.84 points (8 mins 25 secs)
Average Score	258.54 (for 36 correct submissions)

Value	250
Submission Rate	516 / 614 (84.04%)
Success Rate	278 / 516 (53.88%)
High Score	Petr for 246.20 points (3 mins 32 secs)
Average Score	157.72 (for 278 correct submissions)

First, suppose neither s1 nor s2 start with an asterisk. If they start with different letters, the correct answer is "impossible", because after any replacements the strings will still start with different letters. Otherwise, if they start with the same letter, we can remember that the answer must start with this letter and remove this letter from both strings.

Similarly, we can consecutively remove letters from the endings of the strings, (and if we notice different letters on the endings, the answer is "impossible").

After doing so, we will have two strings, at least one of which starts with an asterisk (otherwise we could remove one more letter from the beginning), and at least one of which ends with an asterisk (otherwise we could remove one more letter from the ending).

If one of the strings is an asterisk ("*"), than the answer is the other string with its asterisk removed (better to say, replaced with an empty string).

Otherwise, we have one string starting with an asterisk (say, s2) and the other string ending with an asterisk (s1). Remove the asterisks from both strings. Now the answer is the shortest string that starts with s1 and ends with s2 (possibly, there is an overlapping of s1 and s2).

The shortest string with a given prefix and a given suffix can be found using Knuth-Morris-Pratt Algorithm in linear time. However, constraints of this problem allowed to solve this subproblem using a slower algorithm. The easiest approach is to find the largest length of the overlapping part of s1 and s2. Just try all possible lengths from 0 to the length of s1 and check whether the corresponding number of last characters of s1 are equal to the corresponding first characters of s2. If they are equal then we can make this letters the overlapping part of s1 and s2. Obviously, the string with the largest overlapping part is the shortest string that starts with s1 and ends with s2.

An implementation of this approach was coded by yuhch123.

Also worthy of mentioning is a witty solution by maniek who used the Java built-in regular expressions.

Value	1000
Submission Rate	23 / 776 (2.96%)
Success Rate	13 / 23 (56.52%)
High Score	Ripatti for 590.79 points (28 mins 8 secs)
Average Score	460.08 (for 13 correct submissions)

Division 2 coders were asked to find the lexicographically smallest QuasiLatin square, a natural generalization of Latin square. However, the generalization wasn't really important, because the correct answer for any n and d looks like this:

0	0	0	0	1	2	3	...	d-1
0	0	0	0	1	2	3	...	d-1
0	0	0	0	1	2	3	...	d-1
0	0	0	Latin square of size d
1	1	1
2	2	2
3	3	3
:	:	:
d-1	d-1	d-1

Thus, the problem could be reduced to finding the lexicographically smallest Latin square of size d.

However, this reduction wasn't necessary, because even the generalized problem can be solved in reasonable time using a simple backtracking algorithm. A pseudocode implementation of it is shown below.

boolean search(i, j) {
    for (int v = 0; v < d; v++) {
        a[i][j] = v;

        Consider row i of matrix a
        Count p, the number of different digits in cells a[i][0] through a[i][j]
        We need to put d-p more digits, and we only have n-j-1 cells
        If there is not enough cells for the digits
            continue;

        Consider column j of matrix a
        Count q, the number of different digits in cells a[0][j] through a[i][j]
        We need to put d-q more digits, and we only have n-i-1 cells
        If there is not enough cells for the digits
            continue;

        if (i, j) is the last cell
            return true;
        if search(next cell after (i, j))
            return true;
    }
    return false;
}

The nature of the lexicographically smallest Latin squared of size d strongly depends on d. When d is a power of two, the desired Latin square is not only symmetrical, but it also follows a wonderful pattern:

On the other hand, for d=5, 7, 9, and 10 (and many larger values that weren't considered in the given problem), the answer is not symmetrical with respect to the main diagonal.

Value	500
Submission Rate	327 / 614 (53.26%)
Success Rate	262 / 327 (80.12%)
High Score	ACRush for 473.93 points (6 mins 44 secs)
Average Score	324.56 (for 262 correct submissions)

Let's try to calculate the score of the player, when starting from all possible initial cells. Then the answer to the problem is the maximum of all N such values.

Start emulating the process from initial cell number 1. The token will make some moves and finally reach a cell that was already visited before. Look at the piece of the path, from the first visitation of that cell to the second visitation. This is a loop. Calculate the length of this loop L (the number of the cells in it), and for each cell in the loop, store that the score when starting from this cell is L (indeed, if we start in this cell, the token will travel along the loop and reach the initial cell, thus giving score L).

Now let's look at the cells of the considered path that come before the loop. What if we start from the cell right before the loop? The score in this case will be L+1. Starting from the previous cell leads to the score of L+2, and so on. Iterate over all the cells that come before the loop and calculate this scores.

By now, we've gathered all the useful information about all the cells on the path starting from 1. But we need to process all the cells outside this path as well.

Select any cell that doesn't belong to this path. Start emulating the process from this cell. We will reach one of the following situations:

• We will reach a cell that was already visited during this emulation
• We will reach a cell that was already processed during previous emulations

In the first case, we should do the same procedure as we did above for the path starting from 1.

In the second case, we reach a cell C processed before, so we already know the score when starting from cell C. Then the score for the cell before C is equal to the score for C plus 1. The score for the previous cell is the score for C plus 2 etc. Iterate over the entire path in backwards direction and calculate all the scores in this fashion.

Repeat the above procedure for all cells that haven't been processed until there are no such cells left.

Note that each cell is processed exactly once in the proposed algorithm, thus the overall working time is O(N).

Coders should be aware that implementing this algorithm (or a similar one) in a recursive fashion can lead to stack overflow. It is good to know the default stack size of your language. It is also good to know how to avoid recursive functions in hazardous situations (roughly speaking, using your own stack).

Value	1000
Submission Rate	120 / 614 (19.54%)
Success Rate	52 / 120 (43.33%)
High Score	ACRush for 891.22 points (10 mins 10 secs)
Average Score	591.07 (for 52 correct submissions)

First, since the number 999...9 is an equidigit number, the answer to the problem always has the same length as the input N. Let's denote this length m. Also for simplicity let's check whether N is already equitigit, and return N if it is. So now we need to find the smallest equidigit number of length m that is strictly greater than N.

As this desired number is greater than N, let's denote p the position of the leftmost digit in which this number differs from N. Also, let's denote q the digit of this number in the position p.

Iterate over all posible values of p and q. Having fixed p and q, the task is to find the smallest equidigit number satisfying the following conditions:

• Its length is m
• Its first p-1 digits are those of number N
• Its p-th digit is q

Now iterate over v from 1 to 10, that is the number of different digits in the desired equidigit number.

When we have fixed m, v and several first digits of the desired number, the next digit can be found easily according to a greedy algorithm. Indeed, iterate over all possible values for the next digit, and select the smallest value, such that setting it into the current position doesn't make the number of different digits used exceed v and doesn't make the amount of each digit exceed m/v.