DONUTS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

2

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.

1 Like
3

I think, the answer to the subtask 1 is \lfloor{\frac{M}{2}}\rfloor

4

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.

5

Using qsort() gave me TLE, used CountSort and got it AC’ed :
https://www.codechef.com/viewsolution/8095743

2 Likes
6

corrected.

7

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

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<m;i++)
			{
				scanf("%d",&a);
				if(a==1)
				y++;
				else if(a==0)
				x--;
			}
	
			if(y<x/2)
			{
			tot[s]=x-1-y;
			s++;
			    
			}
			else if(y>=x/2)
			{
			tot[s]=x/2;
			s++;
			}
		}
};
 
int main()
{
	int t;
	
	scanf("%d",&t);
	for(int qw=0;qw<t;qw++)
	{
		doug obj[qw];
		obj[qw].create();
	
	}
		for(int qw=0;qw<t;qw++)
	{
		printf("%d\n",tot[qw]);
		
	}
	return 0;
}
8

Here is my solution. A bit modified algorithm as the editorial.
https://www.codechef.com/viewsolution/8000147

9

qsort is n*n in worst case. This suggest that the test cases were set nicely.

10

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.

1 Like
11

waht is “O(MlogM) per test case” i am not able to understand it.

12

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 :slight_smile:

13

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<l){
            while(f<l&&a[f]==0){f++;}
            if(f>=m||f==l){break;}
            a[f]--;
            l--;
            count++;
        }
14

a simple approach :slight_smile:
https://www.codechef.com/viewsolution/8117190

15

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 :

16

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?

17

Why do i get TLE??

https://www.codechef.com/viewsolution/8244582

18

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.

19

@h4cktivist
It means for every test case it will take o(MlogM), what you didn’t understand.

20

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