CHEFTMA - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra

DIFFICULTY:

Simple

PREREQUISITES:

Greedy, In-built data structures

PROBLEM:

EXPLANATION:

Subtask 1
Given constraints are very small. Thus, a brute force solution can easily work. Trying all possible buttons in all possible ways and noting the minimum over all such arrangements gives the answer. The total complexity of this approach is \mathcal{O}(2^N*2^M*2^K). This will pass under the given constraints.

Subtask 2
There are many observations to make here which reduce this problem substantially:

  • For the given A[i] and B[i] values, we are only interested in the value A[i]-B[i]. Basically, we can modify each A[i] to A[i]-B[i]. From this point onwards in this editorial, array A is assumed to be containing the modified values, i.e., A[i]-B[i].

  • The black and white buttons fundamentally do the same things when dealing with the modified values of the array A. Thus, we put all the values from the two arrays, C and D, in a common multiset called buttons. A multiset is a set which allows duplicates to exist.

Now, before we go on to the formal algorithm, let’s think of a smaller problem. Let’s take two values from the array A (just reminding, the values aren’t the ones which were taken as input) A[i] and A[j]. Let’s assume that A[j] > A[i]. Now, let us take two values x and y from the buttons multiset. Let’s say that x < y < A[j]. Which button should be use for A[j] then. Intuition tells us that it is beneficial to use y. This is for two reasons. First one is that using y allows us to complete more number of tasks on the j^{th} day than x using why would. Second reason is that assume y > A[i] and x < A[i]. If we use x on A[j], we won’t be able to use y on A[i]. A better strategy is to use x on A[i] and y on A[j]. What if both x and y were less than A[i]. Then we could use either of buttons on A[i] and the other on A[j]. This is because we will anyway be reducing the same number of tasks from the sum of total incomplete tasks.

This gives us our greedy algorithm: for a particular value A[i], use the button x such that x hasn’t been used up till now and x is the largest value less than or equal to A[i] in the buttons multiset. Now, the incomplete tasks left will be A[i] - x. Add this to the accumulator variable which is to be finally returned as the answer. x is removed from the multiset since one button can’t be used twice. The proof of this greedy algorithm has been given above and can be more formally stated as “Exchange Argument”. You can find more about proofs of greedy algorithms here.

The multiset data structure can be found in almost all the major programming langauges. Writing one on your own requires knowledge of balanced binary search trees. All operations in a multiset are in order \mathcal{O}(\log N).

The editorialist’s program follows the editorial. Please see for implementation details.

OPTIMAL COMPLEXITY:

\mathcal{O}(N\log N) per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

3 Likes
2

NO requirement of any data structures like multiset or balanced binary trees. Just an algorithm, also called “2-pointer algorithm” which reduces the complexity from O(n^2) to O(n). Here is a link to a tutorial on 2-pointer algorithm (link).

First just sort the initial difference array in descending order and find the most suitable candidate for it in the buttons array using binary search or just linear search as well. Then using 2 pointer concept, iterate over the buttons and difference array. Here is a link to my AC solution.

Another problem on 2 pointer concept is Codeforces problem

1 Like
3

Implemented the same O(nlogn) solution as in the editorial.


[1]


  [1]: https://www.codechef.com/viewsolution/9064386 "Code"
4

short editorial on 4 easy problems: Codechef Jan’16 challenge – Discussion Forum

5

An easy solution can be:

  1. Store difference if a[i]-b[i] in one array (named diff) , sorted in descending order.

  2. Store all buttons in one array sorted in descending order of their value x.

  3. Iterate over the array diff, get the biggest button that is smaller than or equal to diff[i].

  4. Use this button to lessen diff[i] to 0 or a smaller integer.

  5. Store this value in incomplete tasks variable.

  6. Repeat steps 3-5 for other elements in diff.

Here is the link to my solution

2 Likes
6

Seriously? Optimal complexity is suggested to be O(NlgN) ? It can be solved in O(N) without any complex data-structure but just arrays.

Sorry, even my solution was O(NlgN) :frowning:

7

I think you sorted it. That’s O(nlogn).
And yes arrays are way easier

8

Yes array does it. But you do need to sort it. Can you do this in O(n)?

1 Like
9

Used a simple approach, got AC!,
use test case like:
4 2 3 (denoting N,K,M respectively)
4 2 6 9
2 4 2 1
1 4 5
7 8
/*
*
*/
for reference refer to code:

#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int T;
cin>>T;

while(T--)
{
    llint n,k,m,i;

    cin>>n>>k>>m;

    llint a[n],c[n],h[k+m];

    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
        cin>>c[i];

        llint W[k],B[m];
    for(i=0;i<k;i++)
    {cin>>W[i];
        h[i]=W[i];
    }

    for(i=0;i<m;i++)
        {cin>>B[i];
            h[k+i]=B[i];
        }

sort(h,h+k+m,greater());
llint d[n];

    for(i=0;i<n;i++)
        d[i]=abs(a[i]-c[i]);
    
    sort(d,d+n,greater<int>());

    llint j=0,l=0;

        llint maxi1=0,s=0,s1=0;

for(i=0;i<n;i++)
{
s+=d[i];

}
i=0;j=0;
while(i<k+m && j<n)
{
if(h[i]<=d[j])
{s1+=h[i];
i++;
j++;
}
else i++;

}
llint X=s-s1;

        cout<<X<<'\n';
}

}

1 Like
10

Your test case should give answer as -1 not 4, and your test case format needs correction. But your test case actually helped to find bug in my code. Your contribution means a lot to programmers like us.
Happy Coding!!!

1 Like
11

Thanks for suggestion, i have corrected and followed the strict space separated format.

12

Regarding the answer, i found out that these test case gives different answers for different codes. I think it is not covered in test cases.

13

Can anyone review this code: CodeChef: Practical coding for everyone

I am getting runtime error for task 2 but all other tasks have been cleared