KDELI - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author, Tester, and Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sorting

PROBLEM:

K people line up to buy N pastries from a shop. You’re L-th in line.
The pastries have deliciousness values A_1, A_2, \ldots, A_N.

On their turn, a person will always pick the most delicious remaining pastry; then move to the back of the line.
Find the total deliciousness of pastries you buy.

EXPLANATION:

Let’s sort the array A, so that A_1 \geq A_2 \geq \ldots \geq A_N.
Then, notice that:

  • The first person will choose A_1
  • The second person will choose A_2
  • The third person will choose A_3
    \vdots
  • The K-th person will choose A_K
  • Then, it’s the first person’s turn again, who will pick A_{K+1}
  • The second person gets another turn, and picks A_{K+2}
    \vdots

In general, the i-th person in line will pick A_i, A_{i+K}, A_{i+2K}, \ldots.
You’re L-th in line, so you’ll pick A_L, A_{L+K}, A_{L+2K}, \ldots
Simply print the sum of these numbers.

Since N can be as large as 2\cdot 10^5 in this task, sorting A needs to be done in \mathcal{O}(N\log N) using an efficient algorithm, such as mergesort or quicksort; \mathcal{O}(N^2) sort algorithms such as bubble sort and insertion sort won’t be fast enough.
The simplest way is to just use your language’s built-in sort function.

TIME COMPLEXITY

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, k, l = map(int, input().split())
    a = sorted(list(map(int, input().split())))[::-1]
    print(sum(a[l-1::k]))
1 Like