×

BIAS - Editorial

Tester: Hanlin Ren
Editorialist: Hanlin Ren

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.

View Content

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.

This question is marked "community wiki".

7★r_64
261924
accept rate: 16%

19.7k350498541

 1 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 '18, 17:49 1.6k●2●9 accept rate: 23% 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]. (14 Feb '18, 02:05) abx_21094★ I did like,just sort them,and given l[i] to first n/3,r[i] to last n/2 (14 Feb '18, 02:13)
 0 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. answered 13 Feb '18, 00:50 954●2●10 accept rate: 42% @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 '18, 22:59)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,490
×820
×233
×47
×10

question asked: 11 Feb '18, 20:30

question was seen: 814 times

last updated: 14 Feb '18, 02:13