Match Editorials

Match summary

Easy 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 Problems

Value	250
Submission Rate	51 / 53 (96.23%)
Success Rate	45 / 51 (88.24%)
High Score	xiaowuc1 for 249.28 points (1 mins 31 secs)
Average Score	227.22 (for 45 correct submissions)

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.

Value	500
Submission Rate	17 / 53 (32.08%)
Success Rate	11 / 17 (64.71%)
High Score	gogokefakefa for 465.28 points (7 mins 52 secs)
Average Score	304.39 (for 11 correct submissions)

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₁, x₂ , ... , x_k that x₁ + x₂ + ... + x_k = N and lcm (x₁, x₂, ... , 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₁, x₂, ... , 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

Value	1000
Submission Rate	9 / 53 (16.98%)
Success Rate	1 / 9 (11.11%)
High Score	wcao for 722.30 points (19 mins 14 secs)
Average Score	722.30 (for 1 correct submission)

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¹⁶. 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