Match Editorial

Match summary

In division I, ACRush immediatly took the lead with the fastest 250. Few minutes afterwards, Burunduk1 with an excellent performance on the 500 managed to reach the top. However, an extremely fast 1000 and a successful challenge granted ACRush the victory. Burunduk1 taking the second place added his name to the target list.

In division II, the coders faced a quite tricky 1000 pointer. Only 8 coders managed to solve it correctly. maksay took the first place advancing to division I followed by xjtuhyh and al13n.

The Problems

Value	250
Submission Rate	716 / 773 (92.63%)
Success Rate	625 / 716 (87.29%)
High Score	nitdgp for 247.65 points (2 mins 46 secs)
Average Score	198.05 (for 625 correct submissions)

This problem was a simple implementation of Luhn method. Coders were asked to correctly parse the input data and calculate the sum of the digits of odds and even positions while doubling the appropriate digits correctly and taking care of the case where the resulting number is bigger than 9. A card number is invalid when the sum is not a multiple of 10. This could easily be checked by calculating the remainder modulo 10.

Value	500
Submission Rate	332 / 773 (42.95%)
Success Rate	214 / 332 (64.46%)
High Score	faeton for 467.23 points (7 mins 37 secs)
Average Score	299.72 (for 214 correct submissions)

Value	250
Submission Rate	515 / 548 (93.98%)
Success Rate	439 / 515 (85.24%)
High Score	ACRush for 247.14 points (3 mins 4 secs)
Average Score	201.08 (for 439 correct submissions)

The problem asked you to calculate the minimum number of changes needed to make the dna string periodic with period less than or equal to maxPeriod.

Suppose that we want our string to be periodic with period 1. Then every character must be the same. So what we need to do is to keep the character that appears the most times and change all the others.

In case we want it to be periodic with period 2, characters in an odd positions must be the same and so must be characters in even positions. So we change all the characters in odd positions to the character that appears the most times in an odd position and all the characters in even positions to the character that appears the most times in an even position.

Following this pattern it is easy to see that to calculate the minimum number of changes needed to make a string periodic with period p we need to make characters with the same positions modulo p equal and this can be done by greedily picking the character that appears the most times.

So for the actual solution we iterate through every acceptable period and calculate the minimum number of changes needed. See xjtuhyh's code for a clear implementation.

Value	1000
Submission Rate	188 / 773 (24.32%)
Success Rate	8 / 188 (4.26%)
High Score	xjtuhyh for 612.36 points (26 mins 25 secs)
Average Score	526.90 (for 8 correct submissions)

The tricky part about the problem was that it asked for the maximum number that can be made by removing the given digits while in fact the correct approach was to think about which digits must stay. So the correct algorithm to create the desired number is to start with no digits and append the maximum possible digit at the end of the number. But how do we check if it is possible to add a certain digit? Well, that digit must satisfy two conditions:

• The digit must appear strictly more times in number than in digits because otherwise we won't have enough digits to remove
• It must be possible to remove all the digits that appear before that digit.

maksay's solution follows the method described above.

Value	500
Submission Rate	342 / 548 (62.41%)
Success Rate	253 / 342 (73.98%)
High Score	Burunduk1 for 442.67 points (10 mins 30 secs)
Average Score	282.49 (for 253 correct submissions)

Let's first try to find a more useful definition of a smooth block by examining several of its properties. Notice that for any two pixels A and B in the same row of the same block the only path that has length equal to their manhattan distance is the path that passes through the pixels between them. So every pixel in the same row as A and B that lies between them must be black. The same applies for any two pixels of the same column. So when examining a smooth block by each row or by each column, that block must consist of at most a single part.

We will now prove that this property is enough for a block to be smooth. A block with this property is always smooth as there exists a path equal to the manhattan distance for every 2 pixels. Suppose that we have pixels A and B and without loss of generality B is upper and righter than A. We can reach pixel B from A only by going up or right to black pixels with smaller manhattan distance from B. This will always be possible because of the previous property. But such a path is the shortest possible path as it doesn't make any unnecessary steps and uses only black pixels. And since this applies for any 2 pixels inside the block, the block is smooth.

Based on the above property we conclude that in order to make a block smooth we must turn to black every pixel between the leftmost and the rightmost pixel in each row and every pixel between the topmost and the bottommost in each column. The pixels that need to be changed are fixed and they don't depend on the other changes we make so the answer that makes the minimum number of changes is always unique.

So using these ideas we can create an algorithm that makes every block smooth until all blocks are smooth.

blocks_are_smooth = false
while blocks_are_smooth == false {
    blocks_are_smooth = true
    Find the blocks using a flood fill algorithm
    For each block {
        For each row {
            Find the leftmost and 
            the rightmost pixel of the block
            Turn every pixel in between black
            if at least one change was made
                blocks_are_smooth = false
        }
        For each column {
            Find the topmost and 
            the bottommost pixel of the block
            Turn every pixel in between black
            if at least one change was made
                blocks_are_smooth = false
        }
    }
}
return the image

This algorithm is very unoptimized and may run a bit slow. Some optimizations that can be made is to calculate the leftmost, rightmost, topmost and bottommost pixels when finding the blocks and avoid pointless searching over smooth blocks already searched.

For an implementation of this approach you can look at Burunduk1's submission

Value	1000
Submission Rate	62 / 548 (11.31%)
Success Rate	39 / 62 (62.90%)
High Score	ACRush for 976.01 points (4 mins 28 secs)
Average Score	603.09 (for 39 correct submissions)

The problem was about a game played in two phases. The first phase was for each player to remove as many heaps as the player wants and the second one was a normal Nim game.

The solution to the normal Nim is a very common combinatorial game theory result: The player that is presented with a set of piles such that the xor (or the nim-sum as it is usually called) of the heap sizes is 0 will lose the game if his opponent plays optimal.

Now for the first phase, after the first player makes his move removing several heaps, the second player will try to remove some of the remaining heaps so that the first player will be at a losing position at the beginning of the second phase. But since the first player doesn't want that to happen he must choose the heaps to remove carefully so that no subset of the remaining heaps has xor of the heap sizes 0.

We can consider the heap sizes as vectors over GF(2) containing only zeros and ones as their coordinates according to their binary representation. For example, a heap with size 5 has binary representation (101)₂ and corresponds to the vector (1,0,1). Notice that the xor is equivalent to addition of the vectors over GF(2).
5 xor 6 = 3 => (1,0,1)+(1,1,0)=(1+1,0+1,1+0)=(0,1,1).
Let's call our vectors a1,...,aN. We want to find a subset of them b1,...,bK such that no subset of the bis has sum 0. So the equation: b1*c1+..+bK*cK = 0 where cis are either 0 or 1 must have only one solution where every ci is 0. So what we are really looking for is a linearly independent (over GF(2)) subset of our original vectors.

After these considerations all that is left is to find which vectors to remove so that the sum of their values is minimum. This can be done in two ways. The first way is to consider the vector space that is created by the original vectors and remove each time the minimum possible that does not change the vector space. We can check this by checking if removing a single vector reduces the dimension of the vector space. The other way is to initially start with an empty set of vectors and add the largest one that maintains the linear independence. Then remove from the rest of them.

Checking for linear independence or finding the dimension of the vector space can be done using Gaussian Elimination. ilyaraz's solution uses the second method. ACRush's very fast submission picks the largest vector that maintains linear independence as well but does that in a single Gaussian Elimination.