TTUPLE - Editorial

i_64 · June 15, 2020, 1:30pm

It is for handling the cases for which answer is 3

blank_kami · June 15, 2020, 1:32pm

Noob, i got 550, how do you beat that😂

anon24245385 · June 15, 2020, 1:38pm

I feel that such questions should not be added in the contest. Instead a nice DP problem would have been much better for the place of the 7th question. Anyways, here’s my solution (I got 24 WA’s before I got an AC !) -

#include <bits/stdc++.h>

typedef long long int ll;
typedef unsigned long long int ull;
typedef long int li;
typedef long double ld;
#define test ll t; cin >> t; while(t--)
#define MOD pow(10,9)+7
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define forn(i,n) for(ll i=0;i<n;i++)
#define ford(i,n) for(ll i=n-1;i>=0;i--)
#define forne(i,n,a) for(ll i=a;i<n;i++)
#define forde(i,n,a) for(ll i=n-1;i>=a;i--)
using namespace std;

void solve (){
	// problem code - TTUPLE, Author - satin1004
	ll p,q,r,a,b,c;
    cin >> p >> q >> r;
    cin >> a >> b >> c;
	if(p==a && q==b && r==c){
	    // 0 distinct
	    cout << 0 << endl;
	    return;
	}
	if(p==a && q==b && r!=c || p==a && r==c && q!=b || q==b && r==c && a!=p){
	    // 1 distinct
	    cout << 1 << endl;
	    return;
	}
	if(p==a && q!=b && r!=c){
	    // 2 distinct
	    if(b-q==c-r){
	        cout << 1 << endl;
	        return;
	    }
	    if(q!=0 && r!=0 && b%q==0 && c%r==0){
	        if(b/q == c/r){
	            cout << 1 << endl;
	            return;
	        }
	    }
	    cout << 2 << endl;
	    return;
	}
	if(p!=a && q==b && r!=c){
	    // 2 distinct
	    if(a-p==c-r){
	        cout << 1 << endl;
	        return;
	    }
	    if(p!=0 && r!=0 && a%p==0 && c%r==0){
	        if(a/p==c/r){
	            cout << 1 << endl;
	            return;
	        }
	    }
	    cout << 2 << endl;
	    return;
	   
	}
	if(p!=a && q!=b && r==c){
	    // 2 distinct
	    if(a-p == b-q){
	        cout << 1 << endl;
	        return;
	    }
	    if(p!=0 && q!=0 && a%p==0 && b%q==0){
	        if(a/p == b/q){
	            cout << 1 << endl;
	            return;
	        }
	    }
	    cout << 2 << endl;
	    return;
	   
	}
	if(p!=a && q!=b && r!=c){
	    // 3 distinct
	    if(a-p == b-q && b-q == c-r){
	        cout << 1 << endl;
	        return;
	    }
	    if(p!=0 && q!=0 && r!=0 && a%p==0 && b%q==0 && c%r==0){
	       if(a/p == b/q && b/q == c/r){
	           cout << 1 << endl;
	           return;
	       }
	    }
	}
	ll dif1 = a-p;
    ll dif2 = b-q;
    ll dif3 = c-r;
    if(dif1 + dif2 == dif3 || dif2 + dif3 == dif1 || dif1 + dif3 == dif2 || dif1== dif2 || dif2 == dif3 || dif3 == dif1){
        // Add and Add  
        cout << 2 << endl;
        return;
    }
    ll div1,div2,div3;
    bool f1=false,f2=false,f3=false;
    if(p!=0 && a%p==0){
        div1 = a/p;
        f1=true;
    }
    if(q!=0 && b%q==0){
        div2 = b/q;
        f2=true;
    }
    if(r!=0 && c%r==0){
        div3 = c/r;
        f3=true;
    }
    if(f1==true && f2==true && f3==true){
        if(div1*div2==div3 || div2*div3==div1 || div1*div3==div2 || div1==div2 || div2==div3 || div3==div1){
            cout << 2 << endl;
            return;
        }
    }
    if(f1==true && f2==true && f3==false){
        if(div1==div2){
            cout << 2 << endl;
            return;
        }
    }
    if(f2==true && f3==true && f1==false){
        if(div2==div3){
            cout << 2 << endl;
            return;
        }
    }
    if(f3==true && f1==true && f2==false){
        if(div3==div1){
            cout << 2 << endl;
            return;
        }
    }
	if((p-q)!=0 && (a-b)!=0 && (a-b)%(p-q)==0 && (b*p-a*q)%(a-b)==0){
		// Add and Multiply
		ll l = (b*p-a*q)/(a-b);
		ll k = (a-b)/(p-q);
		if((r+l)*k == c || r+l == c || r*k==c){
			cout << 2 << endl;
			return;
		}
	}
	if((q-r)!=0 && (b-c)!=0 && (b-c)%(q-r)==0 && (q*c-b*r)%(b-c)==0){
		// Add and Multiply
		ll l = (q*c-b*r)/(b-c);
		ll k = (b-c)/(q-r);
		if((p+l)*k==a || p+l==a || p*k==a){
			cout << 2 << endl;
			return;
		}
	}
	if((p-r)!=0 && (a-c)!=0 && (p*c-a*r)%(a-c)==0 && (a-c)%(p-r)==0){
		// Add and Multiply
		ll l = (p*c-a*r)/(a-c);
		ll k = (a-c)/(p-r);
		if((q+l)*k==b || q+l==b || q*k==b){ 
		    cout << 2 << endl;
		    return;
		}
	}
	
	if((p-q)!=0 && (p*b-q*a)%(p-q)==0 && (a-b)%(p-q)==0){
		// Multiply and Add
		ll l = (p*b-q*a)/(p-q);
		ll k = (a-b)/(p-q);
		if(r*k+l==c || r+l==c || r*k==c){
			cout << 2 << endl;
			return;
		}
	}
	if((p-r)!=0 && (p*c-r*a)%(p-r)==0 && (a-c)%(p-r)==0){
		// Multiply and Add
		ll l = (p*c-r*a)/(p-r);
		ll k = (a-c)/(p-r);
		if(q*k==b || q*k+l==b || q+l==b){
			cout << 2 << endl;
			return;
		}
	}
	if((q-r)!=0 && (q*c-b*r)%(q-r)==0 && (b-c)%(q-r)==0){
		// Multiply and Add
		ll l = (q*c-b*r)/(q-r);
		ll k = (b-c)/(q-r);
		if(p*k+l==a || p+l==a || p*k==a){
			cout << 2 << endl;
			return;
		}
	}
	if(q!=0){
		// Multiply and Add
		if(b%q==0){
		    ll k1 = b/q;
		   	ll l1 = c-r;
		   	if(p*k1==a || p*k1+l1==a || p+l1==a || (p+l1)*k1==a){
		   	    cout << 2 << endl;
		   	    return;
		   	}
		    ll k2 = b/q;
		    ll l2 = a-p;
		    if(r*k2==c || r+l2==c || r*k2+l2==c || (r+l2)*k2==c){
		        cout << 2 << endl;
		        return;
		    }
		}
	}
	if(r!=0){
		// Multiply and Add
		if(c%r==0){
			ll k1 = c/r;
			ll l1 = b-q;
			if(p*k1==a || p*k1+l1==a || p+l1==a || (p+l1)*k1==a){
			    cout << 2 << endl;
			    return;
			}
		    ll k2 = c/r;
		    ll l2 = a-p;
		    if(q*k2==b || q+l2==b || q*k2+l2==b || (q+l2)*k2==b){
		        cout << 2 << endl;
		        return;
		    }
		}
	}
	if(p!=0){
		// Multiply and Add
		if(a%p==0){
		    ll k1 = a/p;
		    ll l1 = b-q;
		    if(r*k1==c || r+l1==c || r*k1+l1==c || (r+l1)*k1==c){
		        cout << 2 << endl;
		        return;
		    }
		    ll k2 = a/p;
		    ll l2 = c-r;
		    if(q*k2==b || q+l2==b || q*k2+l2==b || (q+l2)*k2==b){
		        cout << 2 << endl;
		        return;
		    }
		}
	}
	cout << 3 << endl;
	return;
}
int main (){
    test {
	    solve ();
    }
}

