Editorial for TLE '16 Contest 5 P5 - Better Ranking List


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: d

For the first subtask, print the maximum score so far for the first problem. This subtask was intended to reward users who read all of the problems.

Time Complexity: \mathcal{O}(N)

For the second subtask, perform the instructions listed in the problem statement. Keep an array which stores the highest submissions for each problem, sort a copy of this array, and calculate the PP.

Time Complexity: \mathcal{O}(N \times P \log P)

For the third subtask, notice that r^{i-1}=1. Then the user's PP is equal to \sum_{i=1}^{100\,000} s_i. In this formula, sorting is not needed. For each query, find the increase in the total sum, then output the total sum.

Time Complexity: \mathcal{O}(N)

For the fourth subtask, it is only necessary to get the user's top 5 submissions. All of the other submissions are covered by the relative error, since r^5 + r^6 + r^7 + \dots < 10^{-7}. Record the problems which are in the top 5, and update this small list when necessary.

Time Complexity: \mathcal{O}(5N)

The fifth subtask is intended to reward submissions which are not fast enough to solve the sixth subtask. Some reasons include:

  • using long double instead of double
  • calculating the powers of r every time (instead of using an array)
  • runtime is slower than \mathcal{O}(N \log N)

For the sixth subtask, it is important to know about merging two lists of scores. Let S be the final list, and Q+R=S where Q and R are smaller lists. Suppose all of the elements in Q are equal/greater than the elements in R, and the PP for Q and R are known. Then the PP for S can be calculated easily by this formula:

\displaystyle PP(S) = PP(Q) + r^{\text{size}(Q)} \times PP(R)

Then segment trees can be used to quickly update the PP. First, keep an array of all (V_i, i) pairs, then sort the array by V_i. At the very beginning, the leaves of the segment tree are all set to size 0, since there are no submissions yet. For every update, the old leaf needs to be set to size 0, and the new leaf set to size 1. Every node contains its own PP and size, and the user's PP can be found at the root of the segment tree. Make sure to keep another array which stores r^0, r^1, \dots, r^{100\,000} so that the formula is efficient. Lazy propagation is not needed.

To do this problem onlinely, it is possible to use a balanced binary search tree (BBST) and the formula described above (except with a slight modification). Every node contains a PP, and lazy propagation is not needed because every node can store its size. I don't see a way to use pb_ds, sorry Kirito.

Time Complexity: \mathcal{O}(N \log N)


Comments

There are no comments at the moment.