Well It just fails at one case:
when (a,b,c) —> (p,q,r)
p = ka+d
q = kb+d
r = c+d
It fails in the 3 permutations of this case only I believe
Salute your patience man !!!
1 Like
try:
import random
def randoms():
return random.randint(-10,10)
def goopo(a,b,c,p,q,r):
if a!=0:
if p/a==int(p/a):
if q-b*(p/a)==r-c*(p/a):
return True
if b!=0:
if q/b==int(q/b):
if p-a*(q/b)==r-c*(q/b):
return True
if c!=0:
if r/c==int(r/c):
if q-b*(r/c)==p-a*(r/c):
return True
return False
def checkthreeoftwoproduct(a,b,c,p,q,r):
if a!=0:
x=p/a
else:
x=9999999999
if b!=0:
y=q/b
else:
y=9999999999
if c!=0:
z=r/c
else:
z=9999999999
if x==int(x) and y==int(y) and z==int(z):
if x*y == z or z*y==x or x*z==y:
return True
return False
def checkthreeoftwosum(a,b,c,p,q,r):
x=p-a
y=q-b
z=r-c
if x==y+z or z==x+y or y==x+z:
return True
return False
def checklastsum(a,b,c,p,q,r):
x=p-a
y=q-b
z=r-c
if b+x!=0 and c!=0 :
if ((q/(b+x))==r/c) and r/c == int(r/c):
return True
if c+x!=0 and b!=0 :
if ((r/(c+x))==q/b) and q/b == int(q/b):
return True
if b+z!=0 and a!=0 :
if ((q/(b+z))==p/a) and p/a == int(p/a):
return True
if a+z!=0 and b!=0 :
if ((p/(a+z))==q/b) and q/b == int(q/b):
return True
if c+y!=0 and a!=0:
if ((r/(c+y))==p/a) and p/a == int(p/a):
return True
if a+y!=0 and c!=0 :
if ((p/(a+y))==r/c) and r/c == int(r/c):
return True
return False
def checklastproduct(a,b,c,p,q,r):
if a!=0:
if p/a==int(p/a):
x=p/a
if (q-b*x==r-c) or (r-c*x==q-b):
return True
if b!=0:
if q/b==int(q/b):
x=q/b
if (p-a*x==r-c) or (r-c*x==p-a):
return True
if c!=0:
if r/c==int(r/c) and c!=0:
x=r/c
if (q-b*x==p-a) or (p-a*x==q-b):
return True
return False
def operation(p,q,r,a,b,c,t):
x=p-a*t
y=q-b*t
z=r-c*t
if (x==y==z) and t==int(t):
return True
else:
return False
def hoopo(a,b,c,p,q,r):
if (a-b)!=0:
t1=(p-q)/(a-b)
else:
t1=9999999999.9
if (b-c)!=0:
t2=(q-r)/(b-c)
else:
t2=9999999999.9
if (c-a)!=0:
t3=(r-p)/(c-a)
else:
t3=9999999999.9
if operation(p,q,r,a,b,c,t1) and t1==int(t1):
return True
if operation(p,q,r,a,b,c,t2) and t2==int(t2):
return True
if operation(p,q,r,a,b,c,t3) and t3==int(t3):
return True
return False
def operations2(p,q,r,a,b,c,k):
if (a+k==p) and b+k!=0 and c+k!=0:
if (q/(b+k)==r/(c+k)) and r/(c+k)==int(r/(c+k)):
return True
if (b+k==q) and a+k!=0 and c+k!=0:
if (p/(a+k)==r/(c+k)) and r/(c+k)==int(r/(c+k)):
return True
if (c+k==r) and b+k!=0 and a+k!=0:
if (q/(b+k)==p/(a+k)) and p/(a+k)==int(p/(a+k)):
return True
return False
def joopo(a,b,c,p,q,r):
k1=p-a
k2=q-b
k3=r-c
if operations2(p,q,r,a,b,c,k1):
return True
if operations2(p,q,r,a,b,c,k2):
return True
if operations2(p,q,r,a,b,c,k3):
return True
return False
for _ in range(int(input())):
a,b,c=map(int,input().split())
p,q,r=map(int,input().split())
#a=randoms()
#b=randoms()
#c=randoms()
#p=randoms()
#q=randoms()
#r=randoms()
#print(a,b,c)
#print(p,q,r)
equals=0
if p==a:
equals+=1
if q==b:
equals+=1
if r==c:
equals+=1
if (equals==3):
steps=0
elif (equals==2):
steps=1
elif (equals==1):
x=p-a
y=q-b
z=r-c
if a!=0:
xx=p/a
else:
xx=9999999999
if b!=0:
yy=q/b
else:
yy=9999999999
if c!=0:
zz=r/c
else:
zz=9999999999
if x==y!=0 or y==z!=0 or z==x!=0:
steps=1
elif ((xx==yy!=9999999999 and xx==int(xx) and zz==1) or (yy==zz!=9999999999 and yy==int(yy) and xx==1) or (zz==xx!=9999999999 and zz==int(zz) and yy==1)):
steps=1
else:
steps=2
elif (equals==0):
x=p-a
y=q-b
z=r-c
if a!=0:
xx=p/a
else:
xx=9999999999
if b!=0:
yy=q/b
else:
yy=9999999999
if c!=0:
zz=r/c
else:
zz=9999999999
if x==y==z!=0 or (xx==yy==zz!=9999999999 and xx==int(xx)):
steps=1
elif x==y!=0 or y==z!=0 or z==x!=0:
steps=2
elif ((xx==yy!=9999999999 and xx==int(xx) and zz==1) or (yy==zz!=9999999999 and yy==int(yy) and xx==1) or (zz==xx!=9999999999 and zz==int(zz) and yy==1)):
steps=2
elif checklastproduct(a,b,c,p,q,r):
#print(10)
steps=2
elif checklastsum(a,b,c,p,q,r):
#print(11)
steps=2
elif checkthreeoftwosum(a,b,c,p,q,r):
#print(12)
steps=2
elif checkthreeoftwoproduct(a,b,c,p,q,r):
#print(13)
steps=2
elif joopo(a,b,c,p,q,r):
#print(14)
steps=2
elif goopo(a,b,c,p,q,r):
#print(15)
steps=2
elif hoopo(a,b,c,p,q,r):
#print(16)
steps=2
elif a==0 and b==0 and c==0:
steps=2
else:
steps=3
print(steps)
except EOFError:
pass
why i am getting WA???
yes they did for sure let x=p/a y=q/b and z=r/c
if xy==z or yz==x or x*z==y:
they can be done in 2 steps
We only need to consider the multiply-add case. Why?
Let's say:
(p + i) * j = a, Eg: (6 + 3) * 4 = 36
p * j + i * j = a 6 * 4 + 3 * 4 = 36
Replace (i * j) by k Replace (3 * 4) by 12
p * j + k = a 6 * 4 + 12 = 36
So we have replaced add-multiply with multiply-add. And this can be done for any number so we need to only check the multiply-add condition.
4 Likes
I got 90 during the contest… and now after much frustration found an edge case that wasn’t working. Putting it here in case some finds it useful.
1
10 20 30
8 13 18
Output:
3
My code was giving 2. Basically it was considering non-integer multiplication.
10 * 0.5 + 3 = 8
20 * 0.5 + 3 = 13
30 * 0.5 + 3 = 18
2 Likes
My reaction just after looking at the code - “BC kya hai yeh?” 
.
But HATTTS OFFF dude for so much work. How many hours each day it took you to come up with this?
I don’t think this is an Easy-Medium problem. It is harder than that because of too many cases and no neat logic to cover them all.
The cases for 2 elements are simple, for 3 elements I solved for any pair all the equations a * d1 + d2 = x, (a + d1) * d2 = x, a + d1 + d2 = x, a * d1 * d2 = x, based on a two-bit mask that represents whether operation 1 and 2 was done or not, and see if any satisfied the equation of the remaining element, based on two cases, one in which everyone did the two operations (++ and ** operations not allowed), or in which at least one element was doing exactly one operation.
Somebidy please tell my error the code above …
is there any specific data structure which can be used to solve this problem regardless of making all these cases and all
i saw a post regarding this on geek for geeks where he has used this concept of taking all cases into consideration at a time and move forward using BFS … i would really like to know about a more specific solution to this
please help me with my code, i used BFS
#include<bits/stdc++.h>
using namespace std;
typedef long long int inti;
struct node{
inti a,b,c,p,q,r,step;
};
int main(){
inti t;
cin>>t;
while(t–){
queue que;
node n;
cin>>n.a>>n.b>>n.c;
cin>>n.p>>n.q>>n.r;
n.step=0;
que.push(n);
inti ans=3;
if(n.p==n.q&&n.q==n.r){
if(n.p==0)
ans=1;
else
ans=2;
}
while(!que.empty()){
node temp=que.front();
que.pop();
if(temp.step<ans){
if(temp.a==temp.p && temp.b==temp.q && temp.c==temp.r)
ans=min(ans,temp.step);
else{
if(temp.a!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.p/temp.a;
one.step=temp.step+1;
one.a=temp.a*q;
one.b=temp.b;
one.c=temp.c;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c;
que.push(one);
one.a=temp.a*q;
one.b=temp.b;
one.c=temp.c*q;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
}
if(temp.b!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.q/temp.b;
one.step=temp.step+1;
one.a=temp.a;
one.b=temp.b*q;
one.c=temp.c;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c;
que.push(one);
one.a=temp.a;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
}
if(temp.c!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.r/temp.c;
one.step=temp.step+1;
one.a=temp.a;
one.b=temp.b;
one.c=temp.c*q;
que.push(one);
one.a=temp.a;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
one.a=temp.a*q;
one.b=temp.b;
one.c=temp.c*q;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
}
if(temp.p-temp.a!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.p-temp.a;
one.step=temp.step+1;
one.a=temp.a+q;
one.b=temp.b;
one.c=temp.c;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c;
que.push(one);
one.a=temp.a+q;
one.b=temp.b;
one.c=temp.c+q;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
}
if(temp.q-temp.r!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.q-temp.b;
one.step=temp.step+1;
one.a=temp.a;
one.b=temp.b+q;
one.c=temp.c;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c;
que.push(one);
one.a=temp.a;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
}
if(temp.r-temp.c!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.r-temp.c;
one.step=temp.step+1;
one.a=temp.a;
one.b=temp.b;
one.c=temp.c+q;
que.push(one);
one.a=temp.a;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
one.a=temp.a+q;
one.b=temp.b;
one.c=temp.c+q;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
}
}
}
}
cout<<ans<<"\n";
}
return 0;
}
please help me with my code, i used BFS
i ran all known cases which were running fine, but answer coming is WA
#include<bits/stdc++.h>
using namespace std;
typedef long long int inti;
struct node{
inti a,b,c,p,q,r,step;
};
int main(){
inti t;
cin>>t;
while(t–){
queue que;
node n;
cin>>n.a>>n.b>>n.c;
cin>>n.p>>n.q>>n.r;
n.step=0;
que.push(n);
inti ans=3;
if(n.p==n.q&&n.q==n.r){
if(n.p==0)
ans=1;
else
ans=2;
}
while(!que.empty()){
node temp=que.front();
que.pop();
if(temp.step<ans){
if(temp.a==temp.p && temp.b==temp.q && temp.c==temp.r)
ans=min(ans,temp.step);
else{
if(temp.a!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.p/temp.a;
one.step=temp.step+1;
one.a=temp.a*q;
one.b=temp.b;
one.c=temp.c;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c;
que.push(one);
one.a=temp.a*q;
one.b=temp.b;
one.c=temp.c*q;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
}
if(temp.b!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.q/temp.b;
one.step=temp.step+1;
one.a=temp.a;
one.b=temp.b*q;
one.c=temp.c;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c;
que.push(one);
one.a=temp.a;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
}
if(temp.c!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.r/temp.c;
one.step=temp.step+1;
one.a=temp.a;
one.b=temp.b;
one.c=temp.c*q;
que.push(one);
one.a=temp.a;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
one.a=temp.a*q;
one.b=temp.b;
one.c=temp.c*q;
que.push(one);
one.a=temp.a*q;
one.b=temp.b*q;
one.c=temp.c*q;
que.push(one);
}
if(temp.p-temp.a!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.p-temp.a;
one.step=temp.step+1;
one.a=temp.a+q;
one.b=temp.b;
one.c=temp.c;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c;
que.push(one);
one.a=temp.a+q;
one.b=temp.b;
one.c=temp.c+q;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
}
if(temp.q-temp.r!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.q-temp.b;
one.step=temp.step+1;
one.a=temp.a;
one.b=temp.b+q;
one.c=temp.c;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c;
que.push(one);
one.a=temp.a;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
}
if(temp.r-temp.c!=0){
node one;
one.p=temp.p;
one.q=temp.q;
one.r=temp.r;
int q=temp.r-temp.c;
one.step=temp.step+1;
one.a=temp.a;
one.b=temp.b;
one.c=temp.c+q;
que.push(one);
one.a=temp.a;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
one.a=temp.a+q;
one.b=temp.b;
one.c=temp.c+q;
que.push(one);
one.a=temp.a+q;
one.b=temp.b+q;
one.c=temp.c+q;
que.push(one);
}
}
}
}
cout<<ans<<"\n";
}
return 0;
}
Still scored 90… 
@rajarshi_basu
@i_64
The editorial mentions you are restricted to add some thing which completes at least 1 pair , i.e. (p-a) || (q-b) || (r-c) but we can have a case
3 5 7
15 21 27
Add 2 to all and multiply all by 3
Can any one proove that what editorial says covers this case also?
1 5 7
7 27 37
should be 2 and *5 then +2
yep they are covered but as multiply by 3 and then add 6 to all
Corrected… Thanks!
This is just simple thing I missed…Thanks.