PROBLEM LINK:
Author: Kochekov Kerim
Editorialist: Darshan Sen
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Counting, Well-ordering theorem
PROBLEM:
Find the number of integer triples (a, b, c) s.t. a \in [1, A], b \in [1, B], a \in [1, C]
and ax^2+2bxy+cy^2>x^2+y^2, \forall(x, y) \in \mathbb{R}^2.
EXPLANATION:
ax^2+2bxy+cy^2>x^2+y^2
\implies (a-1)x^2+2bxy+(c-1)y^2>0
Let’s change the domains of a and c to:
a \in [0, A - 1] and c \in [0, C - 1]
\implies ax^2+2bxy+cy^2>0
a and c cannot take value 0 because, the inequality will not hold for all values of x and y.
So, we can safely substitute the value of A with A - 1 and the value of C with C - 1:
a \in [1, A] and c \in [1, C]
Hence,
ax^2+2bxy+cy^2>0
a \in [1, A], b \in [1, B] and c \in [1, C]
\implies b^2 < ac (reference)
\forall b \in [1, B]:
\forall a \in [1, A], if b^2<ax, all triplets (a,b,y) s.t. x \leq y form valid solutions. So, if we find the minimum value of x<C, then corresponding to a, we will have (C-x+1) solutions.
We can deduce the same similarly for the triplets of the form (_ ,b,c), \forall c \in [1, C].
NOTE:
We will find that if we simply combine both the lists of triplets, every triplet will be in pairs:
Since all the triplets are unique, according to the well-ordering theorem, the subset of solutions of the form (a, b, _) has minimum element (a, b, x). Similarly, the subset of solutions of the form ( _ , b, x) has minimum element (z, b, x). Since, we built the elements by minimizing a and c, a must equal z.
So, if we compute half of the number of such triplets, we would have the correct answer, but our solution would have a complexity of O(B*max(A,C)). Given the orders of magnitude of A, B and C, we can observe that such a solution is not feasible.
Hence, we resort to another observation:
Let’s fix b and find each corresponding y for a few a starting from 1:
a \hspace{0.73cm}| y
1 \hspace{0.74cm}| b^2+1
2 \hspace{0.74cm}| \leq b^2
. \hspace{0.74cm} | .
. \hspace{0.74cm} | .
. \hspace{0.74cm} | .
b \hspace{0.77cm}| b+1
b+1 \hspace{0.17cm}| b
b+2 \hspace{0.17cm}| \leq b
. \hspace{0.74cm} | .
. \hspace{0.74cm} | .
. \hspace{0.74cm} | .
b^2 \hspace{0.61cm}| 2
b^2+1 | 1
b^2+2 | 1
. \hspace{0.74cm} | .
. \hspace{0.74cm} | .
. \hspace{0.74cm} | .
We are repeating calculations!
Instead of performing the aforementioned process on all values of a, let’s do it on only
a \in [1,min(A,b)] and c \in [1,min(C,b)].
We are only left with values of a and c greater than b.
With those, we only add all possible triplets (a,b,c) from the remaining a
(i.e., max(0, A-b)) and remaining c (i.e., max(0, C-b)). Number of such possible combinations is the simple product of the cardinalities of the set of remaining a and the set of remaining c.
Summing these numbers brings us to the required result.
TIME COMPLEXITY:
O(B^2)
SOLUTIONS:
Editorialist's Solution
#include <iostream>
#define MOD 1000000007
typedef long long ll;
int solve (int A, int B, int C) {
// 1≤a≤A , 1≤b≤B and 1≤c≤C
// for any two real numbers 'x' and 'y'
// such that x≠0 and y≠0,
// ax^2+2bxy+cy^2>x^2+y^2
// => (a-1)x^2+2bxy+(c-1)y^2>0
// => ax^2+2bxy+cy^2>0; s.t. a∈[1,A-1], c∈[1,C-1]
// => b^2<ac
// Reference:
// https://www.quora.com/Why-is-the-inequality-ax-2-+-2bxy-+cy-2-0-equivalent-to-b-2-ac-0-when-a-0-x-y-neq-0-0
ll res = 0LL;
--A; // A←A-1
--C; // C←C-1
for (int b = 1; b <= B; ++b) {
int b_squared = b * b;
int minimum_of_b_and_A = std::min(A, b);
int minimum_of_b_and_C = std::min(C, b);
// For any 'a', if b^2<ax, all triplets (a,b,y) s.t. x≤y form a valid solution.
// So, if we find the minimum value of x<C, then corresponding to 'a',
// we will have (C-x+1) solutions.
// We can do so similarly for the triplets (p,b,a) for the corresponding 'p's.
// We will find that if we combine both the lists of triplets,
// every triplet will be in pairs because
// the minimum value 'x' for 'a' forms a triplet (a,b,x)
// and the minimum value '_' for 'x' to form such a triplet is 'a'!
// So, we may find the half of the number of such triplets.
// That, would give us the correct answer,
// but, our solution would have a complexity of O(B*max(A,C)).
// Given the orders of magnitude of A, B and C, we can observe that
// such a solution is not feasible.
// Hence, we resort to another observation:
// > Let us fix 'b' and find the corresponding 'y's for a few 'a's starting from 1:
// > a y
// > 1 b^2+1
// > 2 ≤b^2
// > . .
// > . .
// > . .
// > b b+1
// > b+1 b
// > b+2 ≤b
// > . .
// > . .
// > . .
// > b^2 2
// > b^2+1 1
// > b^2+2 1
// > . .
// > . .
// > . .
// We are repeating calculations!
// Instead of performing the aforementioned process on all the 'a's,
// let's do it on the 'a's only in range(1,min(A,b))
for (int a = 1; a <= minimum_of_b_and_A; ++a) {
int c = (b_squared + a - 1) / a; // ceil(b^2/a)
if (a * c == b_squared) // correcting 'c' such that ac>b^2
++c;
if (c <= C) { // valid values of 'c' only
// res←(res+C-(c+1))%MOD
res = 1LL + res + C - c;
res = (res >= MOD ? res % MOD : res);
}
}
// and for all 'c's in range(1,min(C,b)).
for (int c = 1; c <= minimum_of_b_and_C; ++c) {
int a = (b_squared + c - 1) / c; // ceil(b^2/c)
if (a * c == b_squared) // correcting 'a' such that ac>b^2
++a;
if (a <= A) { // valid values of a only
// res←(res+A-(a+1))%MOD
res = 1LL + res + A - a;
res = (res >= MOD ? res % MOD : res);
}
}
// We are only left with 'a's and 'c's greater than 'b'.
// With those, we only add all possible triplets
// (a,b,c) from the remaining 'a's(i.e., max(0, A-b))
// and remaining 'c's(i.e., max(0, C-b)).
// Number of such possible combinations is
// the simple product of the cardinalities of
// the set of remaining 'a's and
// the set of remaining 'c's.
int remaining_as = std::max(0, A - b);
int remaining_cs = std::max(0, C - b);
res = 1LL * remaining_as * remaining_cs + res;
res = (res >= MOD ? res % MOD : res);
}
// This brings us to the actual solution!
return res;
// Complexity of the solution is O(B^2).
}
int main() {
int T;
std::cin >> T;
while (T--) {
int A, B, C;
std::cin >> A >> B >> C;
std::cout << solve(A, B, C) << std::endl;
}
return 0;
}
