ganesh_6's blog

O(1) Solution for this Combinatorics question
By ganesh_6, history, 18 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

Comments Comments (8)
| Write comment?
»
18 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
  • »
    »
    18 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
    • »
      »
      »
      18 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
    • »
      »
      »
      18 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
      • »
        »
        »
        »
        18 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
        • »
          »
          »
          »
          »
          18 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
          • »
            »
            »
            »
            »
            »
            18 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
            • »
              »
              »
              »
              »
              »
              »
              18 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