PROBLEM LINK:Author: Hasan Jaddouh 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 hillclimbing 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:
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 wellimplemented 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)$ timeALTERNATIVE 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.
This question is marked "community wiki".
asked 11 Feb, 20:30

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 answered 12 Feb, 17:49
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*(n1)/4 I assigned the value r[i] to the column else l[i].
(14 Feb, 02:05)
I did like,just sort them,and given l[i] to first n/3,r[i] to last n/2
(14 Feb, 02:13)

One thing that works surprisingly well is to multiply each $A_{ij}$ with the factor $(n/2i)$ and then summing all the columns to get $C_j = \sum_{i=1}^n A_{ij} * (n/2i)$. 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. answered 13 Feb, 00:50
@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!
(13 Feb, 22:59)

i am opposing with final testcase. my code give better solution from some people that get more point. i generate many test case and see. even in some case my code very better result from those /: answered 13 Feb, 02:12

this type of problem need 1000 testfile while you test it with just 20 testfile /: answered 13 Feb, 02:17
