I highly disagree, my AC code has 250 lines and was by far the most painful to debug of all problems (excluding PPARTS and DIFVAL, which I didn’t solve).
No it won’t.
eg. multiplying ‘x’ to p,q,r and add ‘y’ to q,r, First case is: p*x, q*x + y, r*x + y, and other one is: p*x, r*x + y*x ((r+y)*x), q*x + y*x ((q+y)*x)… In the second case, we can consider y*x as y’(some constant)
suppose you have to reach from 5 to 8
you can do this by multiplying with 12 and adding -52 so it is not necessary that the multiplier is in the range -10 to 10
#include <bits/stdc++.h>
using namespace std;
const int minf = -1000000001;
int func(vector<int> s,vector<int> f,vector<int> add,vector<int> mul){
if((s[2]+add[0]+add[1])==f[2]) return 1;
if(mul[1]!=minf && ((s[2]+add[0])*mul[1])==f[2]) return 2;
if(mul[0]!=minf && (s[2]*mul[0] + add[1])==f[2]) return 3;
if(mul[0]!=minf && mul[1]!=minf && (s[2]*mul[0]*mul[1])==f[2]) return 4;
if(mul[2]!=minf && (s[0]*mul[2]-f[0])==(s[1]*mul[2]-f[1])) return 5;
if((s[0]+add[2])!=0 && f[0]%(s[0]+add[2])==0 && (s[1]+add[2])!=0 && f[1]%(s[1]+add[2])==0 && (f[0]/(s[0]+add[2]))==(f[1]/(s[1]+add[2]))) return 6;
if(s[1]!=0 && (f[1]-add[2])%s[1]==0 && s[0]!=0 && (f[0]-add[2])%s[0]==0 && ((f[1]-add[2])/s[1])==((f[0]-add[2])/s[0]))return 7;
if(mul[2]!=minf && mul[2]!=0 && f[1]%mul[2]==0 && f[0]%mul[2]==0 && (f[1]/mul[2] - s[1])==(f[0]/mul[2] - s[0]))return 8;
if((s[0]-s[1])!=0 && (f[0]-f[1])%(s[0]-s[1])==0){
int x = (f[0]-f[1])/(s[0]-s[1]);
int y = f[0]-s[0]*x;
if((s[2]*x+y)==f[2])return 9;
}
return 0;
}
int main() {
int t;
cin >> t;
while(t--){
vector<int> s(3),f(3);
for(int i=0;i<3;i++)cin >> s[i];
for(int i=0;i<3;i++)cin >> f[i];
int ne = 0;
vector<int> add,mul;
for(int i=0;i<3;i++){
if(s[i]!=f[i]){
add.push_back(f[i]-s[i]);
mul.push_back(s[i]==0 ? minf : (f[i]%s[i]==0 ? f[i]/s[i] : minf));
}
else ne++;
}
int ans;
if(ne==3)ans = 0;
else if(ne==2)ans = 1;
else if(ne==1){
ans = 2;
if(add[0]==add[1])ans = 1;
if(mul[0]==mul[1] && mul[0]!=minf)ans = 1;
}
else{
ans = 3;
if(add[0]==add[1] || add[1]==add[2] || add[2]==add[0])ans = 2;
if((mul[0]==mul[1] && mul[0]!=minf) || (mul[1]==mul[2] && mul[1]!=minf) || (mul[2]==mul[0] && mul[2]!=minf))ans = 2;
vector<int> index = {0,1,2};
do{
vector<int> a(3),b(3),c(3),d(3);
for(int i=0;i<3;i++){
a[i] = s[index[i]];
b[i] = f[index[i]];
c[i] = add[index[i]];
d[i] = mul[index[i]];
}
if(func(a,b,c,d)>0){
ans = 2;
break;
}
}while(next_permutation(index.begin(),index.end()));
if(add[0]==add[1] && add[1]==add[2])ans = 1;
if(mul[0]==mul[1] && mul[1]==mul[2] && mul[0]!=minf)ans = 1;
}
cout << ans << '\n';
}
}
oh yes…thanks bro
it was painful no doubts about that but i disagree that it was not logical
-6 9 -3
3 -6 9
Answer: 2
What the hell i am doing wrong ?
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <bitset>
#include <iomanip>
#include <assert.h>
using namespace std;
#define endl '\n'
#define bp(x) __builtin_popcount(x)
#define zf(x) __builtin_clz(x)
#define zl(x) __builtin_ctz(x)
#define par(x) __bultin_parity(x)
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios::sync_with_stdio(0); std::cin.tie(0);
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define i128 __int128
using ll = long long;
/* **************************************************************************************** */
bool poss1_base_(ll p, ll q, ll r, ll a, ll b, ll c)
{
ll d;
if(p != 0 && a % p == 0)
{
d = a / p;
if(
(q * d == b || q == b) && (r * d == c || r == c)
)
return true;
}
d = a - p;
if(
(q + d == b || q == b) && (r + d == c || r == c)
)
return true;
return false;
}
bool poss1(ll p, ll q, ll r, ll a, ll b, ll c)
{
return
poss1_base_(p, q, r, a, b, c) ||
poss1_base_(q, p, r, b, a, c) ||
poss1_base_(r, p, q, c, a, b) ;
}
bool poss2_base_(ll p, ll q, ll r, ll a, ll b, ll c)
{
ll d;
if(p != 0 && a % p == 0)
{
d = a / p;
if(
//poss1(a, q, r, a, b, c) ||
poss1(a, q * d, r, a, b, c) ||
poss1(a, q, r * d, a, b, c) ||
poss1(a, q * d, r * d, a, b, c)
)
return true;
}
d = a - p;
if(
//poss1(a, q, r, a, b, c) ||
poss1(a, q + d, r, a, b, c) ||
poss1(a, q, r + d, a, b, c) ||
poss1(a, q + d, r + d, a, b, c)
)
return true;
return false;
}
bool poss2__(ll p, ll q, ll r, ll a, ll b, ll c)
{
return
poss2_base_(p, q, r, a, b, c) ||
poss2_base_(q, p, r, b, a, c) ||
poss2_base_(r, p, q, c, a, b);
}
bool linear(ll x1, ll x2, ll x3, ll y1, ll y2, ll y3)
{
if (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) != 0 )
return false;
return true;
}
bool fit_line(ll x1, ll x2, ll x3, ll y1, ll y2, ll y3)
{
if(!linear(x1, x2, x3, y1, y2, y3))
return false;
set <ll> xs;
xs.insert(x1);xs.insert(x2);xs.insert(x3);
if(xs.size() == 3 && (y2 - y1) % (x2 -x1) != 0)
return false;
if(xs.size() == 3 && (y3 - y1) % (x3 - x1) != 0)
return false;
return true;
}
bool poss2(ll p, ll q, ll r, ll a, ll b, ll c)
{
//Two seprate additions on two different subsets
if(a == b && b == c)
return true;
set <ll> subs;
subs.insert(a - p);subs.insert(b - q);subs.insert(c - r);
assert(subs.size() > 1);
if(subs.size() == 2)
return true;
subs.clear();
//Two seprate multiplications on two different subsets
if(p != 0 && q != 0 && r != 0 && a % p == 0 && b % q == 0 && c % r == 0)
{
subs.insert(a / p);subs.insert(b / q);subs.insert(c / r);
assert(subs.size() > 1);
if(subs.size() == 2)
return true;
}
subs.clear();
//Damn line
if(fit_line(p, q, r, a, b, c))
{
return true;
}
//The mixed - Maybe recursion ??
if(poss2__(p, q, r, a, b, c))
return true;
return false;
}
void test_case()
{
FAST_IO
ll p, q, r, a, b, c;
cin >> p >> q >> r >> a >> b >> c;
set < pair<ll, ll> > uni;
if(p != a) uni.insert({p, a});
if(q != b) uni.insert({q, b});
if(r != c) uni.insert({r, c});
if(uni.size() == 0)
{
cout << '0' << endl;
}
else if(uni.size() == 1)
{
cout << '1' << endl;
}
else if(uni.size() == 2)
{
// 1 or 2
p = (*uni.begin()).first;
a = (*uni.begin()).second;
q = (*uni.rbegin()).first;
b = (*uni.rbegin()).second;
//1
if((p != 0 && q != 0 && a % p == 0 && b % q == 0 && a / p == b / q ) || (a - p == b - q))
cout << '1' << endl;
//2
else
cout << '2' << endl;
}
else
{
// 1 or 2 or 3
//1
if( (a - p == b - q && b - q == c - r) || (p != 0 && q != 0 && r != 0 && a % p == 0 && b % q == 0 && c % r == 0 && a / p == b / q && b / q == c / r) )
cout << '1' << endl;
//2
else if(poss2(p, q, r, a, b, c))
cout << '2' << endl;
//3
else
cout << '3' << endl;
}
return ;
}
int main()
{
FAST_IO
int t;
cin >> t;
while(t -- )
test_case();
return 0;
}
Don’t know exactly but can give you a counter test case for which your code fails
1
0 0 0
1 2 3
answer should be 2 but your code is giving 1 as output
I had the same issue. Here are few cases which failed for my 90 marks solution and passed for my 10 marks solution. Hope this might be helpful.
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
Since Max is 2.
If Ans is not 0 and not 1 then ans wil surely be 2?
What is the need to check for 2?
Is there need for function check_two?
This is my solution to ttuple. its quite huge one but doesn’t work. So if anyone can help me out (by telling some test cases where it fails or directly some condition that i missed) it would be great!
/code/
#include<bits/stdc++.h>
using namespace std;
/typededfs/
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<int, ll> pil;
typedef vector vi;
typedef vector vll;
typedef vector vs;
/consts/
const int INF = (int) 1e9+5;
const long long LINF = (ll) 4e18+5;
const int M = 1e9+7;
/defines/
#define F first
#define S second
#define pb push_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define forz(i,n) for(int i=0;i<(n);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define rforz(i,n) for(int i=(n-1);i>=0;i–)
#define rfore(i,a,b) for(int i=(a);i>=(b);i–)
#define endl ‘\n’
#define o0(a) cout<<a<<’ ’
#define o1(a) cout<<a<<endl
#define o2(a,b) cout<<a<<’ '<<b<<endl
#define test int T; cin>>T; while(T–)
/templates/
template T gcd(T a, T b) { return (b == 0) ? abs(a) : gcd(b, a % b); }
template inline T lcm(T a, T b) { return a / gcd(a, b) * b; }
int main(){
FASTIO;
test{
ll p,q,r,a,b,c;
cin>>p>>q>>r;
cin>>a>>b>>c;
int ans=3;
if((a==p)&&(b==q)&&(c==r)){
// 3 same
ans=0;
}
else if(((a==p)&&(b==q))||((a==p)&&(c==r))||((b==q)&&(c==r)))
{
// 2 same
ans=1;
}
else if((a==p)||(b==q)||(c==r))
{
// 1 same
if(a==p){
if((b-q)==(c-r)){ans=1;}
else if((q!=0)&&(r!=0)&&(b%q==0)&&(c%r==0)&&(b/q==c/r)){ans=1;}
else{ans=2;}
}
else if(b==q){
if((a-p)==(c-r)){ans=1;}
else if((p!=0)&&(r!=0)&&(a%p==0)&&(c%r==0)&&(a/p==c/r)){ans=1;}
else{ans=2;}
}
else if(c==r){
if((q!=0)&&(p!=0)&&(b%q==0)&&(a%p==0)&&(b/q==a/p)){ans=1;}
else if((b-q)==(a-p)){ans=1;}
else{ans=2;}
}
}
else
{
// no same
//1stepmultiply {1,2,3} -> {2,4,6}
if((p!=0)&&(q!=0)&&(r!=0)&&(a%p==0)&&(b%q==0)&&(c%r==0)&&((a/p)==(b/q))&&((b/q)==(c/r)))
{ //cout<<"irewlabakrdl";
ans=1;
}
//1 step add {1,2,3} -> {5,6,7}
else if(((a-p)==(b-q))&&((b-q)==(c-r))){
//cout<<"diffoneelseelseif1 :";
ans=1;
}
// 2 step
//multiply->add
//multiply all add all (MA33) {1,2,3}->{2,4,6}->{3,5,7}
else if((q!=r)&&(p!=q)&&((b-c)%(q-r)==0)&&((a-b)%(p-q)==0)&&((b-c)/(q-r)==(a-b)/(p-q))){
ans=2;
}
else if((p==q)&&(p!=r)&&(a==b)&&(r!=0)&&((c-a)%(r-p)==0)&&((c-b)%(r-q))&&((c-b)/(r-q))==(c-a)/(r-p)){
ans=2;
}
else if((p==r)&&(p!=q)&&(a==c)&&(q!=0)&&((b-a)%(q-p)==0)&&((b-c)%(q-r)==0)&&((b-a)/(q-p)==(b-c)/(q-r))){
ans=2;
}
else if((q==r)&&(q!=p)&&(b==c)&&(p!=0)&&((a-b)%(p-q)==0)&&((a-c)%(p-r)==0)&&((a-c)/(p-r)==(a-b)/(p-q))){
ans=2;
}
// multiply all add 2 (MA32) {1,2,3} -> {2,4,6} -> {3,5,6}
else if((r!=0)&&(c%r==0)&&((a-b)==((c/r)*(p-q)))){
ans=2;
}
// multiply all add 2
else if((q!=0)&&(b%q==0)&&((a-c)==((p-r)*(b/q)))){
ans=2;
}
// multiply all add 2
else if((p!=0)&&(a%p==0)&&((c-b)==((r-q)*(a/p)))){
ans=2;
}/*verified*/
// multiply all add 1 {1,2,3} -> {2,4,6} -> {3,4,6}
else if((q!=0)&&(r!=0)&&(b%q==0)&&(c%r==0)&&((b/q)==(c/r))){
ans=2;
}
// multiply all add 1
else if((p!=0)&&(r!=0)&&(a%p==0)&&(c%r==0)&&((a/p)==(c/r))){
ans=2;
}
// multiply all add 1
else if((p!=0)&&(q!=0)&&(a%p==0)&&(b%q==0)&&((a/p)==(b/q))){
ans=2;
}
// multiply 2 add all (MA32) {1,2,3} -> {2,4,3} -> {3,5,4}
else if((p!=q)&&((a-b)%(p-q)==0)){
ans=2;
}
else if((p!=r)&&((c-a)%(p-r)==0)){
ans=2;
}
else if((q!=r)&&((b-c)%(q-r)==0)){
ans=2;
}
// multiply 2 add 2 (MA22) {1,2,3} -> {2,4,3} -> {2,5,4}
else if((p!=0)&&(q!=0)&&((b-c+r)%q==0)&&(a%p==0)&&(a/p==((b-c+r)/q))){
ans=2;
}
else if((p!=0)&&(q==0)&&((r+b)==c)&&(a%p==0)){
ans=2;
}
// multiply 2 add 2
else if((p!=0)&&(q!=0)&&((a-c+r)%p==0)&&(b%q==0)&&(b/q==((a-c+r)/p))){
ans=2;
}
else if((p==0)&&(q!=0)&&((r+a)==c)&&(b%q==0)){
ans=2;
}
// multiply 2 add 2
else if((q!=0)&&(r!=0)&&((b-a+p)%q==0)&&(c%r==0)&&(c/r==((b-a+p)/q))){
ans=2;
}
else if((r!=0)&&(q==0)&&(c%r==0)&&((p+b)==a)){
ans=2;
}
// multiply 2 add 2
else if((q!=0)&&(r!=0)&&((c-a+p)%r==0)&&(b%q==0)&&(b/q==((c-a+p)/r))){
ans=2;
}
else if((q!=0)&&(r==0)&&(b%q==0)&&((p+c)==a)){
ans=2;
}
// multiply 2 add 2
else if((p!=0)&&(r!=0)&&((a-b+q)%p==0)&&(c%r==0)&&(c/r==((a-b+q)/p))){
ans=2;
}
else if((p==0)&&(r!=0)&&(c%r==0)&&((q+a)==b)){
ans=2;
}
// multiply 2 add 2
else if((p!=0)&&(r!=0)&&((c-b+q)%r==0)&&(a%p==0)&&(a/p==((c-b+q)/r))){
ans=2;
}
else if((r==0)&&(p!=0)&&(a%p==0)&&((q+c)==b)){
ans=2;
}
// multiply 2 add 1 ~~ to multiply 3 add 1
// multiply 1 add 3 (MA13)
else if((a-p)==(b-q)){
ans = 2;
}
// multiply 1 add 3
else if((b-q)==(c-r)){
ans = 2;
}
// multiply 1 add 3
else if((a-p)==(c-r)){
ans = 2;
}
// multiply 1 add 2 ~~ same as multiply 1 add 3
// multiply 1 add 1 ~~ (doesnt make sense)
// 2 step
//add->multiply
// add all multiply all (AM33) same as MA33
// add all multiply 2 (AM32)
else if(((q+c-r)!=0)&&((p+c-r)!=0)&&(b%(q+c-r)==0)&&(a%(p+c-r)==0)&&(b/(q+c-r)==a/(p+c-r))){
ans=2;
}
else if(((q+c-r)!=0)&&(a==0)&&((p+c-r)==0)&&(b%(q+c-r)==0)){
ans=2;
}
else if(((q+c-r)==0)&&(b==0)&&((p+c-r)!=0)&&(a%(p+c-r)==0)){
ans=2;
}
// add all multiply 2
else if(((r+b-q)!=0)&&((p+b-q)!=0)&&(c%(r+b-q)==0)&&(a%(p+b-q)==0)&&(c/(r+b-q)==a/(p+b-q))){
ans=2;
}
else if(((r+b-q)!=0)&&(a==0)&&((p+b-q)==0)&&(c%(r+b-q)==0)){
ans=2;
}
else if(((r+b-q)==0)&&(c==0)&&((p+b-q)!=0)&&(a%(p+b-q)==0)){
ans=2;
}
// add all multiply 2
else if(((r+a-p)!=0)&&((q+a-p)!=0)&&(c%(r+a-p)==0)&&(b%(q+a-p)==0)&&(c/(r+a-p)==b/(q+a-p))){
ans=2;
}
else if(((r+a-p)!=0)&&(b==0)&&((q+a-p)==0)&&(c%(r+a-p)==0)){
ans=2;
}
else if(((r+a-p)==0)&&(c==0)&&((q+a-p)!=0)&&(b%(q+a-p)==0)){
ans=2;
}
// add all mutiply 1 (AM31) same as MA13
// add 2 multiply all (AM23) same as MA32
// add 2 multiply 2 (AM22)
else if((r!=0)&&((q+a-p)!=0)&&(c%r==0)&&(b%(q+a-p)==0)&&(c/r==b/(q+a-p))){
ans=2;
}
else if((r!=0)&&((q+a-p)==0)&&(c%r==0)&&(b==0)){
ans=2;
}
// add 2 multiply 2
else if( (r!=0)&&((p+b-q)!=0)&&(c%r==0) && (a%(p+b-q)==0) && (c/r==a/(p+b-q)) ){
ans=2;
}
else if((r!=0)&&((p+b-q)==0)&&(c%r==0)&&(a==0)) {
ans=2;
}
// add 2 multiply 2
else if((q!=0)&&((p+c-r)!=0)&&(b%q==0)&&(a%(p+c-r)==0)&&(b/q==a/(p+c-r))){
ans=2;
}
else if((q!=0)&&((p+c-r)==0)&&(b%q==0)&&(a==0)){
ans=2;
}
// add 2 multiply 2
else if((q!=0)&&((r+a-p)!=0)&&(b%q==0)&&(c%(r+a-p)==0)&&(b/q==c/(r+a-p))){
ans=2;
}
else if((q!=0)&&((r+a-p)==0)&&(b%q==0)&&(c==0)){
ans=2;
}
// add 2 multiply 2
else if((p!=0)&&((q+c-r)!=0)&&(a%p==0)&&(b%(q+c-r)==0)&&(a/p==b/(q+c-r))){
ans=2;
}
else if((p!=0)&&((q+c-r)==0)&&(a%p==0)&&(b==0)){
ans=2;
}
// add 2 multiply 2
else if((p!=0)&&((r+b-q)!=0)&&(a%p==0)&&(c%(r+b-q)==0)&&(a/p==c/(r+b-q))){
ans=2;
}
else if((p!=0)&&((r+b-q)==0)&&(a%p==0)&&(c==0)){
ans=2;
}
// add 2 multiply 1 (AM21) ~~ repeat case
// add 1 multiply 3 (AM13) ~~ repeat case
// add 1 multiply 2 (AM12) ~~ repeat casse
// add 1 multiply 1 (AM11) ~~ repeat case
// add->add (AA22) (only unique case when adding ie p+x=a; q+y=b: r+x+y=c;)
else if((b-a-c)==(q-p-r)){
ans=2;
}
else if((a-b-c)==(p-q-r)){
ans=2;
}
else if((c-a-b)==(r-p-q)){
ans=2;
}
// M->M (MM22) (p*x=a; q*y=b; c*x*y=r;)
else if((a*q*c)==(p*b*r)){
ans=2;
}
else if((a*r*b)==(p*q*c)){
ans=2;
}
else if((p*b*c)==(a*q*r)){
ans=2;
}
}
o1(ans);
}
}
Due I ran these cases on my solution. They are all yield same results as mine. But still my solution got 90 points and failed for subtask 1.
My solution link:
https://www.codechef.com/viewsolution/34358444
Here are few in the order of p,q,r,a,b,c
2 9 6 5 -6 -4
-10 -6 -3 5 1 2
7 8 1 -4 -4 -3
0 4 -6 0 -4 6
8 4 6 -6 -3 -6
4 8 9 3 6 -10
-2 4 4 5 -4 -10
-3 8 3 7 0 -7
9 3 -8 3 1 -6
-10 1 -6 5 9 3
-4 4 -1 -5 5 -8
5 -4 -4 -6 -6 -10
10 -9 9 -2 -2 2
7 9 10 -7 7 2
2 -2 7 5 -5 -5
-8 4 -6 10 -5 -4
4 -2 4 -10 5 -7
3 9 5 -4 -2 2
7 -7 -7 5 -5 -7
-8 4 -1 -2 -10 10
-9 -2 9 3 9 -3
-3 -10 9 -1 -6 3
9 0 3 -10 1 -3
5 6 8 -4 -8 2
7 2 9 -8 -3 10
0 0 1 -4 -8 2
5 8 10 -3 5 -3
And I got 10 points but was unable to find what test case is missing in 2nd subtask.
Dude, it’s 1. Multiply all with 0.
Are all the testcases having an answer of two?