MAKETRIANGLE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have three numbers X, Y, Z.
In one move, you can increase any one of them by 1.
Find the minimum number of moves needed to make the three values be the sides of a non-degenerate triangle.

EXPLANATION:

Without loss of generality, let the order of the values be X \le Y \le Z.

According to the triangle inequality, these values can be the sides of a non-degenerate triangle if and only if:

  • The sum of any two of the values is strictly larger than the third one.

Because Z is the largest one, we have X+Z \gt Y and Y+Z \gt X for free.
So, we only need to ensure that X+Y \gt Z is true.

If this inequality is true, then no operations are needed and the answer is 0.

Otherwise, we have X+Y \le Z.
In one move, we can increment one value by 1. This means (X+Y) can also increase by only 1.
It’s optimal to make X+Y reach Z+1 (which is doable by, for example, always incrementing Y.)
So, the number of moves needed is (Z+1) - (X+Y).

To deal with the general case (where it’s not necessary that X\le Y\le Z), note that we care about two quantities:

  1. The largest value among X, Y, Z.
  2. The sum of the other two values.

So, let S = X+Y+Z - \max(X, Y, Z) and M = \max(X, Y, Z).
Then,

  • If S \gt M, the answer is 0.
  • Otherwise, the answer is (M+1-S).

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y, z = map(int, input().split())
    
    mx = max(x, y, z)
    sm = x + y + z - mx
    if sm > mx: print(0)
    else: print(mx+1 - sm)