LAPD - Unofficial Editorial

PROBLEM LINK:

Contest

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

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 - CodeChef: Practical coding for everyone

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
Link :- CodeChef: Practical coding for everyone

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. :slightly_smiling_face:

1 Like

How about this editorial? I’ve used a simpler algorithm. :slightly_smiling_face:

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.