×

# DONUTS - Editorial

Author: Andrii Mostovyi
Tester: Kevin Atienza
Editorialists: Pushkar Mishra and Suhash Venkatesh

Easy

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:

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$.

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.

# SAMPLE SOLUTIONS:

This question is marked "community wiki".

1.3k156581
accept rate: 4%

11

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

(04 Jan '16, 08:33) 1★

 4 Using qsort() gave me TLE, used CountSort and got it AC'ed : https://www.codechef.com/viewsolution/8095743 answered 14 Sep '15, 17:17 1.1k●1●8 accept rate: 10% qsort is n*n in worst case. This suggest that the test cases were set nicely. (14 Sep '15, 23:13) likecs6★ 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)
 1 How is subtask 1's answer m-1? 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 893●2●11●35 accept rate: 10% corrected. (14 Sep '15, 17:23)
 1 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 5★beroul 132●3 accept rate: 6%
 0 I think, the answer to the subtask 1 is $\lfloor{\frac{M}{2}}\rfloor$ answered 14 Sep '15, 15:46 1●1 accept rate: 0%
 0 Here is my solution. A bit modified algorithm as the editorial. https://www.codechef.com/viewsolution/8000147 answered 14 Sep '15, 21:49 226●2●9 accept rate: 9%
 0 waht is "O(MlogM) per test case" i am not able to understand it. answered 15 Sep '15, 13:55 1 accept rate: 0% @h4cktivist It means for every test case it will take o(MlogM), what you didn't understand. (04 Jan '16, 08:32) arpit7281★
 0 for sorted array a[m] we can have two pointers at the start and end and move them like this :  int f = 0; int l = m-1; int count=0; while (f=m||f==l){break;} a[f]--; l--; count++; }  answered 15 Sep '15, 19:15 1 accept rate: 0%
 0 a simple approach :-) https://www.codechef.com/viewsolution/8117190 answered 15 Sep '15, 20:59 1 accept rate: 0%
 0 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 2★ankit15 41●2 accept rate: 0%
 0 The editorial consists of many typos. Can someone explain the logic used here in this part? for (int i = 0; i < M; i++) { sum += (a[i] + 1); if (sum >= M) { ni = i; break; } }  How does looping through the condition (sum < M) gives no of single doughnuts to join all the chains? answered 19 Sep '15, 01:37 3★ash_code 475●1●14 accept rate: 15%
 0 Why do i get TLE?? https://www.codechef.com/viewsolution/8244582 answered 25 Sep '15, 18:28 1 accept rate: 0%
 0 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 1★d73_112b 1 accept rate: 0%
 0 in case of tle use scanf instead of cin and the problem is solved answered 08 Sep '16, 11:54 4★pramodc 1 accept rate: 0%
 0 getting TLE for task# 4 . Used counting sort but still it gives TLE. Here's the link : link answered 13 Sep '16, 10:08 1 accept rate: 0%
 -1 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 #include using namespace std; int tot[200],s=0; class doug { public: int m,n,i,y,a,x; void create() { y=0; scanf("%d",&n); scanf("%d",&m); x=m; for(i=0;i=x/2) { tot[s]=x/2; s++; } } }; int main() { int t; scanf("%d",&t); for(int qw=0;qw
 -2 Lol,the answer for first subtask is about m/2.Every step you connect 3 donuts and create 1 bigger chain.So every step you get rid of two donuts. answered 14 Sep '15, 15:53 6★archazey 57●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×1,024
×801
×158

question asked: 31 Aug '15, 23:57

question was seen: 6,260 times

last updated: 13 Sep '16, 10:08