MISS_NUM - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Kuriseti Ravi Sri Teja
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Alice (uniformly and independently) randomly picks two integers a, b from the range [1,10^4], and writes down the values of a + b, a - b, a \cdot b and \lfloor \frac{a}{b} \rfloor (integer division) in some random order. Unfortunately, she forgot the values of a and b. You need to help her to find out if there exists two integers a, b such that 1 \leq a, b \leq 10^4 and a + b, a - b, a \cdot b, \lfloor \frac{a}{b} \rfloor are the numbers she has written down.

If a solution exists, it is guaranteed to be unique.

EXPLANATION:

Number of variables in the problem that are unknown.

We have two variables a and b in our problem that our unknown. We want to find out the values of these variables, given the constraint that both of these variables are integers, and some set of equations involving these variables. Also note that these variables lies in the range [1, 10^4].

Number of equations given in the problem.

Along with the constraint that a and b are integers, we are given the values of 4 expressions: a+b, a-b, a \cdot b, \lfloor \frac{a}{b} \rfloor. The twist is, we are not given the corresponding values of these expressions, rather the values are given in some random order.

What if the values were given in the correct order?

If the values of the expressions were given in the correct order, then we would be having 2 variables and 4 equations. We could have used any 2 equations to get the values of a and b, and then we could have checked if the values that we have got are satisfying the other 2 equations or not.

There are several combinations of the initial 2 equations that we could have chosen. Which one should we choose to make our problem easy?

Choosing the initial 2 equations!

We can choose several combinations of the initial 2 equations to get the probable values of a and b. One of the simplest way is to choose the equations a+b and a-b. We can add these two equations to get the value of a, and subtract these equations to get the value of b. Now we can check whether the values of a and b that we have got satisfies the other two equations or not!

How to solve when the values are given in random order?

So we have seen that if the values were given in correct order, we could have solved the problem. The problem is, they are not given in the correct order.

Can we fix the values of the equations somehow?
There are 4! ways in which we can fix the values of the equations. We can try out all these 4! ways to check if we get a valid answer in one of the ways or not. If yes, then we have got our a and b, otherwise there does not exist a valid solution.

The final part - Implementation

In the problems that involves iterating over all the permutations, some inbuilt functions, like next_permutation in C++, or similar functions in other languages are very handy.

You might be getting wrong answer due to one of the following reasons!
  • While dividing, always make sure that your denominator is non-zero.
  • Note that a and b lies in the range [1,10^4]. Make sure you are not printing answers outside this range.
  • Before printing the answers, make sure that all the 4 conditions are satisfied.

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Editorialist's Solution 
#include<bits/stdc++.h>
#define ll long long
using namespace std ;

bool is_valid(ll add, ll sub, ll mul, ll div)
{
    ll a = (add + sub)/2 ;
    ll b = (add - sub)/2 ;

    if(a < 1 || a > 10000)
        return false ;
    if(b < 1 || b > 10000)
        return false ;


    ll flag = 0 ;
    if(a+b == add) flag++ ;
    if(a-b == sub) flag++ ;
    if(a*b == mul) flag++ ;
    if(b != 0 && a/b == div) flag++ ;

    if(flag == 4) // if all 4 equations are satisfied, we have got a valid answer
    {
        return true ;
    }
    return false ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    int t ;
    cin >> t ;

    while(t--)
    {
        ll val[4] ;
        for(int i = 0 ; i < 4 ; i++)
            cin >> val[i] ;

        // val[arr[i]] will denote the value of the i^th equation. The equations are numbered as:
        // 0: a + b     1: a - b    2: a*b  3: a/b
        ll arr[4] = {0 , 1 , 2 , 3} ;

        pair<ll ,ll> ans = {-1 , -1} ;
        do
        {
            // check if we can get a valid answer. If yes, extract the values and break.
            if(is_valid(val[arr[0]], val[arr[1]], val[arr[2]], val[arr[3]]))
            {
                ans.first = (val[arr[0]] + val[arr[1]])/2 ; // value of a
                ans.second = (val[arr[0]] - val[arr[1]])/2 ;// value of b
                break ;
            }
        }
        while(next_permutation(arr , arr+4)) ;

        cout << ans.first << ' ' << ans.second << endl ;
    }

    return 0;
}
5 Likes
2

