Match Editorial

Match summary

This SRM win came to Petr during the challenge phase - he was only third after the coding and needed 75 points to win it all. Needless to say, he got the W. Two leaders after the coding phase - ahyangyi and ACRush - came second and fourth, respectively, with blueblimp making the top-3 after a tremendous challenge phase.

Division 2 problems were tougher than usual. tfranovic and ftasb1 were leading the pack after the coding with a moderate 1280 and 1240 points respectively. Unfortunately, challenges and system tests weren't easy for them - tfranovic's hard failed to pass systests, ftasb1 was overtaken by YangKete, whose 175 challenge points were enough for a win.

The Problems

Value	250
Submission Rate	715 / 805 (88.82%)
Success Rate	586 / 715 (81.96%)
High Score	nitdgp for 247.14 points (3 mins 4 secs)
Average Score	183.74 (for 586 correct submissions)

First, it is never advantageous to put two BB polyominoes next to each other. Indeed, we can always replace "BBBB" with "AAAA" and thus get a lexicographically smaller string.

Now, consider a group of 'X' cells (surrounded by dots or borders of the region). Denote its length L.

• If L is odd, there is no way to cover this group (the polyominoes have even length), so the answer is "impossible".
• If L is a multiple of 4, use L/4 AAAA polyominoes to cover this group.
• If L is even but doesn't divide by 4, one BB polyomino has to be used. To make the answer lexicographically smallest, it should be placed in the end of the group, preceded by (L-2)/4 AAAA polyominoes.

Using patterns can make the code extremely short:

public String findCovering(String region) {

    region = region.replaceAll("XXXX", "AAAA").replaceAll("XX", "BB");

    return region.contains("X") ? "impossible" : region;

}

Value	500
Submission Rate	178 / 805 (22.11%)
Success Rate	107 / 178 (60.11%)
High Score	Start for 477.67 points (6 mins 12 secs)
Average Score	297.88 (for 107 correct submissions)

Value	250
Submission Rate	547 / 624 (87.66%)
Success Rate	500 / 547 (91.41%)
High Score	Abednego for 246.57 points (3 mins 21 secs)
Average Score	188.58 (for 500 correct submissions)

Contestants were asked to count all letters in all subrectangles of the given table.

The straight-forward algorithm looks like this: iterate over all subrectangles and for each subrectangle, count the letters inside it. Unfortunately, this algorithm takes O((h×w)³) time for a h×w table and doesn't fit in 2 seconds for a 100×100 table.

The correct algorithm is to iterate over all cells of the table, and for each cell, count the number of times it appears in subrectangles.

For a cell (i, j), the number of subrectangles that contain this cell is equal to (i + 1)(2h - i)(j + 1)(2w - j).

Value	1000
Submission Rate	55 / 805 (6.83%)
Success Rate	20 / 55 (36.36%)
High Score	winsweet for 631.11 points (25 mins 2 secs)
Average Score	526.09 (for 20 correct submissions)

Value	500
Submission Rate	395 / 624 (63.30%)
Success Rate	261 / 395 (66.08%)
High Score	Petr for 489.26 points (4 mins 13 secs)
Average Score	314.47 (for 261 correct submissions)

The solution can be split in 2 parts - first we find any masses which satisfy the given receipt, and then we change the solution to make the total mass as small as possible. The latter part is easy - as soon as we have a solution (M1, ..., Mn), we compute the greatest common divisor of all Mi and divide each Mi by this divisor.

The former part - finding any vector of masses which satisfies the receipt - can be done in multiple ways. Since the total number of ingredients is very low, we can forget about optimizations - it will be hard to construct an algorithm which will NOT work in time.

The most natural approach is to find the proportion for all pairs of ingredients, set the mass of ingredient 1 to some value and compute the masses of all other ingredients using the proportions. Computing the matrix of proportions is easy - parse all input proportions and run some kind of Floyd-Warshall algorithm (so, if we know ingredients A and B are in proportion a:b and ingredients B and C are in proportion c:d, then we conclude A and C are in proportion (a * c):(b * d)).

