PROBLEM LINK:Author: Andrii Mostovyi 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 Subtask 2 and 3 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 $Mi1$. 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 $Mi1$ or more than $Mi1$. In the former case, the answer is $Mi1$. In the latter case, it is $Mi$ because the $i^{th}$ chain will have to be attached in the end too. COMPLEXITY:$\mathcal{O}(M \log M)$ per test case. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 31 Aug '15, 23:57

Using qsort() gave me TLE, used CountSort and got it AC'ed : https://www.codechef.com/viewsolution/8095743 answered 14 Sep '15, 17:17
qsort is n*n in worst case. This suggest that the test cases were set nicely.
(14 Sep '15, 23:13)
i used the qsort from c library, i don't think it's worst case running time is n*n as the standard does not specify the implementation. The point is, any nlogn sort was making the solution slow :)
(15 Sep '15, 17:48)

How is subtask 1's answer m1? suppose there are 5 donut chains of size 1, we can join them using 2 donuts. one can join two of them forming a three chains of size 1 1 and 3. Then another 1 can join the chain of size 1 and 3 forming a single chain of size 5. So answer will be floor(m/2). Correct me if I am wrong. answered 14 Sep '15, 15:27

This problem was nice. It was not obvious for me that totally breaking a chain may turn to be useful. Maybe the editorial could give an example, for instance with 2,3,5,6, which can be achieved by breaking the first chain only. answered 15 Sep '15, 00:19

I think, the answer to the subtask 1 is $\lfloor{\frac{M}{2}}\rfloor$ answered 14 Sep '15, 15:46

Here is my solution. A bit modified algorithm as the editorial. https://www.codechef.com/viewsolution/8000147 answered 14 Sep '15, 21:49

waht is "O(MlogM) per test case" i am not able to understand it. answered 15 Sep '15, 13:55
@h4cktivist It means for every test case it will take o(MlogM), what you didn't understand.
(04 Jan '16, 08:32)

for sorted array a[m] we can have two pointers at the start and end and move them like this :
answered 15 Sep '15, 19:15

a simple approach :) https://www.codechef.com/viewsolution/8117190 answered 15 Sep '15, 20:59

The question can be solved without sorting or using any fast input/output,as 1 ≤ Ai ≤ 10^5. check this video tutorial for the explaination : https://www.youtube.com/watch?v=TAQeGo4GVHg answered 16 Sep '15, 12:05

The editorial consists of many typos. Can someone explain the logic used here in this part?
How does looping through the condition (sum < M) gives no of single doughnuts to join all the chains? answered 19 Sep '15, 01:37

Why do i get TLE?? answered 25 Sep '15, 18:28

Could anybody tell me what is the issue with my solution https://www.codechef.com/viewsolution/8055624. It might be something stupid as I am new to submitting on CodeChef. Please Help. answered 10 Oct '15, 15:14

in case of tle use scanf instead of cin and the problem is solved answered 08 Sep '16, 11:54

sir , I have a query regarding this code i submitted and i am getting subtask 2 and 3 are not correct but i tested it with the other case other than subtask 1 and getting the right result please verify my code: #include<stdio.h> #include<iostream>
answered 14 Sep '15, 20:07

@pushkarmishra In what order(increasing/decreasing) should I sort them.