PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Praveen Dhinwa
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk
PREREQUISITES:
Basic Math and Linear Equations.
PROBLEM:
There are three friends A, B and C. They make the following claim.
- A says that I have x Rupees more than B.
- B says that I have y Rupees more than C.
- C says that I have z Rupees more than A.
Given |x|, |y| and |z|, Find out if it’s possible to assign signs to x, y and z so that all three claims hold.
SUPER QUICK EXPLANATION
- Answer is yes if and only if |x|+|y|+|z| = 2*max(|x|, |y|, |z|).
EXPLANATION
Suppose Friend A has a Rupees, B has b Rupees and C has c rupees. Then, the three claims result in the following equations.
- a = b+x
- b = c+y
- c = a+z
Substituting value of a from 1 in 3, we get c = (b+x)+z.
Substituting value of b from 2 in this equation, we get c = (c+y)+x+z.
We have the final equation x+y+z = 0.
Two solutions exist.
One is to try every combination of signs for x, y and z and checking if it satisfies above relation at any time. It may take 8 (2^3) iterations in the worst case.
Other is to notice that the two values other than largest have to be assigned the same direction, while the largest value will be assigned opposite direction, to get sum 0.
See, if we assign a value other than largest value, same sign as largest, we can never get the sum 0 by assigning whichever sign to the third element. So, assign smaller two elements one direction, and largest value opposite direction and print Yes if the sum is 0. Otherwise, print No.
Time Complexity
Time complexity is O(1) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 