O(1) Solution for this Combinatorics question
Difference between en1 and en2, changed 133 character(s)
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).↵
↵
↵
The below solution worked and i got AC: Submission Using this formula: https://codeforces.com/contest/1744/submission/179129170

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ganesh_6 2022-11-05 05:31:53 5 Tiny change: '(n).\n\n\nThe below ' -> '(n).\n\n\nUPD: The below '
en2 English ganesh_6 2022-11-04 05:28:57 133
en1 English ganesh_6 2022-11-03 23:08:03 615 Initial revision (published)