You are not logged in. Please login at www.codechef.com to post your questions!

×

DONUTS - Editorial

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

This question is marked "community wiki".

asked 31 Aug '15, 23:57

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156481
accept rate: 4%

edited 14 Sep '15, 20:40

rarora777's gravatar image

2★rarora777 ♦
11

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

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

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

link

answered 14 Sep '15, 17:17

xariniov9's gravatar image

6★xariniov9
1.1k18
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) xariniov96★

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.

link

answered 14 Sep '15, 15:27

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

corrected.

(14 Sep '15, 17:23) pushkarmishra4★

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.

link

answered 15 Sep '15, 00:19

beroul's gravatar image

5★beroul
1313
accept rate: 6%

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

link

answered 14 Sep '15, 15:46

anishshah's gravatar image

3★anishshah
11
accept rate: 0%

edited 14 Sep '15, 15:47

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

link

answered 14 Sep '15, 21:49

atulshanbhag's gravatar image

4★atulshanbhag
22629
accept rate: 9%

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

link

answered 15 Sep '15, 13:55

h4cktivist's gravatar image

3★h4cktivist
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★

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

answered 15 Sep '15, 19:15

rajanwaliya's gravatar image

2★rajanwaliya
1
accept rate: 0%

edited 15 Sep '15, 19:19

link

answered 15 Sep '15, 20:59

sumanyurosha's gravatar image

2★sumanyurosha
1
accept rate: 0%

edited 15 Sep '15, 21:01

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

link

answered 16 Sep '15, 12:05

ankit15's gravatar image

2★ankit15
412
accept rate: 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?

link

answered 19 Sep '15, 01:37

ash_code's gravatar image

3★ash_code
475114
accept rate: 15%

edited 19 Sep '15, 01:40

link

answered 25 Sep '15, 18:28

krishnakhowal's gravatar image

2★krishnakhowal
1
accept rate: 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.

link

answered 10 Oct '15, 15:14

d73_112b's gravatar image

1★d73_112b
1
accept rate: 0%

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

link

answered 08 Sep '16, 11:54

pramodc's gravatar image

4★pramodc
1
accept rate: 0%

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

link

answered 13 Sep '16, 10:08

mithil_levi's gravatar image

3★mithil_levi
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<stdio.h> #include<iostream>

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

answered 14 Sep '15, 20:07

nekkanti's gravatar image

1★nekkanti
-1
accept rate: 0%

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

link

answered 14 Sep '15, 15:53

archazey's gravatar image

6★archazey
572
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,477
×3,704
×973
×775
×158

question asked: 31 Aug '15, 23:57

question was seen: 6,183 times

last updated: 13 Sep '16, 10:08