Problem Selection

Easy

0/40

Average time to solve is 30m

Contributed by

12 upvotes

Asked in company

Problem statement

This is your last test before the summer break. You had prepared for the test, but this time your teacher has prepared something special for you, he gave you ‘N’ problems and an array ‘A’ of length ‘N’, where each problem gives you A[i] marks if you answer it. The teacher has given some constraints on how you can answer the question. Every time you answer a question, he will block ‘K’ questions of your choice that has not been answered or blocked yet. If you have fewer than ‘K’ questions, he will block all the questions. Once a question is blocked, you can not answer it. Since you prepared last night, you know the answers to all the problems. Now you are wondering what’s the minimum and maximum marks you can achieve in the test.

Note: You cannot leave the test until all the questions are either answered or blocked. You will never answer a question incorrectly.

Detailed explanation ( Input/output format, Notes, Images )

Input Format-

First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains two integers, ‘N’ and ‘K’.
The following line contains the array ‘A’ of the length ‘N’, denoting the marks you will get to answer the problems.

Output Format-

For each test case, You have to print two space-separated integers denoting the minimum and maximum marks that you can achieve in the test.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints -

1 <= ‘T’ <= 5
1 <= ‘N’ <= 10^5
0 <= ‘K’ <= ‘N - 1’ 
1 <= A[i] <= 10^5, i ∈  (1,N) 


Time Limit: 1 sec

Sample Input-1

Sample Output-1

3 7
1 5

Explanation for Sample Input 1:

For test case 1:
    For the minimum:
        We first solved the second problem and got ‘2’ marks, then we selected problem numbers ‘1’ and ‘4’ to be blocked. After that, we answered the third problem and got a ‘1’ mark making a total of ‘3’ marks.
    For the maximum:
        We first solved the fourth problem and got ‘4’ marks, then we selected problem numbers ‘2’ and ‘3’ to be blocked. After that, we answered the first problem and got ‘3’ marks making a total of ‘7’ marks.

Sample Input -2

Sample Output -2

4 4
1 2

Hint 1

How many questions do you have to answer?

Approaches (1)

Approach 1

Greedy

Approach: we have to answer exactly ceil(N / (K + 1)) questions. So, if we want to maximize the total marks, we will select ceil(N / (K + 1)) largest elements from the Array. If we have to minimize the total marks, we will select ceil(N / (K + 1)) smallest elements from the Array.

Algorithm:

Create two variables, ‘minAns’, ‘maxAns’, and initialize them to ‘0’.
Create a variable ‘req’ and initialize it to ceil(N / (K + 1)).
Sort A.
Iterate using a for loop from i = ‘0’ to ‘req’.
- Update ‘minAns’ to minAns + A[i].
- Update ‘maxAns’ to maxAns + A[N - i - 1].
Print ‘minAns’, ‘maxAns’.

Time Complexity

O(N * log(N)), where N is the size of the array.

We are sorting the array ‘A’. Hence the overall complexity is O(N * log(N)).

Space Complexity

O(1).

We are creating three variables. Hence the overall complexity is O(1).

(100% EXP penalty)

Problem Selection

Console