Thursday, April 3, 2008 Match summaryIn 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 ProblemsVerifyCreditCardUsed as: Division Two  Level One:
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. DNAStringUsed as: Division Two  Level Two: Used as: Division One  Level One:
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. RemovingDigitsUsed as: Division Two  Level Three:
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:
maksay's solution follows the method described above. FixImageUsed as: Division One  Level Two:
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 MoreNimUsed as: Division One  Level Three:
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 nimsum 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)_{2} and corresponds to the vector (1,0,1). Notice that the xor is equivalent to addition of the
vectors over GF(2). 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. 
