### PROBLEM LINK:

**Author:** Andrii Mostovyi

**Tester:** Kevin Atienza

**Editorialists:** Pushkar Mishra and Suhash Venkatesh

### DIFFICULTY:

Easy

### PREREQUISITES:

Sorting, Greedy

### PROBLEM:

Given chains of doughnuts of different lengths, we need to join them to form a single chain. Two chains can be joined by cutting a doughnut into two and using it to clip the chains together. We need to minimize the number of cuts needed to form a single chain consisting of all the N doughnuts.

### EXPLANATION:

**Subtask 1**

Since all the chains are of length 1, we can simply take them one by one and attach to form larger chain. Thus, the answer each time is \lfloor\frac{M}{2}\rfloor.

**Subtask 2 and 3**

We can observe that a single doughnut is capable of joining two chains of lengths l_1 and l_2 in one cut to form a chain of length l_1 + l_2 + 1. This hints towards a greedy solution. We need to decide the number of single doughnuts we need in order to join all the chains together. It can be noted that it is best to join longer chains together. For example, consider the case when we have chains of lengths 1, 2, 3. It is best to join chains of lengths 2 and 3 with the help of the unit-length chain. Any other order of joining doesn’t yield an optimal result.

Thus, we begin by sorting the chains by their lengths. Next, we iterate from i = 1 to M. We stop at that i where cumulative sum of chain lengths from 1 to i becomes greater than M-i-1. This is the point where we have the sufficient number of single doughnuts to join all chains. As a last step, we need to check whether cumulative sum up to i is exactly equal to M-i-1 or more than M-i-1. In the former case, the answer is M-i-1. In the latter case, it is M-i because the i^{th} chain will have to be attached in the end too.

### COMPLEXITY:

\mathcal{O}(M \log M) per test case.