LAPD - Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

Setter : Kochekov Kerim

Tester : Istvan Nagy

Editorialist : Anand Jaisingh

DIFFICULTY

Medium

PREREQUISITES :

Sylvester’s Criterion, Basic Arithmetic skills

PROBLEM :

Given 3 integers A,B,C, you need to find the number of positive triplets of integers (a,b,c) , such that 1 \le a \le A , 1 \le b \le B , 1 \le c \le C and for any two real numbers x \ne 0 and y \ne 0 , ax^2+2bxy+cy^2 > x^2 +y^2

QUICK EXPLANATION :

We can re-write the given inequality as (a-1) \cdot x^2 +2bxy +(c-1) \cdot y^2 > 0 . Let P(x,y)=(a-1) \cdot x^2 +2bxy +(c-1) \cdot y^2. We can re-write P(x,y) as img

Now, P(x,y) > 0 \forall x \ne 0 , y \ne 0 if the matrix in the middle is Positive definite , after which we use Sylvester’s Criterion for Positive Definiteness of a matrix and some ad-hoc logic to find possible values of (a,b,c).

EXPLANATION :

The first thing that comes to mind is that we can rearrange the given inequality a little bit. We can :

ax^2+2bxy+cy^2 > x^2 +y^2

ax^2 - x^2 +2bxy +cy^2 -y^2 > 0

x^2(a-1) + 2bxy + y^2(c-1) >0

(a-1)\cdot x^2 + 2bxy +(c-1) \cdot y^2 > 0

Now, let P(x,y)= (a-1) \cdot x^2 + 2bxy + (c-1) \cdot y^2

Note that P(x,y) is a polynomial in two variables (x,y)

We can rewrite using a matrix equation as :

P(x,y) =

img

For this polynomial P(x,y) to be > 0 for all x \ne 0 and y \ne 0 , we need the matrix

net-resizeimage%20(1)

To be Positive Definite. Now, Sylvester’s Criterion says that the given matrix is Positive Definite, if all its Principal Minor’s ( A Principal Minor is the determinant of some top left k \cdot k matrix ) are positive.

This gives us two equations to solve :

(1) (a-1) > 0, \hspace{0.2cm} a > 1

(2) (a-1) \cdot (c-1) - b^2 > 0 , \hspace{0.2cm} (a-1) \cdot (c-1) > b^2

Now, we’ve reduced our original problem to the following :

For each b in the range [1,B] we need to find the number of pairs of integers (a,c), 1 \le a \le A , 1 \le c \le C and (a-1) \cdot (c-1) > b^2 . Since B is rather small, we can simulate this process.

Let’s see how we can do this for a fixed integer b.

An important observation we can make is that if both (a-1) and (c-1) are > b , then the product (a-1) \cdot (c-1) is > b^2 , and if (a-1) and (c-1) < b then (a-1) \cdot (c-1) < b^2

So we are left with 3 cases to consider

Case 1 :

Both (a-1) and (c-1) are > b . In this case, the answer is the number of lattice points inside the rectangle [b+1,A-1] \times [b+1,C-1]

Case 2 :

Here we consider the case when a-1 \le b . For some (a-1) \le min(b,A-1) , the minimum number it needs to be multiplied by is \left\lfloor\frac{b^2}{a-1}\right\rfloor +1 . So we iterate over each possible a in the range [2,min(b,A-1)] and find the number of corresponding possible (c-1)'s

Case 3 :

And, analogous to Case 2, we do similarly when (c-1) \le min(b,C-1).

In the end, just don’t forget to take the final answer Modulo 10^9+7.

That’s it, thank you !

Your Comment’s are Welcome !

I also suggest that you read another wonderful approach by pick_pacemen in the comments section

COMPLEXITY ANALYSIS :

Time Complexity : O( T \cdot B^2 )

Space Complexity : O(1)

SOLUTION LINKS :

