### PROBLEM LINK:

**Author:** Hasan Jaddouh

**Tester:** Hanlin Ren

**Editorialist:** Hanlin Ren

### DIFFICULTY:

Challenge

### PREREQUISITES:

### PROBLEM:

There is a contest with N participants and M problems. The score of i-th participant from j-th problem is the maximum score of j-th problem, multiplied by A[i][j]/10^6. The maximum score of i-th problem should lie in the interval [L_i,U_i]. Assign a set of maximum scores, such that the number of **inversions** is minimized. A pair of participants (i,j) is an inversion if i < j and the total score of i is less than the total score of j.

### EXPLANATION:

The tester uses a simple hill-climbing algorithm to reach a performance of 0.469 points(compared to the best solution in contest). Let scr_i be the maximum score of i-th problem, firstly we assign scr_i to be a random number in [L_i,U_i]. Then we repeat the following āadjustmentā steps until time is going to run out:

Find a random i and assign scr_i to a new random number. If this doesnāt decrease the number of inversions, undo the step.

In pseudocode:

```
i = randint(1, m)
j = scr[i]
scr[i] = randint(L[i], U[i])
if new_result > result
scr[i] = j
else
result = new_result
```

We can accelerate the algorithm so that we perform as many steps as possible. Since only one problem has its maximum score changed, we only need O(n) time to update scores of participants. Then we compute the inversion using O(n\log n) time. A well-implemented solution can have about 2500 adjustment steps in 0.6\texttt{s} per test. For more details, see Testerās Solution below.

## How to compute inversions in O(n\log n) time

## Click to view

Now we have scores of participants s_1, s_2, \dots, s_n. We want to count the number of inversions. Note that in our context, an inversion is a pair i,j s.t. i < j and s_i < s_j. (The definition is not the standard one; however the algorithm is.)

Weāll use a divide-and-conquer method to count inversions:

- Let \mathrm{Solve}(s) do the following two things: return the number of inversions in s, and
**sort the sequence s in descending order**. (Youāll know why we need to sort it later.) - Let m=\lfloor n/2\rfloor, i.e. divide the sequence into two halves.
- Let inv=\mathrm{Solve}(s_{1\sim m})+\mathrm{Solve}(s_{m+1\sim n}). Now inv is the number of inversions such that 1\le i < j\le m or m < i < j \le n.
- We need to count the number of inversions such that 1\le i\le m and m+1\le j\le n. Note that s_{1\sim m} and s_{m+1\sim n} are
**sorted**, so we can count them in O(n) time. - More precisely, for any 1\le i\le m, let j be the smallest index in [m+1,n] such that s_j \le s_i, then there are j-m-1 inversions whose first element is i. We can maintain i,j in one iteration of the sequence, thus time complexity is O(n). See pseudocode for better understanding.

```
j = m + 1
for i = 1 to m
while j <= n and s[j] > s[i]
j += 1
inv += (j - m - 1)
```

- Then we need to sort the whole sequence s.
- You may be confused since sorting needs O(n\log n), and the total time complexity would become O(n\log^2 n). But, note that s_{1\sim m} and s_{m+1\sim n} are already sorted; what we do is only
**combining them into one big sorted list**. This task can be done in linear time: each time we take the bigger number from the head of two lists and remove it. See Merge sort. - In total, the time complexity is O(n\log n). Testerās solution has a clear implementation of it.

### ALTERNATIVE SOLUTION:

This is a challenge problem, so we expect many different and smart solutions. Please feel free to share your approaches

### AUTHORāS AND TESTERāS SOLUTIONS:

Authorās solution can be found here.

Testerās solution can be found here.