BIAS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Hanlin Ren
Editorialist: Hanlin Ren

DIFFICULTY:

Challenge

PREREQUISITES:

Counting inversions

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 :slight_smile:

AUTHORā€™S AND TESTERā€™S SOLUTIONS:

Authorā€™s solution can be found here.
Testerā€™s solution can be found here.

2

My solution fetched around 83 points bt i think it was the simplest.

Firstly for each problem i considered only two scores l[i] or r[i],so as u can see for the last test case we can just brute for all possible combination,and then check for which the number of inversions is least .(complexity 2^10n10*logn)

Now for first 4 test case:
Firstly let me tell how did i calculated inversion ,i calculate the score array ,multiply all elements by -1,and then calculate inversion.
So now lets see which problems should be preferred low score and which one high score.lets say ,if i calculate number of inversion based on independent problems(m inversions) ,so iā€™ll prefer to give low to the problem which has more inversion,and high to the problem which has less inversion.
So i assigned the values of some problems based on their independent inversion and for rest values generated randomly.

My solution:
https://www.codechef.com/viewsolution/17419828

1 Like
3

One thing that works surprisingly well is to multiply each A_{ij} with the factor (n/2-i) and then summing all the columns to get C_j = \sum_{i=1}^n A_{ij} * (n/2-i). Finally choose the scores P_j to maximize \sum_{j=1}^m C_j*P_j.

So let score j be U[j] if C_j>0 or otherwise let the score be L[j]. I donā€™t really know why this works as well as it did. This with some small optimizations got me to $13$th place.

4

@gorre_morre your way for Cj=Sigma(Aijāˆ—(n/2āˆ’i)) is wonderful! and for L[i] and U[i] we can use one combination of all L[i] or R[i] for each problem and get final points with L[i] and R[i] for each problem(for Example : L1,R2,L3,L4,R5, ā€¦ ). in practice i extend range of each l[i] and R[i] to L[i]-x , R[i]+x (x>0) and i see better result(before print points for problem i change again its to L[i] and R[i]). it was wonderful. i do it in my last submit and get better result. so your approach and this tip make more point. both was wonderful for me!

5

I too did something similarā€¦assigned either l[i] or r[i] to each column depending on the number of inversions of that column(which I calculated using segment tree).If number of inversions <= n*(n-1)/4 I assigned the value r[i] to the column else l[i].

6

I did like,just sort them,and given l[i] to first n/3,r[i] to last n/2