JOIN
 Match Editorials
TCHS SRM 55
Tuesday, August 26, 2008

## 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

VeryInterestingMovie
Used as: Division One - Level One:
 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.

MagicStones
Used as: Division One - Level Two:
 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 x1, x2 , ... , xk that x1 + x2 + ... + xk = N and lcm (x1, x2, ... , xk) 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 x1, x2, ... , xk, where all xi 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

CollectingPostmarks
Used as: Division One - Level Three:
 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 216. 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

By Gluk
TopCoder Member