So, the only missing part of the solution is the selection of the mass of ingredient 1. This mass has to be selected in such way that the masses of all other ingredients will be integer as well (for example, if ingredients 3 and 1 are in proportion 2 : 3, then mass of the first ingredient must be a multiple of 3). In other words, if ingredient 1 and ingredient k are in proportion Ak : Bk, then the mass of the first ingredient must be divisible by Ak (for all k). Therefore, we can pick the least common multiple of all Ak's as the mass of the first ingredient.

And the algorithm altogether:

1. Parse all input proportions.
2. Compute the proportions between all pairs of ingredients.
3. Calculate the mass of the first ingredient using the LCM above.
4. Compute the masses of all other ingredients.
5. Minimize the total mass dividing all masses by their GCD.

Value	1000
Submission Rate	172 / 624 (27.56%)
Success Rate	34 / 172 (19.77%)
High Score	ahyangyi for 897.65 points (9 mins 49 secs)
Average Score	617.77 (for 34 correct submissions)

The task was to cover a given region with polyominoes of two types:

A  A

AAAA  and  BB

Moreover, the covering had to be the lexicographically smallest one.

Let's solve the second part first.

Suppose that, given a region, we can determine whether it can be covered or not. Now, here's the general approach that allows to find the lexicographically smallest covering:

Check whether the given region can be covered.

If not, return "impossible".

While the region is not covered, do the following:

    Find the first 'X' (the leftmost among the topmost Xs)

    Try to put an A-polyomino, so that its upper-left corner occupies this 'X'.

    If a) an A-polyomino fits there, and b) the rest of the region can be covered

        Fix an A-polyomino like this.

    Otherwise,

        Fix a BB polyomino at this 'X' and the 'X' on the right of it.

This algorithm always puts the lexicographically smallest valid symbol at the position of the first 'X', so the result is optimal.

Now we are to solve the first part of the problem: given a region, check whether it can be covered.

Definition Let's call embracing pattern the following rectangle:

ABBA

AAAA

Lemma If a region can be covered, then it can be covered without embracing patterns.

Proof While there are embracing patterns, continue demolishing them with the following transformation:

          ABBA          BBBB

replace   AAAA   with   BBBB

Each such replacement decreases the number of embracing patterns by 1, so it will eventually reach 0. End of proof

Thus, our question ("can this region be covered?") is equivalent to the following one: can this region be covered if embracing patterns are prohibited? Let's design an algorithm that answers this question.

Find the first 'X'. It can be either the upper-left corner of an A-polyomino, or the left half of a BB polyomino.

Check whether the corresponding polyominoes fit into the region.

If none of them fits, the answer is "no" (the region can't be covered).

If exactly one of them fits, fix the one that fits (that's the only choice) and continue applying the algorithm.

If both of them fit, we have the following situation:

XXCX

XXXX

• Case 1, cell C is empty ('.'). We can't put an A-polyomino: it would leave one uncoverable cell. So, put a BB polyomino and continue.
• Case 2, cell C is an 'X'. Suppose we put an A-polyomino. But such decision leaves two cells inside this A-polyomino. These two cells must be covered with a BB polyomino. And we get an embracing pattern which is prohibited. Therefore, we had to put a BB polyomino in this case.

Thus, all cases being investigated, we have a linear-time algorithm that checks whether a given region can be covered.

This algorithm can be simplified. Note that in all cases, if we can place a BB polyomino in the X cell under consideration, we always do put it. Therefore, the algorithm can be reformulated:

While the region is not covered, do the following:

    Find the first 'X'.

    If there is an 'X' on the right of it

        Put a BB polyomino there and continue.

    If it is possible to put an A-polyomino with its upper-left corner at this 'X'

        Put such A-polyomino and continue.

    Return "impossible".