CF: Rockethon 2015

Though I’ve been coding algorithm contests since high school, when I was an OIer, and for 5 years till now. I’ve never really achieved something big in the algo contest field, due to having been lack of persistence and being distracted by other annoying things from time to time, and most of all, the limit of gift(:/). End of the sad story.

However, I’ve decided to make some changes by starting to get my color red in Codeforces. Actually you can see the story above pretty much by my rating curves

Anyway, I’ve practiced the Rockethon 2015, here are some conclusions.

A. Game:

Silly problems.

B. Permutations:

The constraint constraints will largely reduce the number of valid permutations. Let’s view this sum by the contribution each individual number made. In the largest cases, the 1 is counted n times, n-1 times for 2, n-2 times for 3… Thus, to make this happen, 1 should be placed at either end of the spots, 2 should be placed at one end of the remaining spots, and so on. Hence, there are 2^n valid sequences, and the first 2^n-1 start with 1, and others end with 1, then in these subsequences, the first half start with 2 and the second half end with 2 and so on. And so goes the way that we generate the kth lexicographical sequence.


Since n is at most 5, and R is at most 10000, brute-force can be safely used. So we classify the bidders into 3, the ones that bid lower than the second price, those who bid equally, and those who bid higher. Notice that there are 2 cases, the first is that 1 highest bid and several second bids and the second is that the highest bid has the value as the second one.

To Be Updated