THREEFR - EDITORIAL

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.

  1. a = b+x
  2. b = c+y
  3. 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. :slight_smile:

4 Likes

Lets take A B C as money each of three friend have
then from the question we can write:-
A = x + B B = y + C C= z + A
After solving we get an equation
x + y + z = 0

This equation can only hold true when
either
x= -( y + z )
y= -( z + x )
z= -( x + y )

And its given we can take anyone negative
So we can check

If(x= ( y + z ) || y= ( z + x ) || z= ( x + y ) ) then we print yes
otherwise false

Here is my Solution
https://www.codechef.com/viewsolution/45343406

HAPPY CODING!!!

2 Likes

2*(max(x,y,z))-(x+y+z) = 0
https://www.codechef.com/viewsolution/53326185

how do we know that x and y have same sign in the solution video?