| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
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
thanku for ur awesome explanation..
But how to find C(total — 2, k — 2). We cannot go the usual way.
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.me/blog/entry/66377
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)*..*2
And 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.
See my code: https://atcoder.jp/contests/abc127/submissions/5641879
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.
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
I think the function value is the sum of the differences of all other numbers to the median one.
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|$$$.
I missed this. Thanks a lot!
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.
Can you please explain why is it equivalent to finding the median?
I found this quora answer by misof quite intuitive, you can refer it.
ohhhh, thanks now i get it.
Can someone explain F Binary indexed tree solution, plz
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.