# LAPD - Editorial

Author: Kochekov Kerim
Editorialist: Darshan Sen

EASY-MEDIUM

# 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.

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;
}
7 Likes

Hi,
I implemented O(B*B) solution
https://www.codechef.com/viewsolution/26620415 but still it’s timing out
can anyone justify why

2 Likes

I’m sorry, I think there’s some problem with the link. I guess, if your algorithm is similar to the one I mentioned above, your code is possibly having unconditional modulo operations, which should be avoided and instead, be wrapped by a conditional confirming that the modulo operation takes place only if the first operand is \geq the right operand.

Is Modulo a costly operation ?
but still I am facing TLE for one case

1 Like
1 Like

Made optimizations like using int instead of long long and it passed
https://www.codechef.com/viewsolution/26630864

1 Like

Yes, it’s pretty costly given the large ranges of numbers.

1 Like

Good job!

1 Like