Setter
#include "bits/stdc++.h"
#define MOD 1000000007
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
int f(int x,int y){return int((x*1.0*x)/y);}
int mod(long long x){return (x%MOD);}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
	    int a,b,c,ans=0;
	    scanf("%d%d%d",&a,&b,&c);
	    //(a-1)(c-1)>b*b and a>1
		for(int i=1;i<=b;i++){
			ans=mod(max(0,c-i-1)*1LL*max(0,a-i-1)+ans);//1<=b+1<a,c
			for(int j=2;j<=min(a,i+1);j++)//2<=a<=b+1<c
				ans=mod(ans+max(0,c-f(i,j-1)-1));
			for(int j=2;j<=min(c,i+1);j++)//1<=c<=b+1<a
				ans=mod(ans+max(0,a-f(i,j-1)-1));
		}
		printf("%d\n",ans);		
	}
	return 0;
} 
Tester
#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
 
using namespace std;
 
long long readInt(long long l, long long r, char endd) {
	long long x = 0;
	int cnt = 0;
	int fi = -1;
	bool is_neg = false;
	while (true) {
		char g = getchar();
		if (g == '-') {
			assert(fi == -1);
			is_neg = true;
			continue;
		}
		if ('0' <= g && g <= '9') {
			x *= 10;
			x += g - '0';
			if (cnt == 0) {
				fi = g - '0';
			}
			cnt++;
			assert(fi != 0 || cnt == 1);
			assert(fi != 0 || is_neg == false);
 
			assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
		}
		else if (g == endd) {
			assert(cnt > 0);
			if (is_neg) {
				x = -x;
			}
			assert(l <= x && x <= r);
			return x;
		}
		else {
			//assert(false);
		}
	}
}
 
