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;
}