An ordered triple (a, b, c) is called a triangle triple if a, b, c are positive integers such that there is a triangle with side lengths a, b, c and a positive area.
find number of ordered triplet (a, b, c) such that a <= A, b <= B and c <= C
Input: A, B, C (all between 1 to 10^9)
Output: Number of triplets Mod 10^9 + 7
Problem: [Link] Can someone please help me solving this problem?
Let X be the answer. It's easy to see that X = A * B * C — numberOfBadTriples. Bad Triples are triples where one of numbers is more of eq to sum of another 2. So the only problem now to score them fast. Let firstly score number of triples where C >= A + B. What is it? It's Sum(i,1,A)(Sum(u,1,B)(Max(0,C — i — u))); It's easy to see that Max(0,C — i — u) == C — 2 only for i==u==1, Max(0,C — i — u) == C — 3 in 2 cases: i==1, u==2 and i==2, u==1, Max(0,C — i — u) == C — 4 in 3 cases and so on. It's the main idea and then it's easy find O(1) formula for this sum, it I will leave for u)