Dear friends!

The next competition - Codeforces Round 101 for participants Div2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Polina Bondarenko (Polichka) and Gerald Agapov (Gerald). There were Artem Rahov (RAD), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.

It is a little bit about authors: all of us study at the Saratov State University at faculty of Computer Sciences and Information technology on 4th course. Now in free time from competitions and problems we pass the exams :) I’m a 1/3 part from command Saratov SU#2, and Gerald with Polina - 2/3 from Saratov SU#1. We would like our rounds became kind tradition on Codeforces and you have seen us among authors soon again.

We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the total table. Today you will help Santa Claus, Elf, Vasya and the other characters. All the similarities to real people are casual :)

The points on problems are distributed today in this way: **500-1000-2000-2000-2500**

**UPD: **You can read the tutorial here.

**UPD:**Thanks all for participation! The round has turn out difficult enough and only one person among all participants (including Div. 1) has solved all offered problems

**-**akim239. Our congratulations for him!!

**UPD:**our congratulations for Top-10 participants in competition:

a_{i}. // fail() means that there is no solutionres, where we will keep name of person, his height.a_{1}> 0) fail();h_{1}= 500000;i= 2..n{a_{i}≥i) fail();a_{i}= =a_{i - 1}) {h_{i}=h_{i - 1}a_{i}+ 1)th place,h_{i}= 500000 -a_{i}Thank you

And if you want to hack them, you need to understand their codes totally.

code "[ [ submission:1021473 ] ]" without space.

3 3

1 2 S

1 2 M

2 3 S

After sorting:

First, let h

_{1}= n (or what number you like as long as it is not less than n).At step i, assign n - a

_{i}to h_{i}and decrease h_{j}by 1 if h_{j}≤ h_{i}(obviously, these changes do not affect previous order). Therefore, after step i, we can maintain a list of numbers from n - i + 1 to n.can you tell why your solution works ? idea behind it.

Now, instead of choosing values, let's think about choosing ranks for these elements (from 1 to n, 1 is the biggest). Then, we can easily choose value for an element if we know its rank.

First, there's only 1 element, of course its rank is 1.

With element i, we know it must be smaller than a

_{i}elements, so its rank is a_{i}+1. Inserting this element into the list we created so far will increase the ranks of elements whose current ranks are greater than a_{i}.For ex: let the a[] after sorting is {0,1,1,2,2,3}

Array rank[] after each step (bold numbers are whose ranks are increased after each step)

Step 0: 1

Step 1: 1,2

Step 2: 1,

3,2Step 3: 1,

4,2,3Step 4: 1,

5,2,4,3Step 5: 1,

6,2,5,3,4count differences between these two codes!

http://www.codeforces.com/contest/141/submission/1024571

http://www.codeforces.com/contest/141/submission/1022993

Codeforces was so slow today and I think your code deserves to be rejudged.

I think the reason is judging a lot of submissions at the same time in system testing might cause a little difference in execution time (1920ms is pretty close to time limit).

the order of my code is n^2logn which is should pass when n = 3,000. u r right it is very close to 2 secs, but my code passes in less than 2 secs.

Process time is not a constant on any operation system, but it could vary a little. Typically 3-10% is acceptable accuracy. In particular on this all author solutions are 2-3 times faster than a time limit. Actually each contest we have some solutions which work around a time limit. Some of them pass system tests, some of them not. But anyway, writing such solution is a risk, because you can't get will it pass tests or not.

We do not rejudge such solutions, it would be unfair to other participants. We apologize for the inconvenience.

can you please tell us how you get such number of operations? what if we replace

setwithsort?the number of operations will be the same? I think you just have not strong enough test data. Codeforces servers are very fast as i know.upd:withsortyour program works only 340 ms, but it is still O(n^2 * log(n)). The constant factor is very important. BTW dont't you forget about N^2/2 calls of "operator new" when you useset? There is more optimal - O(n^2) solution, so there is no any problem.as I know that the set implementation in the c++ is a red-black tree, which takes log(n) in the insertion. so my code is O(N^2Log(N)) and N = 30000, So N^2Log(N) = 3000^2Log(3000) = 31,294,091.292476962.

setmust be used, but you should understand: it is slower then just sorting.There's an even more optimal O(N) solution too.