cm_ashish's blog

doubt in ARC 104-D , Multiset median
By cm_ashish, history, 6 years ago, In English

this is the question i am trying to solve .
this is its editorial .

I didn't quite understood soln in the editorial . I got that they are pre computing knapsack dp of n*n*k
that is knapsack dp of sum . But i didn't understand the fulcrum concept . they say that you have to take
subset from { 1 , 2 , .... ,m-1 } and { 1 , 2, ...... , n-m} . why i mean how will it solve the question ??
what are they trying to say?

Even the smallest help is welcome , i tried asking my friends but they also don't understand the editorial.
thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Let $$$a_i$$$ equal to the number of $$$i$$$ in the set, and $$$x$$$ the average of numbers, then we have:

$$$ \begin{aligned} &\frac{\sum\limits_{i=1}^nia_i}{\sum\limits_{i=1}^na_i}=x\\ \Leftrightarrow&\sum\limits_{i=1}^n(i-x)a_i=0\\ \Leftrightarrow&\sum\limits_{i=1}^{n-x}ia_{x+i}=\sum\limits_{i=1}^{x-1}ia_{x-i} \end{aligned} $$$

Found that the restrictions on all $$$a_i$$$ are the same, so we need to choose two sequences length $$$n-x$$$ and $$$x-1$$$, and the sums are equal, like the editorial.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +8 Vote: I do not like it

    Thanks bro got it. I was confused that i we have sum of numbe both array will overlap and frequency of number will be more than k. But i was wrong the numbers are syemtric so sum of n-x is actually from number greater than x and sum of x-1 is from numbers lower than x so they will not overlap. Thanks

    → Reply