nilesh8757's blog

How to solve E & F from ABC-127 ?
By nilesh8757, history, 6 years ago, In English

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

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    thanku for ur awesome explanation..

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But how to find C(total — 2, k — 2). We cannot go the usual way.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      what do you mean by usual way?
it can be calculate in O(1) with pre calc
      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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://mirror.codeforces.com/blog/entry/66377

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

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

    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

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

      I think the function value is the sum of the differences of all other numbers to the median one.

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

      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|$$$.

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

        I missed this. Thanks a lot!

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain why is it equivalent to finding the median?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain F Binary indexed tree solution, plz

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply