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.net/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.net/contest/1744/submission/179129170
Could you briefly explain your approach? or how did u arrive at this?
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
. An arithmetic progression.
Sorry. $$$b \le m$$$. it's the same problem. you can deal 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)}
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!
$$$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$$$.