ADADISH - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author & Editorialist: Alei Reyes
Tester: Istvan Nagy

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

Chef Ada is preparing N dishes (numbered 1 through N), the i-the dish requires a cooking time of C_i seconds.

Ada has a kitchen with two identical burners. To cook the i-th dish, she puts it in one of the burners, waits for C_i seconds, and then removes it from the burner. The dishes can be prepared in any order. Two dishes can be cooked simultaneously, however no two dishes can be in the same burner at the same time. When a dish is in a burner, it can’t be removed before it is completely cooked.

What is the minimum time to prepare all dishes?

QUICK EXPLANATION:

Brute force all possible ways of assigning each dish to a burner.

EXPLANATION:

The dishes will be splitted between the two burners. Let L be the sum of cooking times of all the dishes cooked in the first burner, similarly let R be the sum of cooking times of the second burner. The total time required to cook all dishes is T=min(L,R). If we denote by S the sum of cooking times of all dishes, then L+R=S and therefore T=min(L,S-L)

There are three possible ways of splitting the dishes, we can try all possibilities:

  • all dishes are cooked in only one burner, this optimal when there is only one dish!
  • one dish is cooked in the first burner (let’s say dish i), and the rest in the second burner. The cooking time is min(C_i,S-C_i).
  • each burner cooks two dishes, let’s say dishes i and j are cooked in the first burner. The cooking time is min(C_i+C_j, S-(C_i+C_j))

SOLUTIONS:

Setter's Solution, first subtask
for _ in range(input()):
    n = input()
    c = map(int, raw_input().split())
    s = sum(c)
    print ((n+1)/2)*c[0]
Setter's Solution, full score
for _ in range(input()):
    n = input()
    c = map(int, raw_input().split(" "))
    s = sum(c)
    ans = s
    for x in c: 
        ans = min(ans, max(x, s-x))
    for i in range(n):
        for j in range(i+1,n):
            x = c[i] + c[j]
            ans = min(ans, max(x, s-x))
    print ans
Tester's Solution (C++)
int main(int argc, char** argv)
{
  int T;
  cin >> T;
  forn(i, T)
  {
    int N, csum = 0, best = 1000;
    cin >> N;
    vector<int> C(N);
    for (auto& ci : C)
    {
      cin >> ci;
      csum += ci;
    }
 
    for (int j = 0; j < (1 << N); ++j)
    {
      int su = 0;
      for (int k = 0; k < N; ++k)
      {
        if ((1 << k) & j)
          su += C[k];
      }
      best = min(best, max(su, csum - su));
    }
    cout << best << endl;
  }
  return 0;
}

VIDEO EDITORIAL (Hindi):

VIDEO EDITORIAL (English):

3 Likes

you guys held a great contest(especially for long) , great questions, fast editorials,
thanks

3 Likes

great contest :slight_smile:

Bonus-Try to solve this problem for n<1000, sum of all elements is less than 1000.

The video editorial solution will end up with a wrong answer for the testcase of : 3 3 2 2 2.
The correct answer to this problem is 6 whereas the greedy solution will return 7. Did I misunderstand something or is the official solution really wrong. The constraints seem to point out that it was meant to be a brute force problem(dp optimization might be possible). Please correct me if I misunderstood the solution.

Something is wrong with Codechefs Java and Kotlin checker it gave me WA whereas the same code in C++ gave AC please fix ASAP!

1 Like

n<=4

I just read the slide of the summary in the video editorial (19:35). Surprisingly assigning each dish to the least busy burner works for the given constraints (why?). In general the problem is NP.

Is 23 minutes for the cakewalk too long? google says that most anime episodes lasts for 24 minutes!

1 Like

why is this code giving WA for original constraints section
while(t–)
{
int n,m=0;
cin>>n;
int a[4];
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n,greater());
if(n==4)
{
if(a[0]>=(a[1]+a[2]+a[3]))
m=a[0];
else
m=max(a[0]+a[3],a[1]+a[2]);
}
else if(n==3)
{
if(a[0]>=(a[1]+a[2]))
m=a[0];
else
m=max(a[0],a[1]+a[2]);
}
else if(n==2)
m=a[0];
else
m=a[0];
cout<<m<<"\n";
}

1 Like

I have a question, CodeChef allows video editorialist to solve and submit the problem of which they are in charged ,when the contest is live ?

@justin_foley The editorial is published after the contest gets over. Not when it is live.

I’m aware of this fact , but this is the profile of video editorialist of this problem and she solved the question when the contest was live .

I believe that what made this problem easy was the fact that 1 \leq N \leq 4
Because then you can bash through each case.

The idea in this problem was that given a array of N numbers , you have to divide it into 2 subarrays, such that the sums of elements of each of these arrays are nearly equal. In set notation, this means dividing set A into 2 sets B, C such that |S(B) -S(C)|(S(X) \text{~refers to the sum of elements of~}X), is minimised.

I did not bash case. Instead I used dp to solve problem for general N.(Like this made the bound 1 \leq N \leq 4 irrelevant to me.)
Now I realise that it would probably have been better, if I had bashed case instead. Because that would have saved typing a lot of code and also helped in getting AC faster. But since It is a 10 day long challenge, I don’t think it matters. :sweat_smile: :sweat_smile:

3 Likes

@justin_foley Ohhh… Thats right buddy. They can solve when its live because just after the contest gets over they are told to publish immediately. Thats what i believe.

can you explain how it is 6, not 7?

hindustani:on burner-1:-3+3;on burner-2:-2+2+2
can you please let me know which test case it is failing
https://www.codechef.com/viewsolution/39580547

1 Like

cook your dish here----->> can anyone tell where my code is wrong…(which test cases it doesn’t satisfy)

for _ in range(int(input())):
n=int(input())
c=list(map(int,input().split(" ")))
c.sort(reverse=True)

print©

if n==1:
    print(c[0])
elif n==2:
    print(max(c))
elif n==3:

z=c.sort(reverse=True)

    if c[0]>=(c[1]+c[2]):
        print(c[0])
    else:
        print(c[1]+c[2])
else:

z=c.sort(reverse=True)

    if c[0]>=(c[1]+c[2]+c[3]):
        print(c[0])
    else:
        print(max((c[0]+c[3]),(c[1]+c[2])))

Hi, i am also using same logic in python, still getting wrong answer.
Any clue where this logic fails???

@hindustani consider assigning dishes 1 and 2 with 3 minutes each to burner 1 and dishes 3,4,5 with 2 minutes each to burner 2. So the correct answer is 6 for the testcase : 3 3 2 2 2. For n>4 greedy approach does not work.

2 Likes

yes same here