### ganesh_6's blog

By ganesh_6, history, 5 months ago,

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

• 0

 » 5 months ago, # |   +4 $\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}$
•  » » 5 months ago, # ^ |   +4 Could you briefly explain your approach? or how did u arrive at this?
•  » » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   0 Sorry. $b \le m$. it's the same problem. you can deal it
•  » » » » 5 months ago, # ^ |   0 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)}
•  » » » » » 5 months ago, # ^ |   +8 $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}$
•  » » » » » » 5 months ago, # ^ | ← Rev. 3 →   0 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!
•  » » » » » » » 5 months ago, # ^ |   0 $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$.
•  » » » » » » » » 5 months ago, # ^ |   0 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!
•  » » » » » » 5 months ago, # ^ | ← Rev. 7 →   0 Your formula is correct!
•  » » » » » » 5 months ago, # ^ |   0 One more correction: Take K=Math.min(K, M+N) otherwise we get negative values
•  » » » » » » 5 months ago, # ^ |   0 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
 » 5 months ago, # |   0 Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).
 » 5 months ago, # |   0 Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).