ABPLUSC - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: utkarsh_25dec
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

1569

PREREQUISITES:

None

PROBLEM:

Given 1 \leq X\leq 10^{12}, find whether there exist integers 1 \leq A, B, C \leq 10^6 such that AB + C = X.

EXPLANATION:

If X = 1, no solution exists because AB+C \geq 2 for any choice of A, B, C.
Otherwise, a solution always exists!
There are many different approaches, I’ll elaborate on one of them.

Notice that X = AB+C is vaguely reminiscent of division.
In particular, if we fix the value of B, Euclid’s division lemma tells us that there exist unique integers q (the quotient) and r (the remainder) such that:

  • X = qB + r
  • 0 \leq r \lt B

If we’re able to choose B appropriately such that 1 \leq q, r \leq 10^6, we’ll be done, since we can directly take A = q and C = r.
In fact, we don’t really need to worry much about r. Since r \lt B, it’ll never exceed 10^6 anyway, as long as we choose B \leq 10^6.
So, our aim is to keep q small enough.

This can be achieved by picking a large enough B.
For example, suppose we pick B = 10^6 and then find q and r.
Then, since X \leq 10^{12}, we’ll surely have q \leq 10^6, which takes care of all the upper bounds.

This solves the problem for almost all cases — the only ones it doesn’t solve are the ones for which q = 0 or r = 0.
Let’s see how we can fix those.

  • If q = 0, that would mean X \lt 10^6.
    Solving such a case is quite easy though, since we have several options.
    For example, you can choose A = B = 1 and C = X-1, or A = C = 1, B = X-1.
  • If r = 0, that would mean X is a multiple of 10^6.
    In such a case, we can decrease q by 1 and set r = 10^6.
    This will fail only for X = 10^6, since decreasing q by 1 will make it 0.
    However, X = 10^6 can be solved using the previous case anyway, so there’s no issue.

Putting it all together,

  • If X = 1, no solution exists.
  • If X \leq 10^6, choose A = B = 1, C = X-1 (or similar).
  • If X \gt 10^6, find q and r, the quotient and remainder when X is divided by 10^6. Then,
    • If r \gt 0, choose A = q, B = 10^6, C = r
    • If r = 0, choose A = q-1, B = 10^6, C = 10^6

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    x = int(input())
    if x == 1: print(-1)
    elif x <= 1000001: print(1, 1, x-1)
    else:
        m = 10**6 
        if x%m == 0: print(m, x//m - 1, m)
        else: print(m, x//m, x % m)```
1 Like
2

Question: Why is this code not working?
Logic:- For r = 0; I took two prime numbers which are just below 10^6. If in case the number is a multiple of 10^6 and prime number a, I change the value to the second prime number since x being a multiple of 10^6,a and b simultaneously is not possible.
Is there any fault in my logic then? Or, something else??

#include <bits/stdc++.h>
#define int long long int
#define LOOP for(int i = 0; i < n; i++)
#define LOOP1 for(int i = 1; i <= n; i++)
using namespace std;

int i, j;

void sol()
{
int x;
cin>>x;

if(x <= 1)
    cout<<-1<<endl;
else if(x <= pow(10, 6)){
    cout<<1<<" "<<1<<" "<<x - 1<<endl;
}
else if((x%1000000) == 0){
    int a = 0, b = 0, c = 0;
     a = 99991;
     if(x % a == 0)
        a = 99989;
     b = x/a;
     c = x % a;
    cout<<a<<" "<<b<<" "<<c<<endl;
}
else{
    int a = 0, b = 0, c = 0;
    a = 1000000;
    b = x/a;
    c = x % a;
    cout<<a<<" "<<b<<" "<<c<<endl;
}

}

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;

while(t--)
    sol();
return 0;

}

3

else if((x%1000000) == 0){
int a = 0, b = 0, c = 0;
a = 99991;
if(x % a == 0)
a = 99989;
b = x/a;
c = x % a;
cout<<a<<" “<<b<<” "<<c<<endl;
}

> Blockquote

You can simply take a=1000000 , b=x/a-1, c=1000000

4 
import math
# cook your dish here
t=int(input())
for i in range(t):
    x=int(input())
    if(x==1):
        print(-1)
        continue
    elif(x==2):
        print('1 1 1')
        continue
    elif(x==3):
        print('2 1 1')
        continue
    s1=int(x**(1/2))
    if(s1*s1==x):
        print(s1,s1-1,x-(s1*(s1-1)))
    else:
        print(s1,s1,x-(s1*s1))

WHY IS THIS NOT WORKING ON A 1 OF THE TEST CASES BUT GIVES WRITE ON ALL OTHER CASES?

3 Likes
5

Know that but wanted to know what’s the fault in this code since I am unable to detect it.
(And it did display WA)

6

Using the square root approach mentioned in the hint section it is told that in come cases it is possible that C = X - Y^2 can be > 10^6.
I couldn’t find an example where this is possible, can anyone help.

7

I have done exactly the same approach, where is the fault ? @iceknight1093 please tell us the test case where it fails .

1 Like
8

Hi there,
I am not as experienced as @ iceknight1093, but for your submission CodeChef: Practical coding for everyone (latest at this time) , here is the failing testcase

1
999999696969

This is because the square root function you use will always give float of actual square root.
I hope you understand.

Also, on the side note, your program is using logarithmic time complexity

You can solve it in constant time complexity. See my solution and explanation (it is in Rust though, but you can still see the approach )

https://www.codechef.com/viewsolution/95152265

2 Likes
9

why is my solution wrong ?
Solution

10

Take x = 999999999998
for this c would be > 10^6

11

Thank you so much , I got it now and got a relief too , Thank you :relaxed:

1 Like
12

1
1000000000000

In this test case your code gives -1 , but valid answer exists.

999999 1000000 1000000

13

You are always welcome

14

why is this code not working?
import math
t = int(input())
for i in range(t):
x = int(input())

if x==1:
    print(-1)
elif x==2:
    print(1,1,1)
else:
    s=int(math.sqrt(x))
    r=x-(s*(s-1))
    print(s,s-1,r)
15

Again, see testcase

And my approach

16

This submission was accepted but it is wrong. It is not enough (as I saw in some comment above) to consider products of the form A \cdot B = i \cdot (i+1), since then C could be up to 2 \cdot 10^6 - 2 (the difference between two consecutive products may be up to (i+1)\cdot i - i \cdot (i-1) = 2i). For example, for the number (10^6 - 1)^2 + 2 = 999998000003, my code gives (A, B, C) = (999999, 999998, 1000001).

It should be enough if you also consider squares, i.e. both products of the form A \cdot B = i \cdot (i+1) and A \cdot B = i \cdot i, since then the difference between two consecutive products is at most i, and this is what I did in my previous submission (for the previous example this one uses a perfect square as product, i.e. (A, B, C) = (999999, 999999, 2),

1 Like