Tuesday, August 26, 2008 Match summaryEasy problem appeared to be really easy, so almost all coders successfully solved it. Medium was a bit more tricky and only 11 solutions passed system tests. There was only one correct solution for the hard and it brought first place to wcao. He was followed by gogokefakefa and Hornax. The ProblemsVeryInterestingMovieUsed as: Division One  Level One:
The first thing that has to be noticed is that problem can be solved for each row separately. Then you can see that the problem can be solved for each consecutive group of availible seats separately. If such group has length L, then you can place L/2 students on this places if L is even or (L+1)/2 studenrs, otherwise. Look here for a very short solution by xiaowuc1. MagicStonesUsed as: Division One  Level Two:
The problem was to find the maximum period of a permutation of length N. The period of a permutation is the minimum number of repeated invokations required to get back to start. 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. So the problem is to select such numbers x_{1}, x_{2} , ... , x_{k} that x_{1} + x_{2} + ... + x_{k} = N and lcm (x_{1}, x_{2}, ... , x_{k}) is as big as possible. As it is clear that it is useless to use cycles of equal length the problem can be solved by finding all such sets of x_{1}, x_{2}, ... , x_{k}, where all x_{i} are unique and their sum is not greater than N and then selecting the set with the greatest least common multiple. You can see the implementation of this idea in this solution by freopen CollectingPostmarksUsed as: Division One  Level Three:
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 