#include <bits/stdc++.h>
using namespace std;
int const N = 1e4;
int main()
{
int t;
cin >> t;
while (t–)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
array<int, 4> arr = {a, b, c, d};
int ct = 0;
for (int i = 0; i < 4; i++)
{
if (arr[i] < 0)
ct++;
}

    if (ct == 0)
        cout <<"-1"<<" "<<"-1"<<endl;
    else
    {

        sort(arr.begin(), arr.end());
        // for (auto it : arr)
        //     cout << it << " ";
        // cout << endl;
        int m1, s;
        if (arr[2] + 1 == arr[3])
        {
            m1 = arr[2];
            s = arr[3];
        }
        else
        {
            m1 = arr[3];
            s = arr[2];
        }

        map< int,  int> m;

        for (int i = 1; i <= sqrt(m1); i++)
        {
            if (m1 % i == 0)
            {
                pair<int, int> p;
                p = {i, m1 / i};
                m.insert(p);
            }
        }
        int check = 0;
        for (auto &mp : m)
        {
            int sum = (mp.first + mp.second);
            int diff = (mp.first - mp.second);
            int d = mp.first / mp.second;
            int mul = (mp.first * mp.second);
            if (sum == s && diff == arr[0] && mul == m1 && d == arr[1])
            {
                array<int,2>arr1={mp.first , mp.second};
                check = 1;
                if(arr1[0]<0||arr1[1]<0||arr1[0]>N||arr1[1]>N)
                cout <<"-1"<<" "<<"-1"<<endl;
                else
                cout << arr1[0] << " " << arr1[1] << endl;
            }
        }
        if (check == 0)
            cout <<"-1"<<" "<<"-1"<<endl;
    }
}

}

3

@lavish315 can you please tell me what was the 1st test case

4

I believe it had a set of A, B, C, D which produced a solution for a and/or b which were outside the scope of the problem (in the intro it said a and b are between 1 and 10^4). Your code probably (and mine definitely!) reported these as a solution instead of correctly reporting them as -1 -1.

5

Can someone help me why this code is wrong for 1 test case ?
Solution

6

My code is giving the right output for each input, but it didn’t pass one test case, please tell, me where i am going wrong

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

int check1(long long int i,long long int j,long long int arr[])
{
if((i*j)==arr[3])
{
if(((i-j)==arr[0]) &&(floor(i/j)==arr[1])){
cout<<i<<" "<<j<<endl;
return 1;
}

     else if((((j-i)==arr[1]) && (floor(j/i)==arr[0]))){
     cout<<j<<" "<<i<<endl;
     return 1;
     }
}
return 0;

}

int check2(long long int i,long long int j,long long int arr[])
{
if((i*j)==arr[2])
{
if(((i-j)==arr[0]) &&(floor(i/j)==arr[1])){

     cout<<i<<" "<<j<<endl;
     return 1;
   }
     
     else if((((j-i)==arr[0]) && (floor(j/i)==arr[1]))){
         
     cout<<j<<" "<<i<<endl;
     return 1;
     }
}
return 0;

}

int main() {

int t;
cin>>t;

while(t--)
{
   long long int A,B,C,D;
    cin>>A>>B>>C>>D;
    
    long long int arr[4];
    arr[0]=A,arr[1]=B,arr[2]=C,arr[3]=D;
    
    sort(arr,arr+4);
    
    if(abs(arr[0])>10e8 || abs(arr[1])>10e8 || abs(arr[2])>10e8 ||abs(arr[3])>10e8)
    {
        cout<<-1<<" "<<-1<<endl;
        continue;
    }

if(arr[0]==0 && arr[1]==1 && arr[2]==1 && arr[3]==2)
{
cout<<1<<" "<<1<<endl;
continue;

}
int flag=0;
long long int maxi=arr[2];

   long long int i=1,j=maxi-1;
   while(i<=j)
   {
       if(check1(i,j,arr)==1){
           
            
               flag=1;
               break;
               }
               i++;
               j--;
   }
   
   if(flag==0)
    {
         long long int maxi2=arr[3];
   
  long long int m=1,n=maxi2-1;
    while(m<=n)
   {
       if(check2(m,n,arr)==1){
           
            
               flag=1;
               break;
               }
               m++;
               n--;
   }
    
    }
   
    if(flag==0)
   cout<<-1<<" "<<-1<<endl;
   
}
return 0;

}

7

@nairobiny i don’t think so because i have a special check if the values are in range or not.

9

Hello everyone.The first testcase had some test-cases where a,b could be greater than 10^4.This is where most of you had gone wrong

10

If a=1 and b=10^5,your code goes wrong.

11

Can someone pls explain why did he (video solution) leave out the other the combinations. also how did choose to combine multiplication and division together and nothing other than that in this code :

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

void solve(long long int x, long long int y, long long int z, long long int d, int& a, int&b)
{
if((x+y)%2==0){
long long int t1= (x+y)/2;
long long int t2= abs(x-y)/2;

    if((t1<=0 || t1> 1e4) || (t2<=0 || t2>1e4)){
        a=-1;
        b=-1;
        return;
    }
    
    if(((z==t1*t2) && (d==t1/t2)) || ((d==t1*t2) && (z==t1/t2))){
    a=t1;
    b=t2;
    }
    else{
        a=-1;
        b=-1;
    }
}
else{
    a=-1;
    b=-1;
}

}

