TTUPLE - Editorial

PROBLEM LINK:

Contest 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 :wink:)
  • 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 :slight_smile:

49 Likes

I got 90 points but unable to know where I am wrong for 10 points

2 Likes

If any one wants to see the donkey-work I did: https://www.codechef.com/viewsolution/33912122

31 Likes

My 350 lines AC code,brute force,took 5-6 days,adding conditions one-by-one :slightly_smiling_face:
https://www.codechef.com/viewsolution/34204684

19 Likes

In my solution i have included all cases one by one and also wrote documentation for better understanding so that i don’t get lost along the way. So, here’s my submission https://www.codechef.com/viewsolution/34050106

9 Likes

what kind of question was this? until unless i m not the author i cannt solve it. Its very specific solution.

21 Likes

i got full 100…but i still wonder about one thing…according to the first test case every no should be between -10 to 10. This implies that the maximum multiplication required anywhere should be at max 10 and similarly maximum sum required should be 20…so i ran the brute for every possible sum & multiplication but this failed…it however worked for 100 and 200 respectively…why?

2 Likes

fun fact: 1000+ peoples can`t be author.

5 Likes

wait, what?!
HOLD UP

22 Likes

For video editorial of this problem you can visit this link.

13 Likes

can anybody tell me a test case for which 90 marks solution was failing because i did for 90 marks but unable to find the wrong testcase to get 100 marks.
thanks for any help !!

Tried hard with as many test cases but hard luck.
Can someone pls give me a test case where this fails OR rather tell me a case i’m missing out ? @rajarshi_basu @smartnj @fmota
https://www.codechef.com/viewsolution/34401915

I got the logic, but still couldn’t make it. Now gonna check which cases were being failed.
It was working so perfectly on my local system. :sob: :sob:

4 Likes

Exactly!, I have just brute forced for 20 and 20 respectively and tried so hard, But it was unsuccessful. I thought there is some edge I am missing and left it

2 Likes

I faced the same issue.
Later on I figured the test cases which Sub task2 is not covering but Sub task 1 covered. Here are few Cases in the order of p,q,r,a,b,c. Hope this might help.
10 -6 0 -10 6 6
-3 0 2 6 0 -4
-3 0 3 -6 1 6
5 2 0 0 0 -4
0 3 3 -4 6 6
1 -2 0 4 -8 0
0 5 2 1 0 0
-3 0 5 3 -8 -5
0 8 3 1 0 0
-1 7 0 1 -7 4
-5 0 -10 0 -6 0

3 Likes

My crazy solution: https://www.codechef.com/viewsolution/34184127

Even the hard test case to find that is mentioned in editorial is getting passed, and such similar cases. I was unable to find where it failed. :sleepy:

1 Like

Not a big fan of this question! Tests no logic, just whether someone can find all test cases or not. If you are lucky / experienced, you will get it soon, else you’ll have to spend days like me generating large cases and adding conditions…

13 Likes

Don’t we have to consider different cases for situations like :

  1. when we add a number to tuple and then multiply to make it target tuple
  2. when we multiply a number to tuple and then add a number to make it target tuple

What i am trying to ask is wont the order generate different results? So shouldn’t we include both orders in the brute force?

No man…using simple tenth class math could have got you an AC

1 Like