DONUTS - Editorial

editorial
, , , ,
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

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;
}
7

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

8

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.

3 Likes
9

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

10

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++;
        }
11

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

2 Likes
12

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 :

13

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?

14

Why do i get TLE??

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

15

Could anybody tell me what is the issue with my solution CodeChef: Practical coding for everyone.
It might be something stupid as I am new to submitting on CodeChef.
Please Help.

16

in case of tle use scanf instead of cin and the problem is solved

17

getting TLE for task# 4 . Used counting sort but still it gives TLE.
Here’s the link : link

18

corrected.

19

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

20

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:

21

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

22

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

23

greater than m-i-1?? how did u know “m-i-1” would give the answer?