string readString(int l, int r, char endd) {
	string ret = "";
	int cnt = 0;
	while (true) {
		char g = getchar();
		assert(g != -1);
		if (g == endd) {
			break;
		}
		cnt++;
		ret += g;
	}
	assert(l <= cnt && cnt <= r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
	return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
	return readString(l, r, ' ');
}
 
int solver(int A, int B, int C)
{//A<=C
	int res = 0, mod = 1e9 + 7;
	for (int b = 1; b <= B; ++b)
	{//b*b < a*c
		int bb = b * b;
		//if a < c && a <= b
		for (int a = 1; a <= min(A, b); ++a)
		{
			int minc = (bb + a - 1) / a;
			while (minc * a <= bb)	
				++minc;
			if (minc <= C)
			{
				res = res + C - minc + 1;
				if (res > mod)
					res -= mod;
			}
				
		}
		//if c < a && c <= b
		for (int c = 1; c <= min(C, b); ++c)
		{
			int mina = (bb + c - 1) / c;
			while (mina * c <= bb)
				++mina;
			if (mina <= A)
			{
				res = res + A - mina + 1;
				if (res > mod)
					res -= mod;
			}
				
		}
		//if a > b && c > b
		if (A > b)
		{
			res = (res + static_cast<int64_t>(A - b)*(C - b)) % mod;
		}
	}
	return res;
}
 
int main(int argc, char** argv)
{
#ifdef HOME
	if (IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T, A, B, C;
	//T=readIntLn(1, 10);
	scanf("%d", &T);
	for (int tc = 0; tc < T; ++tc)
	{
		//A = readIntSp(1, 1000000000);
		//B = readIntSp(1, 5000);
		//C = readIntLn(1, 1000000000);
		scanf("%d %d %d", &A, &B, &C);
		int sol = solver(min(A, C) - 1, B, max(A, C) - 1);
		printf("%d\n", sol);
	}
	//assert(getchar() == -1);
	return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
 
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];
 
int mul(ll a,ll b)
{
return (a*b)%mod;
}
 
int add(int a,int b)
{
int ret=a+b;
 
if(ret>=mod)
{
    ret-=mod;
}
 
return ret;
}
 
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
 
int t;cin>>t;
 
while(t>0)
{
    int A,B,C,res=0;
 
    cin>>A>>B>>C;
 
    for(int b=1;b<=B;b++)
    {
        int sq=b*b;
 
        int r1=max(0,A-1-(b+1)+1),r2=max(0,C-1-(b+1)+1),prod=mul(r1,r2);
 
        res=add(res,prod);
 
        for(int k1=1;k1<=min(b,A-1);k1++)
        {
            int other=(sq/k1)+1;
 
            int sz=max(0,C-1-other+1);
 
            res=add(res,sz);
        }
 
        for(int z=1;z<=min(b,C-1);z++)
        {
            int other=(sq/z)+1;
 
            int sz=max(0,A-1-other+1);
 
            res=add(res,sz);
        }
    }
 
    cout<<res<<endl;t--;
}
 
return 0;
}
12 Likes

https://www.codechef.com/viewsolution/26627462 Can anyone find what did I do wrong, my order is also same as solution(at least that is what I think :frowning: )
PS: edited code to make it more concise.

We can also write the equations as follows:-
x^2(a-1) + 2bxy +(c-1)y^2 > 0

as x != 0, we can write divide by x^2 and sign of the inequation remains the same. The inequation looks like as follows:-

(a-1) +2b(y/x) + (c-1)(y/x)^2 > 0

Let y/x be t

We get
(a-1) +2bt + (c-1)t^2 > 0

The roots of the above quadratic equation are:-
-b±sqrt(b^2-(a-1)*(c-1))/(a-1)

The inequation to be greater than 0, the discrimant should be negative to have imaginery roots and a-1 > 0

Thus, we get the two conditions:-

a-1 > 0
b^2 < (a-1)*(c-1)

12 Likes

wonderful ! ( Now to complete 20 characters )

https://www.codechef.com/viewsolution/26627878
Can someone pls check my code . Getting TLE in one test case

Wow, i too solved using this same logic :slight_smile:

But i have one doubt.

Wrong Submission - https://www.codechef.com/viewsolution/26602238
In my this submission-> i have used this condition to replace modulo operator,
if(ans>=MOD) ans-=MOD;
Using the same, i got WA on last testcase.

But when i use modulo(%) i get correct answer
Correct Submission - https://www.codechef.com/viewsolution/26602498

Both are the same things, i guess. Any help? :confused:

ans-=MOD will work only if value of ans is between MOD and 2*MOD , lts’s say ans is 10^9+9 then ans-=mod and ans%=mod both will make ans =2, now let ans = 2*10^9 +15
now ans-=MOD will give 10^9+8 and ans%=mod will give 1.
so ans-=mod will work while doing addition but in case of multiplication it will lead to wrong ans.

3 Likes

Refer to first comment @ravi_sumit33 found bug in my code. On replacing unnecessary long long from the code the same code worked and passed in 0.41s https://www.codechef.com/viewsolution/26630486 (Notice typedef int ll )

I have solved it on O(T.B^2). Still TLE.
https://www.codechef.com/viewsolution/26634182
Help?

https://www.codechef.com/viewsolution/26634867 This is your code, after removing count = count%mod by if(count >= mod) count -= mod;

1 Like

I guess i too have same complexity but still three tests gave LTE . Help appreciated :slight_smile:
https://www.codechef.com/viewsolution/26412472

You are getting TLE because of using mod too many times use
if(val > mod) val -= mod;
instead

1 Like

I knew that the % operator is slow but never knew that it could be the difference between a TLE and AC & I have never seen it happen on any other site.

TLE: https://www.codechef.com/viewsolution/26605911
AC: https://www.codechef.com/viewsolution/26639303

why discriminant should be negative and why imaginary roots??

def func2(A, B, C):
s = 0
for b in range(1, B+1):
x = b**2

    if A>b and C>b:
        s+=(A-b)*(C-b)-1
    for a in range(1, min(A, b)):
        s+= max(0, C - (x/a)-1)
    for a in range(1, min(C, b)):
        s+= max(0, A - (x/a)-1)
    #print s,
return s

for _ in range(input()):
A, B, C = map(int, raw_input().split())

#print brute(A, B, C),'\t'
print func2(A, B, C)

how is this code not working???
PLEASE HELP

can you check my approach its bit similar :https://discuss.codechef.com/t/how-codechef-test-the-programme-because-its-tuff-for-me-to-debug-my-code/38270
its giving WA for large cases

Time Complexity can be decreased further : O(B^2 + T*B).
Using DP is the key to decrease the Time Complexity.
Here’s the solution
https://www.codechef.com/viewsolution/26606903

It will work only when ans<2m.
If ans>2m:
ans-m>m
But , ans%m must be less than m.

1 Like

because the value quadratic equation is always positive so It does not cut the x-axis so roots should be imaginary , hence b^2<ac

Why using modulo operator is slower ? It does the same thing.