### 1600's blog

By 1600, history, 5 months ago, ,

Can anyone share their approach for problem E and F from the contest ?

• +12

 » 5 months ago, # |   +16 For E the problem can be reduced to finding sum of Manhattan distances between every pair of points . Now it can be seen that in all possible combination of selected k squares every pair of points will occur C(n*m-2,k-2) times as we have to select k-2 points from n*m-2 points as we have already fixed 2 points. So the answer can be simply written as = C(n*m-2,k-2)*d where d denotes the sum of Manhattan distances between all pair of points which can be easily found out
•  » » 5 months ago, # ^ |   +2 thanku for ur awesome explanation..
•  » » 5 months ago, # ^ |   0 But how to find C(total — 2, k — 2). We cannot go the usual way.
•  » » » 5 months ago, # ^ |   0 what do you mean by usual way? it can be calculate in O(1) with pre calc 
•  » » » 5 months ago, # ^ |   +8 I am not sure but finding binomial coefficients modulo a prime is a very common problem and occurs in many problems. You can refer this blog for more details https://codeforces.com/blog/entry/66377
•  » » » 5 months ago, # ^ |   0 You are right we can not got it the usual way, because numbers are too big. So we need to calculate (total-2)*(total-3)*...*(total-2-(k-2)) / (k-2)*(k-3)*..*2And we are asked to print the answer in module 1e9+7 , moreover division doesn't work with modulo.do instead of calculating numerator and denominator and divide them, we should calculate modular multiplicative inverse of the denominator. and devide (total-2)*(total-3)*...*(total-2-(k-2)) part to modular multiplicative inverse of (k-2)*(k-3)*..*2 . You can find modular multiplicative inverse using fermats little theorem. for that you need to calculate denominator^(mod-2) . and since mod is too big you need to calculate this using binary exponentiation.Problem is pretty educative i believe.
 » 5 months ago, # |   +14 F: First, notice that the b values don't matter, accumulate them in a separate variable and add them to the answer when outputting. Finding the $x$ that minimizes $\sum |x - a_i|$ is equivalent to finding the median of the set of ${ a_i }$. This is a classic problem, which can be solved with two sets (or multisets if the values can repeat). Actually computing the function also requires storing the sum of each set.
•  » » 5 months ago, # ^ |   +3 Can you elaborate on how to compute the function? I figured out how to find the value which minimizes the sum but couldn't find out how to compute the function without iterating over all the numbers
•  » » » 5 months ago, # ^ |   +3 I think the function value is the sum of the differences of all other numbers to the median one.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +10 Sure. The classic online median finding algorithm uses two sets $L$ and $R$, where everything in $L$ is less than or equal to the median, and everything in $R$ is greater than the median.We want to compute $\sum |x - a_i|$, where $x$ is the median of $a_i$, By the way we've defined $L$ and $R$, we can break this up into two.$\sum |x - a_i| = \sum_{y \in L} (x - y) + \sum_{z \in R} (z - x)$Say we've precomputed the sums of $L$ and $R$. Then this boils down to $x \cdot |L| - (\sum_{y \in L} y) + (\sum_{z \in R} z) - x \cdot |R|$.
•  » » » » 5 months ago, # ^ |   +3 I missed this. Thanks a lot!
•  » » » » 5 months ago, # ^ |   -8 how to calculate that summation I to have found that the median minimizes the function what about that summation. pLz, tell as it will be really helpful.
•  » » 5 months ago, # ^ |   0 Can you please explain why is it equivalent to finding the median?
•  » » » 5 months ago, # ^ |   0 I found this quora answer by misof quite intuitive, you can refer it.
•  » » » » 5 months ago, # ^ |   0 ohhhh, thanks now i get it.
 » 5 months ago, # |   0 Can someone explain F Binary indexed tree solution, plz
 » 5 months ago, # |   -8 The solutions have already been explained by other people here. :)The main insight to solve E is to count the number of times each pair is counted, rather than iterating over all $K$ combinations. The main insight to solve F is to notice that Bs are constant, and that the answer to minimise $f(x)$ is the median. We can evaluate the function $f(x)$ quickly by dividing all the A's into two halves $A_1$ and $A_2$. Let $A_1$ contain all elements smaller than or equal to the median and let $A_2$ contain all elements larger than the median. If we just know the sum of $A_1$ and $A_2$, then we can find out $f(x)$ in $O(1)$ time. Here is my GitHub repository consisting of all my programs and explanations. As an experiment, I have started posting some 'rough' notes that I make while working my way through the problem as well. It is not intended to be the full and formal solution. Just some thoughts and key points.