DUMBLEDORE - Editorial

Problem Link - Alice Potter And Dumbledore Army

Problem Statement

Dumbledore’s Army consists of N members. Alice Potter is planning to hold M Dumbledore’s Army sessions, where the members will perform training tasks to improve their skills in Defense Against the Dark Arts.

Initially, each member of the Army has no tasks. Before the i-th training session, Alice gives the P_i-th participant a task that he can complete in T_i seconds. And each subsequent session Alice will add more and more difficult tasks, i.e. T_i \le T_{i+1}.

Let’s assume that by the i-th session, the j-th participant has accumulated C_j tasks. Alice knows that sometimes there is not enough time to complete all the tasks in a single session, so instead of forcing them to complete all C_1+C_2+\ldots+C_N tasks, she can allow them to complete only a certain number k of them. In this case, each participant can choose a subset of their tasks (in total, they have to choose k tasks) and perform only those tasks. Each participant performs his tasks sequentially and spends time equal to the sum of the times of his tasks. However, different participants can perform tasks in parallel, so the total time of the session is equal to the maximum of the times of each participant. We denote the minimum possible value of this time by ans_{i, k}.

In order to optimally train participants, for each session i Alice needs to know the value of ans_{i, 1} + ans_{i, 2} + \ldots + ans_{i, i}. Help Alice — calculate these sums for her.

Approach

To solve this problem, we maintain a running total of tasks for each participant in an array, sum. This array keeps track of the cumulative time required by each participant based on their tasks. With each new session, Alice assigns tasks to a participant, increasing their accumulated time by the task duration for that session.

The approach is to maintain a sum array where each index represents a participant’s accumulated task time. For each session, we read the participant index p and the task time t. We then update the cumulative task time for participant p by adding t to sum[p]. After updating, we calculate the total cumulative time of all participants by summing up all values in sum. This total represents the minimum training time required for that session under Alice’s conditions.

Time Complexity

The solution processes each session in fixed steps, so the time complexity is O(M).

Space Complexity

An array of size N is used for participants’ task times, giving a space complexity of O(N).