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

Sum of medians of all subsets
Автор bihariforces, история, 20 месяцев назад, По-английски

Let's stick to only odd-length subsets for simplicity, given an array of integers, find sum of median of all subsets mod $$$1e9 + 7$$$, median is the middle element for odd-length subsets when sorted.

First step would obviously be sorting but then to count number of subsets whose median is $$$arr[i]$$$ we need to find number of ways to pick equal number of elements from it's left and right, if left has $$$x$$$ elements and right has $$$y$$$ elements, then,

$$$ count(subsets) = \sum_{i=0}^{\min(x,y)} \binom{x}{i} \binom{y}{i} $$$

Finding this for each element would make it $$$O(N^2)$$$, is there a faster method to find the sum of binomial coefficients as shown above efficiently possibly with some precomputation? Or some entirely different approach to solve the original problem?

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

»
20 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

That count is just (x+y)Cy. x+y is always n-1 btw.

→ Ответить
»
20 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
$$$\sum\limits_{i=1}^{\min(x,y)}\binom{x}{i}\binom{y}{i}=\sum\limits_{i=1}^{\min(x,y)}\binom{x}{i}\binom{y}{y-i}=\binom{x+y}{y}$$$
→ Ответить