Contest

EASY-MEDIUM

Conics, Counting

# PROBLEM:

We need to find the number of pairs of a, b and c such that

• a\in[1, A] , b\in[1, B], c\in[1, C].
• ax^2+2bxy+cy^2 > x^2+y^2 holds for \forall x,y\in(-\infty, 0)\cup(0,+\infty) .

# STRATEGY

First, let’s try to simplify the above equation, on simplifying we’ll get->
let \Theta = (a-1)x^2+2bxy+(c-1)y^2 > 0.
This is an equation for conics. Note that for \Theta to hold true, the equation must correspond to that of an ellipse with both r_{1} = r_{2} = 0. For \Theta to be an ellipse, it must satisfy Q^2 - 4*P*R < 0 where P=a-1, Q=2b, R=c-1. We get the relation b^2 < (a-1)(c-1).
Now our question reduces to finding the number of pairs of a and c which when multiplied give the result as greater than b^2.
Let’s try to find the number of pairs of a, c such that a*c<=b^2. The solution to this problem is simply the summation of the following series->
\phi = \sum_{k=1}^N \lfloor N/k \rfloor (try it yourself)
However, using this takes \theta(N) time which is too much. We can reduce \phi as follows using a neat counting trick ->
let \phi' = 2*\sum_{k=1}^ {\lfloor\sqrt[2]N \rfloor} \lfloor N/k \rfloor + \lfloor\sqrt[2]N \rfloor^2
You can arrive at this result by making possible pairs yourself and choosing only up to \sqrt[2]N of the pairs. However, we cannot use this formula directly as there’s an upper bound on A and C whereas there’s no bound in the formula. We’ll call this summation root_summation. You can look up how it’s implemented in the code given below. The time complexity of this summation would be \theta(\sqrt[2]N).

# ALGORITHM

A := A - 1;
C := C - 1;
let total = A*C;
let sum = 0;
for b in B {
sum = (sum + total - root_summation(b*b, A, C)) % MOD;
}


# CODE

#include <iostream>
#include <cmath>

long long MODULO = pow(10, 9) + 7;

int main() {

// freopen("input.txt", "r", stdin);

int T;
scanf("%d", &T);

while (T--) {
long long A, B, C;
scanf("%lld %lld %lld", &A, &B, &C);
A -= 1; C-= 1;

long long count = 0;
long long total = A*C; // TAKE MOD

for (int i=1; i<=B; i++) {

int p = i*i;
int max_range;
int limiting;
int full_range;
bool use_rootsum = false;
if (A < C) {
if (A <= i) {
max_range = A;
limiting = C;
full_range = A;
} else {
max_range = i;
full_range = C;
limiting = A;
use_rootsum = true;
}
} else {
if (C <= i) {
max_range = C;
full_range = C;
limiting = A;
} else {
max_range = i;
full_range = A;
limiting = C;
use_rootsum = true;
}
}

long long sum = 0;
long long diff = 0;

for (int a=1; a<=max_range; a++) {;
diff = diff + std::max(0, (std::min(full_range, p/a) - limiting));
sum = sum + std::min(limiting, p/a);
}

sum = sum  + use_rootsum*(sum - p + diff);

count = (count + total-sum) % MODULO;
}

printf("%lld\n", count);

}

return 0;
}


# TIME COMPLEXITY

The time complexity of the algorithm discussed in this editorial is O(N*\sqrt[2]N) per test case.

2 Likes

My similar-logic submission with comments - https://www.codechef.com/viewsolution/26622158

EDIT: Added more explanations and linked to some visualizations as well.

Poorly written Editorial, you haven’t explain things in detail, looks like just copied from somewhere.

4 Likes

The main point in the problem is root_summation
but that is not explained

4 Likes

Hi everybody,
I just want to correct myself. Please tell me where I am wrong in terms of solving LAPD.

So basically we have given an equation ax^2 + cy^2 + 2bxy > x^2 + y^2.
so it can be re-written as -> b(x+y)^2 + (a-b-1)x^2 + (c-b-1)y^2 > 0.
b(x+y)^2 >= 0 for all b >= 1 for given condition of x and y.

(a-b-1)x^2 > 0 if a > b-1 and (c-b-1)y^2 > 0 if c > b-1.

So the problem reduces to finding a and c above such that a > b-1 and c > b-1, also if a = b-1 then c > b-1 and if c = b-1 then a > b-1.

So for each b = 1 to B, I calculated a = A-b and c = C-b then calculated (a*c - 1) and added it to the answer.

Can you please tell me why this approach is wrong.

My Wrong Solution

Thank you.

How do you know that they are the “only” (a, c) combinations that satisfy this? Did you prove there can’t be more?

1 Like

I’m really sorry that I couldn’t explain this better. This was my first time writing editorials. Maybe I’ll explain in detail what exactly root_summation does and how it does by morrow?

2 Likes

I’ve made this editorial for LAPD. Hope this clears your doubts. My algorithm is pretty simple.

1 Like

1 Like

What is N ??
Now will I have to read each and every line of editorial for understanding what is N ?
Complexity is O(N*\sqrt{N})
Mine was O(T*B*B).
Are our approach different ??

1 Like

@vijju123 or @neverwannafly
Can you rename editorial as unofficial please ?
People are getting confused.