Tuesday, August 26, 2008 Match summary
In Div1 coders faced quite straightforward easy problem. Medium problem appeared to be not that simple and brought lots of challenges. 9 coders successfully
solved the hard, what helped them to get top 9 places. The division was won by Petr who had not very
high scores for all three problems, but got +125 on challenges. ardiankp became the second and
lordmonsoon took the third place. The ProblemsCollectingUsualPostmarksUsed as: Division Two  Level One:
The first and the main thing the competitor had to think about was "What do I have to do with the postmarks which I already have ?". And the answer was quite clear. As sell and buy prices for each postmark are equal you can initialy sell all the postmarks you have and maybe buy some of them later. After realizing that the problem becomes really simple. All you have is to sell all postmarks you initially have and then buy them in the increasing order of prices while you have enough money. ThreePhotosUsed as: Division Two  Level Two:
Let's remove all small cubes and then try to put as many of them as possible to their initial places. If for some cube with coordinates (x,y,z) it turns that A[x][y]='Y' and B[x][z]='Y' and C[y][z]='Y' than it's clear that we can put this cube on its place. If any of the conditions is false we can't leave the cube on its place, so we will have to remove it. Placing cubes in such a way we will leave as many cubes as possible. But don't forget about the case, when all three photos can't be valid. So we have to make some additional checks. If after such a placement it exists such x and y that A[x][y]='Y' but for any z cube with coordinates (x,y,z) has to be removed than there is no way to make the photos valid so 1 has to be returned. The same checks have to be done for B and C. You can find a clear implementation of this idea in this solution by qizichao. CardsCheatingUsed as: Division Two  Level Three:
This problem appeared to be quite easy for some division 2 competitors. The main question that appeared was "How big can the answer be ?". Let's look on the deck shuffle as on the permutation of length N. The period of a permutation is the minimum number of repeated invokations required to get back to start. It's clear that the answer can't be equal or greater than the period of this permutation. So the question transforms into "How big can the period of permutation of length N be ?". Looking at any permutation you can notice that it can be broken into some cycles. The least common multiple of the lengths of these cycles is the period of the permutation. For example let's look on the permutation {1,4,0,3,2,5}. It has two cycles: 0>1>4>2>0 and 3>5>3. Their lengthes are 4 and 2, so the period of permutation will be lcm(4,2) = 4. After some additional calculations you can see that the permutation of length 50 can't have it's period greater than 180180. Knowing this fact the solution becomes really short: apply the shuffle to the deck until you get the required order of cards or you make more than 180180 shuffles. ShipLoadingUsed as: Division One  Level One:
Let's assume we can use each crane only once. Then it will be possible to load all boxes to the ship if the crane with the greatest weight limit is able to move the heaviest box, the crane with the second greatest weight limit is able to move the second heaviest box and so on. Now if we can spend X minutes to load the ship, then we can use each crane X times. It is the same as we have each crane cloned X times and after that we can use each crane once. So the solution is to find the minimum X such that it will be possible to load the ship when each crane is cloned X times and each of them can be used once. 1 is possible only if there exists such a box which can't be moved by any of the cranes. You can find a clear implementation of this idea in this solution by neal_wu. CollectingPostmarksUsed as: Division One  Level Two:
The first quiestion which appeared was "What do I have to do with the postmarks which I already have ?". And the answer was quite clear. As sell and buy prices for each postmark are equal you can initialy sell all the postmarks you have and maybe buy some of them later. So now we can assume that we have no postmarks and need to find the set of postmarks with total value not less than K and total price as small as possible. Let's divide all the postmarks into two groups of equal sizes (if the number of postmarks is odd one of the groups will have 1 more element than the other). Each group will have not more than 16 postmarks and the number of subsets of postmarks of each group will be not greater than 2^{16}. So we can list all subsets of postmarks of first and second group and call the lists A and B respectively. It is also clear than if for some two subsets of first group numbered i and j it appears that A[i].cost >= A[j].cost and A[i].value <= A[j].value then subset A[i] is useless (it will be always better to use subset A[j] than subset A[i]). The same is correct for list B. Now let's assume that both list are ordered in such way that for any i: A[i].value < A[i+1].value, A[i].cost < A[i+1].cost, B[i].value < B[i+1].value and B[i].cost < B[i+1].cost. Now for each i we can find such j that A[i].value+B[j].value >= K and B[j].cost is as small as possible. The pair with the smallest total cost will be the answer. Using the order of elements in A and B all this pairs can be checked in linear time. You can see a clear implementation of this idea in this very fast solution by Burunduk1 AlienDictionaryUsed as: Division One  Level Three:
First of all you have to generate the set of all invalid substrings. All of them have equal length, let's call it L. All strings of length L can be ordered lexicographically and numbered from 0 to 2^{L}1. Using dynamic programming you can simply generate values r[i][j] for each i and j, where r[i][j] is equal to the number of valid alien words of length i starting with substring of length L numbered j. Having these values the generation of valid alien word of length N numbered x is quite simple. Example java code follows: int mask; for (mask = 0; mask < (1 << L); mask ++) { if (r[N][mask] > x) break; x = r[N][mask]; } if (mask == (1 << L)) { result = "NO PAGE"; continue; } for (int j = L  1; j >= 0; j ) if ((mask & (1 << j)) != 0) result+="B"; else result+="A"; for (int step = 1; step + L <= N; step ++) { int move1 = (mask % (1 << (L  1))) * 2; int move2 = move1 + 1; if (r[N  step][move1] > x) { result += "A"; mask = move1; } else { result += "B"; mask = move2; x = r[N  step][move1]; } }You can see the example of the implementation of this idea in this solution by kalinov. 
