Thursday, December 11, 2008 Match summaryThis 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 top3 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 ProblemsLinearPolyominoCoveringUsed as: Division Two  Level One:
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.
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; }SubrectanglesOfTable Used as: Division Two  Level Two: Used as: Division One  Level One:
Contestants were asked to count all letters in all subrectangles of the given table. The straightforward algorithm looks like this: iterate over all subrectangles and for each subrectangle, count the letters inside it. Unfortunately, this algorithm takes O((h×w)^{3}) 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). IngredientProportionsUsed as: Division Two  Level Three: Used as: Division One  Level Two:
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 FloydWarshall 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:
Used as: Division One  Level Three:
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 Apolyomino, so that its upperleft corner occupies this 'X'. If a) an Apolyomino fits there, and b) the rest of the region can be covered Fix an Apolyomino 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 upperleft corner of an Apolyomino, 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(We're looking at the upperleft X, which can be part of either polyomino)
Thus, all cases being investigated, we have a lineartime 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 Apolyomino with its upperleft corner at this 'X' Put such Apolyomino and continue. Return "impossible". 
