HLEQN - Editorial

iceknight1093 · August 15, 2022, 4:35am

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Abhinav Sharma
Testers: Nishank Suresh, Nishant Shah
Editorialist: Nishank Suresh

DIFFICULTY:

1315

PREREQUISITES:

Basic math

PROBLEM:

Given X, find if there exist any positive integer solutions to 2\cdot a + 2\cdot b + a\cdot b = X.

EXPLANATION:

Suppose we fix the value of a. Can we find out whether a valid b exists?

Yes we can

Rearrange the equation to bring b to one side, and we obtain

b = \frac{X - 2\cdot a}{a + 2}

We want b to be a positive integer, and so all that needs to be done is to check two conditions:

X - 2\cdot a \gt 0
a + 2 divides X - 2\cdot a

both of which are easy to check.

With this in mind, we can iterate over all possible values of a, and check if a valid value of b exists or not.

However, there can be upto 10^9 possible values for a, and iterating over them all is too slow so we need to speed up a little.

Note that, since a\gt 0 and b\gt 0, we must have a\cdot b \leq X. In particular, this means that at least one of a and b must be no larger than \sqrt X. In particular, \min(a, b) \leq \sqrt X.

Also note that the equation is symmetric in a and b, i.e, if we swap a and b, the value of 2\cdot a + 2\cdot b + a\cdot b doesn’t change.

So, without loss of generality, we can always say that a \leq b. This, combined with our earlier observation that \min(a, b) \leq \sqrt X now gives us only \mathcal{O}(\sqrt X) different values of a that need to be checked, which is fast enough to solve the problem.

TIME COMPLEXITY

\mathcal{O}(\sqrt X) per test case.

CODE:

Editorialist's Code (Python)

for _ in range(int(input())):
    x = int(input())
    ans = 'no'
    # b = (x - 2*a)/(a+2)
    for a in range(1, x+10):
        if a*a > x:
            break
        if 2*a >= x:
            break
        if (x - 2*a)%(a + 2) != 0:
            continue
        ans = 'yes'
        break
    print(ans)

termii · August 15, 2022, 9:49am

I admit that I could not solve this within 1 hour, and even dropped it after feeling stuck for that long. Maybe I should do more math problems.

vesko · August 15, 2022, 10:04am

I think mine is simpler

int ec(int a,int b)
{
    return a*b+2*a+2*b;
}

string f(int x)
{
    if(x<5) return "NO";
    for (int i = 1; 1; i++)
    {
        int vl = ec(i,i);
        if(vl>x||vl>1e9) break;
        if(vl==x||(x-vl)%(2+i)==0) return "YES";
    }
    return "NO";
}

vgnshiyer · August 15, 2022, 11:57am

I used Binary Search to find out the value of b.
Glad to know there was a simpler solution out there.

silenttkillerr · August 15, 2022, 1:03pm

Explain your logic pleases

vesko · August 15, 2022, 3:47pm

Lets define a function f(a,b) = 2*(a+b)+a*b (for simplicity)
we want to know whats the difference between the number f(a,b) and f(a,b+1)

Lets have a look:
f(1,1) = 5, f(1,2) = 8, f(1,3) = 11
it looks like it increases by 3
why? lets see:
when we increase b by 1 the 2(a+b) part of the expression always increases by 2
and the a*b part increases by a, that means the number will increase by 2+a

That means that we can represent every valid X(by valid I mean a and b exist for X)
by f(a,1) + (2+a)*(some integer), eg. 5+3=8, 5+3+3=11 …

The final step is to check if the difference between f(a,a) and X is divisible by (2+x)
(we used f(a,a) instead of f(a,1) because with f(a,1) we get TLE
and there may be some duplicate pairs for example when a is 3: (3,1),(3,2),(3,3) but (3,1) and (3,2) can be represented as when a is 1 or a is 2 eg. (1,3),(2,3))
the only thing to do is to find the a that this works for if we can’t, then we say “no”,
we can check if X<f(a,a), then we stop (because the f(a+1,a)+n will always be bigger than f(a,a)+n where n is some number)

my submission:

#include<bits/stdc++.h>
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

#define int ll
#define endl '\n'
#define pb(e) push_back(e)
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(), a.end()

#define x first
#define y second

// #pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")

typedef long long   ll;
typedef long double ld;

