ganesh_6's blog

O(1) Solution for this Combinatorics question
By ganesh_6, history, 5 months ago, In English

Given a positive integer k and two non-negative integers n and m such that we need to take out a certain non-negative integer from n and certain non-negative integers from m such that the sum of these two is <=k.

Formally, n, m>=0, and k>0. Number of ways to take a and b from n and m such that

0<=a+b<=k

The number of such (a,b) pairs?

I can do it in a linear solution. Any O(1) combinatorics solution? Please let me know. I need this solve https://codeforces.com/problemset/problem/1744/F -> I got an idea where in i want to optimize from O(n*n) to O(n).

UPD: The below solution worked and i got AC: Submission Using this formula: https://codeforces.com/contest/1744/submission/179129170

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it
$$$\sum_{a=n}^{m}\sum_{b=n}^{m}[a + b \le k] = \sum_{a=0}^{m-n}\sum_{b=0}^{m-n}[a + b \le k - 2 \times n]$$$
$$$n' = 0, m' = n - m, k'= k - 2 \times n$$$
$$$ans = k' + (k' - 1) + ... + (k' - m') = \frac{(2\times k' - m') \times (m' + 1)} {2}$$$
→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Could you briefly explain your approach? or how did u arrive at this?

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

      step 1
      $$$a \ge n,b \ge n$$$. u can subtract n from a and b. so $$$k$$$ being $$$k - 2n$$$

      step 2
      $$$a = x,0 \le b \le k - x$$$.

      So

      $$$ans = \sum_{a = 0}^{m} k - a$$$

      . An arithmetic progression.

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

      Sorry. $$$b \le m$$$. it's the same problem. you can deal it

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

        I think you misunderstood my question. For example, if k=3 and i have n=2 and m=3. Then there are 9 possibilities for (a, b) a belongs to n and b belongs to m. {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1)}

        → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it
          $$$n = \min(k, n), m = \min(k, m)$$$
          $$$ans = \sum_{a=0}^{n} min(k - a + 1, m + 1) = \sum_{a=0}^{k - m} (m + 1) + \sum_{a=k - m + 1}^{n} k - a + 1 = (k - m + 1) \times (m + 1) + \frac{(m + k - n + 1) \times (n + m - k)} {2}$$$
          → Reply
          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            Thanks, could you explain how did u arrive from

            $$$\sum_{a=0}^{n} min(k-a+1, m+1)$$$ to $$$\sum_{a=0}^{k-m} (m+1) + \sum_{a=k-m+1}^{n} k-a+1$$$

            I appreciate your effort!

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

              $$$k - a + 1$$$ will become smaller. you can find a bound that $$$min(m + 1, k - a + 1) = k - a + 1$$$. $$$k - a + 1 < m + 1$$$. $$$a > k - m$$$.

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

                I understand, Basically you are splitting the range [0, n] to [0, k-m] + [k-m+1, n] because in those range one of the values inside min becomes that value so that we can formulate some math formula. Thanks! This is cool!

                → Reply
          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
            ← Rev. 7   Vote: I like it 0 Vote: I do not like it

            Your formula is correct!

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

            One more correction: Take K=Math.min(K, M+N) otherwise we get negative values

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

            Hurrah! Your formual worked and i got AC after handling edge cases like K becoming negative or K exceeding M+N value.

            Submission Using this formula: https://codeforces.com/contest/1744/submission/179129170

            → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).

→ Reply