You are not logged in. Please login at www.codechef.com to post your questions!

×

BIAS - Editorial

0
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

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".

asked 11 Feb, 20:30

r_64's gravatar image

7★r_64
261923
accept rate: 16%

edited 12 Feb, 15:12

admin's gravatar image

0★admin ♦♦
19.5k348496535


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

link

answered 12 Feb, 17:49

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

edited 12 Feb, 18:00

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, 02:05) abx_21095★

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

(14 Feb, 02:13) vivek_19982996★

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.

link

answered 13 Feb, 00:50

gorre_morre's gravatar image

7★gorre_morre
4799
accept rate: 41%

@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) userhacker4★

i am opposing with final test-case. 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 /:

link

answered 13 Feb, 02:12

userhacker's gravatar image

4★userhacker
101
accept rate: 0%

edited 13 Feb, 02:13

this type of problem need 1000 test-file while you test it with just 20 test-file /:

link

answered 13 Feb, 02:17

userhacker's gravatar image

4★userhacker
101
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,026
×736
×232
×47
×10

question asked: 11 Feb, 20:30

question was seen: 758 times

last updated: 14 Feb, 02:13