PROBLEM LINK:
Author: Naman Jain
Tester: Felipe Mota
Editorialist: Rajarshi Basu
DIFFICULTY:
Easy-Medium
PREREQUISITES:
adhoc, implementation, exhaustive search
PROBLEM:
Consider the following operations on a triple of integers. In one operation, you should:
- Choose an integer d and an arithmetic operation ― either addition or multiplication.
- Choose a subset of elements of the triple.
- Apply the arithmetic operation to each of the chosen elements, i.e. either add d to each of them or multiply each of them by d.
You are given an initial triple (p, q, r) and a target triple (a, b, c). Find the minimum number of operations needed to transform (p, q, r) into (a, b, c).
QUICK EXPLANATION:
Read this Quickly!!
- Do an exhaustive brute force search (maybe using recursion, maybe some other pr0 method ?!)
- At every step, we can either add something or multiply something, that will go in the direction of fixing one of the numbers (except in an edge case
) - 0 is a cool number that programmers love. Look out for edge cases related to it.
EXPLANATION:
Notation: I will refer to p,q,r as a_1,a_2,a_3, and a,b,c as b_1,b_2,b_3. Hence, we have to convert a_i to b_i for i \in \{1,2,3\}
Observation 1
First, let us notice that we can always make the initial triplet equal to the final triplet in at most 3 moves, by individually adding the difference between each a_i and b_i.
Observation 2
Next, let us see if we can make the initial triplet equal to the final triplet in just 1 move. This should also be easy to check. (Note that I didn’t handle this explicitly, but it’s an easy case to think about).
Observation 3
There are only a few operations (3 at most) that we need to do in the worst-case, hence exploring all possible operations should be doable with such small constraints since the depth of the recursion will be at most 3. But what all numbers can we add (or multiply?)
Observation 4
Addition
In each operation, we should try to fix at least one of the numbers correct? Hence, the set of all possible numbers we might try to add is restricted to b_i - a_i for i \in \{1,2,3\}. Just 3 numbers, so quite small.
Multiplication
Let’s think about the multiplication case since it’s a bit trickier. Let us say the set mult constains all possible values for multiplication. Then, as in the case of addition, if we are motivated by the fact that atleast one of the numbers must be fixed in a multiplication, then m should be in mult is a_i*m = b_i for some i. (Remember, both a_i and b_i can be 0, so take care).
A Slightly Harder-to-Detect Case
Till now, all our operations had the underlying assumption that after the operation, at least one of the a_i should become equal to b_i. Consider the following case:
a = [2,3,4]
b = [-20,-1,18]
Using just the operations in Observation 4, the best we can do is 3 operations.
However, try this:
- Multiply all the numbers with 19
- Add -58 to all the numbers.
There, we only took 2 operations! But how do we get this magic number of 19?
The Details
Here, we what we are really doing is multiplying by a certain x and then adding a certain y such that a_i*x + y = b_i , \forall i \in \{1,2,3\}. In particular, this means that:
- a_1*x + y = b_1 ---------- (1)
- a_2*x+y = b_2 ---------- (2)
- (a_1-a_2)*x = b_1-b_2 -------- Subtracting (2) from (1)
Hence, we get some more candidate values x which we should include in our set mult. In particular, we should compute this X for all possible such combinations, ie, getX(a_1,a_2,b_1,b_2),getX(a_2,a_3,b_2,b_3),getX(a_1,a_3,b_1,b_3) .
Implementation
We use recursion to search exhaustively. Key points:
- Make a list of all possible additions and multiplications and iterate over them
- Choose a subset on which to perform that operation.
- Perform that operation, and call the function itself with the new parameters.
- To prune, if you see that you have already done 2 operations and still not reached equality condition, just break, since 3 operations will, in any case, be possible.
- For more clarity, see Editorialist’s code.
But But But .... Time Complexity?
Its exponential. The number of possible operations is B = 3+3+3=9, and the number of subsets possible is M=2^3-1. Hence, the branching factor is at most D = B*M. Since the depth of the recursion tree is at most 2, hence the time complexity is upper-bounded by D^2, which is quite less.
QUICK REMINDERS:
long long int is good for your health.
SOLUTIONS:
Tester's Code
# v1 - v0 * x = u1 - u0 * x
# (u0 - v0) * x = u1 - v1
def eq_solve(v0, v1, u0, u1):
den = u0 - v0
num = u1 - v1
if den != 0:
return num / den
return 1
def solve(p, q, r, a, b, c, rs):
if p == a and q == b and r == c:
return rs
if rs >= 2:
return 3
res = 3
adds = [a - p, b - q, c - r]
muls = []
if p != 0:
muls.append(a / p)
if q != 0:
muls.append(b / q)
if r != 0:
muls.append(c / r)
muls.append(eq_solve(p, a, q, b))
muls.append(eq_solve(p, a, r, c))
muls.append(eq_solve(q, b, r, c))
msks = 2 ** 3
for msk in xrange(msks):
for add in adds:
np = p
nq = q
nr = r
if (msk & 1) > 0:
np += add
if (msk & 2) > 0:
nq += add
if (msk & 4) > 0:
nr += add
res = min(res, solve(np, nq, nr, a, b, c, rs + 1))
for mul in muls:
np = p
nq = q
nr = r
if (msk & 1) > 0:
np *= mul
if (msk & 2) > 0:
nq *= mul
if (msk & 4) > 0:
nr *= mul
res = min(res, solve(np, nq, nr, a, b, c, rs + 1))
return res
t = int(raw_input())
while t > 0:
p, q, r = map(int, raw_input().split())
a, b, c = map(int, raw_input().split())
print solve(p, q, r, a, b, c, 0)
t -= 1
Editorialist's Code
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ld long double
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define vv vector
#define endl '\n'
using namespace std;
const int MAXN = 100*1000 + 5;
inline ll mulFac(ll a,ll b,ll c,ll d){
if(b != a and (d-c)%(b-a) == 0){
return (d-c)/(b-a);
}else{
return 1;
}
}
inline bool equal(ll* a, ll* b){
FOR(i,3)if(a[i] != b[i])return false;
return true;
}
int best;
void solve(ll* a,ll* b,int num = 0){
if(num >= best)return;
if(equal(a,b)){
best = min(best,num);
return;
}
if(num >= 2)return;
set<ll> add;
add.insert(b[0]-a[0]);
add.insert(b[1]-a[1]);
add.insert(b[2]-a[2]);
set<ll> mult;
FOR(i,3)if(a[i] != 0 and b[i]%a[i] == 0)mult.insert(b[i]/a[i]);
mult.insert(mulFac(a[0],a[1],b[0],b[1]));
mult.insert(mulFac(a[2],a[1],b[2],b[1]));
mult.insert(mulFac(a[0],a[2],b[0],b[2]));
mult.insert(0);
FORE(mask,1,7){
vi all;
FOR(j,3)if(mask&(1<<j))all.pb(j);
for(auto x: add){
ll aa[3];
FOR(j,3)aa[j] = a[j];
for(auto e: all)aa[e]+=x;
solve(aa,b,num+1);
}
for(auto x:mult){
ll aa[3];
FOR(j,3)aa[j] = a[j];
for(auto e: all)aa[e]*=x;
solve(aa,b,num+1);
}
}
}
void solve(){
best = 3;
ll a[3];
ll b[3];
cin >> a[0] >> a[1] >> a[2];
cin >> b[0] >> b[1] >> b[2];
solve(a,b);
cout << best << endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)solve();
return 0;
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 
