BRKSTICK - 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 N sticks, the i-th has length A_i.
You can take a stick of length X and break it into two sticks of lengths Y and Z, as long as Y+Z = X and both Y, Z are positive integers.

Find the maximum number of breaks you can perform.

EXPLANATION:

First, note that any stick of length \gt 1 can be broken: if it has length X, it can be broken into lengths 1 and X-1, for example.

Now, we make the following observations:

  1. Each break operation doesn’t change the total length of sticks available to us.
  2. Each break operation increases the number of sticks by 1.

So, we’ll only be unable to break any more sticks when every stick has length 1.
Since the total length doesn’t change, this means we’ll have

A_1 + A_2 + \ldots + A_N

sticks of length 1 in the end.

We started with N sticks, and each break increases the count by 1.
So, the number of breaks simply equals

\left( A_1 + A_2 + \ldots + A_N \right) - N

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(sum(a) - n)