int main() {
static int t;
cin>>t;
while(t–){
long long int x,y,z,d;
cin>>x>>y>>z>>d;
int a=0,b=0;
solve(x,y,z,d,a,b);

      if(a==-1 && b==-1)
      solve(x,z,y,d,a,b);
      
      if(a==-1 && b==-1)
      solve(x,d,y,z,a,b);
      
      if(a==-1 && b==-1)
      solve(y,z,x,d,a,b);
      
      if(a==-1 && b==-1)
      solve(y,d,x,z,a,b);
      
      if(a==-1 && b==-1)
      solve(z,d,x,y,a,b);
      
      cout<<a<<" "<<b<<endl;
  }
return 0;

}

Here combinations used are:
x,y,z,d
x,z,y,d
x,d,y,z
y,z,x,d
y,d,x,z
z,d,x,y

12

Update the code worked test case failed for output -1, -1
here is the solution if anyone needs for python - Solution

13

What does your code return for A, B, C, D = -1, 0, 5, 6?
What do you think it should return?

14

@nairobiny my code is returning -1 -1 and i think it should return the same

15

this is my code.
I will explain what i am trying to do.
There are only 3 possible ways A,B,C,D can be layed out.

  1. (a-b, a/b, a+b, a*b) : when a < b and a,b > 1
  2. (a-b, a/b, a*b, a+b) : when a == 1 || b ==1, here array[3] == array[2]+1 always.
  3. (a/b, a-b, a+b, a*b) : when a > b and b > 1.
    After solving it i thought why calculate for all the possibilities which i have done here, So what i did was to try and rearrange all values in (a-b, a/b, a+b , a*b), So that i can simply calculate a = (array[0] + array[2])/2
    I don’t need to change 1st case as it is already in order
    For 2nd case (a-b, a/b, a*b, a+b) we need to swap a*b and a+b. One can put a = 1 or b = 1 or both 1 and will observe that array[2] == array[3] - 1 always, So when that is true we can swap.
    For 3rd case (a/b, a-b, a+b, a*b). This will be true always when a > b and both a,b > 1. So here a / b (or array[0]) will always be greater than 0. but it will also be true for a > b and b == 1, So we have to ignore that value, So for a > b and b == 1, array[2] == array[1]. So if we encounter a value where array[0] > 0 && array[2] != array[1]. We know we are talking about specifically about (a/b, a-b, a+b, a/*b) and here we will swap array[0] and array[1]. In the end i am calculating a and b. But i am getting wrong answer for 1st test case. I don’t know what i am doing wrong in this solution
16

This is a necessary condition when a == 1 but it is not a sufficient one. You should generate A, B, C, D for values of a, b and check that your code is producing what you feed in.

17

@nairobiny So you mean this can hold true for some other value where a or b is not 1? If so can please share that pattern. :slightly_smiling_face:

18

here i am checking all possible values of a and b with all the mentioned conditions but it is still giving wrong answer for first test case…can someone find the error

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

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
		long long A, B, C, D;
		cin>>A>>B>>C>>D;
		if((A<0 && (B<0||C<0||D<0)) || (B<0 && (A<0||C<0||D<0)) || (C<0 && (A<0||B<0||D<0)) || (D<0 && (A<0||B<0||C<0)))
		{
			cout<<"-1 -1\n";
			return 0;
		}
		long long a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12;
		a1=(A+B)/2;b1=(A-B)/2;
		a2=(A+C)/2;b2=(A-C)/2;
		a3=(A+D)/2;b3=(A-D)/2;
		a4=(B+A)/2;b4=(B-A)/2;
		a5=(B+C)/2;b5=(B-C)/2;
		a6=(B+D)/2;b6=(B-D)/2;
		a7=(C+A)/2;b7=(C-A)/2;
		a8=(C+B)/2;b8=(C-B)/2;
		a9=(C+D)/2;b9=(C-D)/2;
		a10=(D+A)/2;b10=(D-A)/2;
		a11=(D+B)/2;b11=(D-B)/2;
		a12=(D+C)/2;b12=(D-C)/2;
		if(a1*b1==C  && b1!=0&& a1/b1==D &&a1<=10000&&b1<=10000&&a1>0&&b1>0)
		cout<<a1<<" "<<b1<<"\n";
		else if(a1*b1==D  && b1!=0&& a1/b1==C &&a1<=10000&&b1<=10000&&a1>0&&b1>0)
		cout<<a1<<" "<<b1<<"\n";
		else if(a2*b2==B  && b2!=0&& a2/b2==D &&a2<=10000&&b2<=10000&&a2>0&&b2>0)
		cout<<a2<<" "<<b2<<"\n";
		else if(a2*b2==D  && b2!=0&& a2/b2==B &&a2<=10000&&b2<=10000&&a2>0&&b2>0)
		cout<<a2<<" "<<b2<<"\n";
		else if(a3*b3==B && b3!=0&&a3/b3==C &&a3<=10000&&b3<=10000&&a3>0&&b3>0)
		cout<<a3<<" "<<b3<<"\n";
		else if(a3*b3==C && b3!=0&&a3/b3==B &&a3<=10000&&b3<=10000&&a3>0&&b3>0)
		cout<<a3<<" "<<b3<<"\n";
		else if(a4*b4==C && b4!=0&&a4/b4==D &&a4<=10000&&b4<=10000&&a4>0&&b4>0)
		cout<<a4<<" "<<b4<<"\n";
		else if(a4*b4==D && b4!=0&&a4/b4==C &&a4<=10000&&b4<=10000&&a4>0&&b4>0)
		cout<<a4<<" "<<b4<<"\n";
		else if(a5*b5==A && b5!=0&&a5/b5==D &&a5<=10000&&b5<=10000&&a5>0&&b5>0)
		cout<<a5<<" "<<b5<<"\n";
		else if(a5*b5==D && b5!=0&&a5/b5==A &&a5<=10000&&b5<=10000&&a5>0&&b5>0)
		cout<<a5<<" "<<b5<<"\n";
		else if(a6*b6==A && b6!=0&&a6/b6==C &&a6<=10000&&b6<=10000&&a6>0&&b6>0)
		cout<<a6<<" "<<b6<<"\n";
		else if(a6*b6==C && b6!=0&&a6/b6==A &&a6<=10000&&b6<=10000&&a6>0&&b6>0)
		cout<<a6<<" "<<b6<<"\n";
		else if(a7*b7==B && b7!=0&&a7/b7==D &&a7<=10000&&b7<=10000&&a7>0&&b7>0)
		cout<<a7<<" "<<b7<<"\n";
		else if(a7*b7==D && b7!=0&&a7/b7==B &&a7<=10000&&b7<=10000&&a7>0&&b7>0)
		cout<<a7<<" "<<b7<<"\n";
		else if(a8*b8==A && b8!=0&&a8/b8==D &&a9<=10000&&b9<=10000&&a9>0&&b9>0)
		cout<<a8<<" "<<b8<<"\n";
		else if(a8*b8==D && b8!=0&&a8/b8==A &&a9<=10000&&b9<=10000&&a9>0&&b9>0)
		cout<<a8<<" "<<b8<<"\n";
		else if(a9*b9==A && b9!=0&&a9/b9==B &&a9<=10000&&b9<=10000&&a9>0&&b9>0)
		cout<<a9<<" "<<b9<<"\n";
		else if(a9*b9==B && b9!=0&&a9/b9==A &&a9<=10000&&b9<=10000&&a9>0&&b9>0)
		cout<<a9<<" "<<b9<<"\n";
		else if(a10*b10==B && b10!=0&&a10/b10==C &&a10<=10000&&b10<=10000&&a10>0&&b10>0)
		cout<<a10<<" "<<b10<<"\n";
		else if(a10*b10==C && b10!=0&&a10/b10==B &&a10<=10000&&b10<=10000&&a10>0&&b10>0)
		cout<<a10<<" "<<b10<<"\n";
		else if(a11*b11==A && b11!=0&&a11/b11==C &&a11<=10000&&b11<=10000&&a11>0&&b11>0)
		cout<<a11<<" "<<b11<<"\n";
		else if(a11*b11==C && b11!=0&&a11/b11==A &&a11<=10000&&b11<=10000&&a11>0&&b11>0)
		cout<<a11<<" "<<b11<<"\n";
		else if(a12*b12==A && b12!=0&&a12/b12==B &&a12<=10000&&b12<=10000&&a12>0&&b12>0)
		cout<<a12<<" "<<b12<<"\n";
		else if(a12*b12==B && b12!=0&&a12/b12==A &&a12<=10000&&b12<=10000&&a12>0&&b12>0)
		cout<<a12<<" "<<b12<<"\n";
		else
		cout<<"-1 -1\n";
	}
		return 0;
}
19

Hey, the problem in your code is that you are trying to hardcode every possible solution. Hardcoding every case is not the right way to solve a problem especially in CP and now even a simple typo which may have caused the error is too hard to find. Better try to understand the logic and put the logic in the code, this will help you in ling term.

20

2 + 3 = 5, 2 * 3 = 6

21

@nairobiny thanks for the pattern that was very useful <3