PROBLEM LINK:
Author \ \ \ \ \ \ \, - \ ishwarendra
Tester \ \ \ \ \ \ \ \, - \ ishwarendra
Editorialist \ - \ ishwarendra
DIFFICULTY:
SIMPLE-EASY.
PREREQUISITES:
Basic Observation, Math,
Cramer’s Rule (For alternate approach)
PROBLEM:
(Brief description only)
Given Packet of items for making a dish, find if it’s possible to make all four dishes in some amount (possible 0) such that no packet remains unused.
NOTE: Readers who have not yet read the problem statement are encouraged to first read it before moving on.
HINTS AND QUICK EXPLANATION:
Hint-1
Is (\ a + b + c + d\ ) being divisible by 10, 20 or 40 enough to prove that there will always exist an answer
For example: If packets of dishes present are: 40, 160, 80, 120. Will chef be able to do as he intends to?
Hint-2
Are you considering the fact that your found solution might be an integer but negative?
SHORT EXPLANATION
Assume the amount of each dish and form simultaneous linear equation of 4 variables.
In order to solve that you can either add all equations to get a new equation and then subtract two consecutive equations (which you formed) to find all variables or simply use Cramer’s rule.
Beware of Overflow issue in case you are using cramer’s rule
EXPLANATION:
It is already stated in question that one packet can be used to make only 1 dish, i.e. you cannot use half item of a packet to make dish-1 and the rest to make dish-2.
Let us assume that number of dish-1, dish2, dish3, dish4 made by chef are x_{1}, x_{2}, x_{3} and x_{4} respectively.
According to the data given in question we can form the following four equations:
x_1 + 2*x_2 + 3*x_3 + 4*x_4 = a \quad \quad.....\quad(i)
4*x_1 + x_2 + 2*x_3 + 2*x_4 = b \quad \quad.....\quad(ii)
3*x_1 + 4*x_2 + x_3 + 2*x_4 = c \quad \quad.....\quad(iii)
2*x_1 + 3*x_2 + 4*x_3 + x_4 = d \quad \quad.....\quad(iv)
Subtracting (i)\ and\ (ii), we get the following equation
\ \ \ \ -3*x_1 + x_2 + x_3 + x_4 = a - b
or, \ x_1 + x_2 + x_3 + x_4 = a - b + 4*x_1 \quad \quad.....\quad(v)
Now somehow if we can get this sum x_1 + x_2 + x_3 + x_4 then we can easily solve for x_1.
Here, we observe that every equation has 1, 2, 3 \; and\; 4\ (in some order) as their coefficient, thus we can add them to get a equation of the following form
c*x_1 + c*x_2 + c*x_3 + c*x_4 = a + b + c + d \quad \quad.....\quad(vi)\
(In our case, c = 10)
Equation-(vi) leads us to our first condition i.e. 10 must divide (a + b + c + d). This condition is necessary but not sufficient.
Another good thing is that we have found the sum x_1 + x_2 + x_3 + x_4 which will not just help to tell whether chef’s task can done or not but we can even tell the amount of each dish he can make if it’s possible.
Coming back to equation-(v), let us call \ x_1 + x_2 + x_3 + x_4 = S
Thus we can re-write equation-(v) as :\ x_1 = \frac{S - a + b}{4}.
Similarly, we can subtract [equations\ (ii) , (iii)], [equations\ (iii) , (iv)], and\ [equations\ (iv) , (i)] to obtain the value of other 3 variables. (x_2, x_3\ and\ x_4)
Our task is now almost complete. All We need is to check the following two conditions for all four variables (x_1, x_2, x_3\ and\ x_4)
1. Is any of the variable negative?
2. Is any variable a not an integer? Careful: In C++, a\ /\ b is equivalent to integer division if both a and b are integers
It is easy to check condition-1 but testing condition-2 might be a bit tricky if you have never done it before.
Feel free to move on if you already know how to.
Check for condition-2
One way is to do a / b == a / (long double)b but this method might not work due to precision issues.
Other way is to check whether a % b == 0 or not. Checking this tells us whether b divides a or not.
If it does then we can guarantee that a/b is an integer, otherwise it is not
If both the conditions are true then it is possible for chef to completely use all packets, otherwise it’s not.
ALTERNATE EXPLANATION:
Another possible way is to use cramer’s rule to find out the solution and then check if solution is acceptable for us or not (using above 2 conditions).
NOTE: Due to high constraint there are chances of your determinant values to exceed long long and even unsigned long long range.
TIME COMPLEXITY:
O(1) per test case
SOLUTIONS:
Setter's Solution (CPP)
#include <bits/stdc++.h>
using namespace std;
long long custom_divide(const long long numerator, const long long denominator)
{
// if (numerator/denominator) is an long longeger value simply return it else return -1
if ((numerator % denominator) == 0)
return numerator/denominator;
return -1;
}
int main()
{
int t; cin >> t;
while(t--)
{
long long a, b, c, d;
cin >> a >> b >> c >> d;
// cout << a + b + c + d << "\n";
long long sum = custom_divide(a + b + c + d, 10);
if (sum < 0)
{
cout << "NO\n";
continue;
}
long long dish1 = custom_divide(sum + b - a, 4);
long long dish2 = custom_divide(sum + c - b, 4);
long long dish3 = custom_divide(sum + d - c, 4);
long long dish4 = custom_divide(sum + a - d, 4);
if (dish1 < 0 or dish2 < 0 or dish3 < 0 or dish4 < 0)
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}
Setter's Solution (Python)
def custom_divide(numerator, denominator):
if numerator % denominator == 0:
return numerator//denominator
return -1
T = int(input())
for _ in range(T):
a, b, c, d = [int(x) for x in input().split()]
S = custom_divide(a + b + c + d, 10)
if (S < 0):
print("NO")
continue;
dish1 = custom_divide(S + b - a, 4)
dish2 = custom_divide(S + c - b, 4)
dish3 = custom_divide(S + d - c, 4)
dish4 = custom_divide(S + a - d, 4)
if dish1 < 0 or dish2 < 0 or dish3 < 0 or dish4 < 0:
print("NO")
else:
print("YES")
Alternate Solution (Python)
Contributed by Abhinav Rawal
from sys import stdin,stdout
from copy import deepcopy
def minor(m,i,j):
return [row[:j] + row[j+1:] for row in (m[:i]+m[i+1:])]
def det(m):
#base case for 2x2 matrix
if len(m) == 2:
return m[0][0]*m[1][1]-m[0][1]*m[1][0]
determinant = 0
for c in range(len(m)):
determinant += ((-1)**c)*m[0][c]*det(minor(m,0,c))
return determinant
d1 = [[1,2,3,4],
[4,1,2,3],
[3,4,1,2],
[2,3,4,1]]
d2 = deepcopy(d1)
d3 = deepcopy(d1)
d4 = deepcopy(d1)
sol = [d1,d2,d3,d4]
t = int(stdin.readline())
for test in range(t):
coeff = list(map(int,stdin.readline().split()))
for i in range(4):
for j in range(4):
sol[i][j][i] = coeff[j]
value = det(sol[i])
if(value > 0 or value%160 != 0):
stdout.write("NO" + '\n')
break
else:
stdout.write("YES" + '\n')
