Блог пользователя cm_ashish

doubt in ARC 104-D , Multiset median
Автор cm_ashish, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +8 Проголосовать: не нравится

    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

    → Ответить