LAPD - Editorial

PROBLEM LINK:

Practice
Contest

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;
	}
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. :slight_smile:

Is Modulo a costly operation ?
I made the change https://www.codechef.com/viewsolution/26629369
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! :slight_smile:

1 Like