const ll inf = LLONG_MAX;
const ld π = 3.1415926535897932384626;
const ld ε = 0.00001;

int ec(int a,int b)
{
    return a*b+2*a+2*b;
}

string f(int x)
{
    if(x<5) return "NO";
    int i;
    for (i = 1; 1; i++)
    {
        int vl = ec(i,i);
        if(vl>x||vl>1e9) break;
        if(vl==x||(x-vl)%(2+i)==0) return "YES";
    }
    return "NO";
}

int32_t main()
{   
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    srand(time(0));

    //#ifdef ONLINE_JUDGE
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    //#endif
    
    int ____; cin >> ____; while (____--)
    {
        int x; cin >> x;
        cout << f(x) << endl;
    }    
}

stark16 · August 16, 2022, 11:53am

The problem can be reduced to show that (X+4) and (X+4)/2 should not be prime numbers.

Here’s how:

X = 2a + 2b + ab
X + 4 = 2a + 2b + ab + 4
X + 4 = (a+2)(b+2)
X + 4 = pq (where p = a+2, q=b+2)

This basically means that X+4 can be written as a product of 2 positive integers p and q, where p>2 and q>2, which essentially means that X+4 should not be a prime number.

And to satify the condition that both p and q > 2, (X+4)/2 should also not be prime.

Here’s the code:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int isPrime(long long int x) {
    double rt = sqrt(x);
    long long int rt_int = (long long int) rt;
    for (long long int i = 2; i<=rt_int+1; i++) {
        if (x%i == 0)
            return 0;
    }
    return 1;
}

int main() {
	int t;
	cin>>t;
	while(t--) {
	   long long int x;
	   cin>>x;
	   if ((x==4) || isPrime(x+4) || ((x+4)%2==0) && isPrime((x+4)/2))
	        cout<<"NO"<<endl;
	   else
	        cout<<"YES"<<endl;
	}
	return 0;
}

silenttkillerr · August 16, 2022, 2:49pm

Nice explanation.
Thank you very muh

vesko · August 16, 2022, 3:30pm

Pretty clever solution.
By the way, in your code you can use typedef to define a type, for example:
typedef long long ll;
When you use ll in your code is the same as long long, but its shorter.
I see that you used endl, that means every line you flush the output, note that flushing is slower than just writing '\n', in some problems it might give TLE.
Also on the first line you include io stream, but that isn’t necessary because you include the stdc++ header.
This is just a tip btw.

stark16 · August 16, 2022, 5:33pm

Agreed, typedef would be quicker. Also, thanks for the info on endl, didn’t know that it flushes the output every time.

rajkamal10 · August 17, 2022, 6:19am

My approach :
a =1 : b = 1 => X = 5
b = 2 => X = 8
b = 3 => X = 11
…
So, a= 1 : X = 5,8,11, 14, … If X >= 5 and X%3 == 2 : then YES

Similarly for,
a = 2 : X = 8, 12, 16, 20, 24, … If X >= 8 and X%4 == 0 : then YES
a = 3 : X = 11, 16, 21, 26, … If X >= 11 and X%5 == 1 : then YES
Now, for further values of a, it can be observed, all X’s produced by them are already generated by either a = 1, or a =2 or a= 3

a = 4 : 14 , 20, 26, 32, …
a = 5 : 17, 24, 31, 38, …
a = 6 : 20, 28, 36, 44, …
all these values are already generated by either a= 1, or a= 2, or a= 3

I coded above logic but getting WA, please tell what testcase I am missing.
Code :

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
	    long long int x;
	    cin>>x;
	    
	    if((x>=5 && x%3 == 2) || (x>=8 && x%4 == 0) || (x>=11 && x%5 == 1)){
	        cout<<"YES\n";
	    }
	    else{
	        cout<<"NO\n";
	    }
	}
	return 0;
}

vesko · August 17, 2022, 8:45am

Try this number 986982.
You can get it when a is 999 and b is 984.

rajkamal10 · August 17, 2022, 10:35am

Thanks

hello_rb_96 · August 18, 2022, 5:11am

Did you get TLE While using Binary search? (Assuming that you iterated linearly for a and did a binary search inside the loop for finding b) If not, then would appreciate if you could tell me your approach

sunoj_23 · August 18, 2022, 5:41am

man that was clever and well done on this , thanks it helped a lot