root8950's blog

How to solve this Question
By root8950, history, 11 years ago, In English

I am unable to find approach to this question. https://www.codechef.com/IOPC2016/problems/IOPC16Q The contest is over and there is no editorial. Anybody having idea how to solve it?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Tutorial in Chinese and the code here

I'll do my best to explain in English.

First we know if we only have to choose a number x , the answer will be the median.
The only property we need to know for this problem is the best choice of x and y must separate the array into two consecutive part: 1 ~ M for x and M+1 ~ n for y.
What we should do is enumerate M and calculate the cost of two independent parts in O(1) for each M.

Hope it helps :).

→ Reply