prakhart_26 · June 15, 2020, 1:42pm

Can someone help me with my submission. I think I have covered all the cases…but I’m receiving RE. I have checked for all possible divide by 0s and all for integer overflow but couldn’t find the error. Pls help.
My code: CodeChef: Practical coding for everyone

anon43418524 · June 15, 2020, 1:54pm

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

checkmate
Not mine though

rishikeshpawar · June 15, 2020, 1:57pm

My code also failed the Subtask1. And The code gives correct ans for all your cases… Do u have some more points

keshavgargg · June 15, 2020, 1:57pm

Sorry! It should be 3… I mistyped it.

tokyo_04 · June 15, 2020, 2:02pm

Can set this solution a great example for brute-force

deepasnhu_1729 · June 15, 2020, 2:03pm

Yeah it’s insane but unfortunately it’s sol. is wrong. Even typing 1000 lines take guts
Not to mention debugging it

harish_dalal · June 15, 2020, 2:39pm

working for all still don’t know why giving wrong for subtask 1
https://www.codechef.com/viewsolution/34142515

anon25640846 · June 15, 2020, 2:45pm

Felt like an O(1) solution.

waltzer47 · June 15, 2020, 2:45pm

Kudos. Great work

keshavgargg · June 15, 2020, 2:46pm

#include<iostream>
#include<cstdlib>
using namespace std;
main() {
   int max;
   max = 22;
   int n;
   cout<<"How many test cases do you need: \n";
   cin>>n;
   srand(time(0));
   for(int i=0;i<n;i++){
   
   int a = rand()%max;
   int b = rand()%max;
   int c = rand()%max;
   int x = rand()%max;
   int y = rand()%max;
   int z = rand()%max;
   if(a>10){a-=21;}
   if(b>10){b-=21;}
   if(c>10){c-=21;}
   if(x>10){x-=21;}
   if(y>10){y-=21;}
   if(z>10){z-=21;}
   
   cout<<a<<" "<<b<<" "<<c<<"\n";
   cout<<x<<" "<<y<<" "<<z<<"\n";
   cout<<"\n";
   }
}

This code will generate use cases for subtask 1. You can take someone’s correct code and check what use cases are you failing. Hope it will help : )

ads191712 · June 15, 2020, 2:54pm

My 90 lines AC Code
https://www.codechef.com/viewsolution/34389764

i_64 · June 15, 2020, 2:55pm

Technically it is O(1)

ads191712 · June 15, 2020, 2:56pm

It would be 3 only

prakhart_26 · June 15, 2020, 3:16pm

Okay my code was not correct, but why was I getting RE and not WA?
PS: thanx for the tc generator

ziki · June 15, 2020, 3:19pm

A brute force validation is usually helpful for this kind of question.
For this question I just generated test cases with numbers < 10 and find all the cases my ‘opt code’ missed:
https://www.codechef.com/viewsolution/33758471

waltzer47 · June 15, 2020, 3:30pm

Code I wrote is giving correct answers still getting WA. Can somebody tell me any cases I’m missing?

#CodeChef: Practical coding for everyone

keshavgargg · June 15, 2020, 3:31pm

You must check p!=0 before checking if(a%p==0). Are you sure that you have done that in all your cases?