### PROBLEM LINK:

Practice

Contest

**Author:** Admin2

**Primary Tester:** Misha Chorniy

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Easy

### PREREQUISITES:

Greedy,Heap

### PROBLEM:

You have an upcoming camp. There are N trainers. The camp runs for **D** days.Each day,there can be at most one lecture. The **i**^{th} trainer arrives on day **D**_{i} and then stays till the end of the camp. He also wants to teach exactly **T**_{i} lectures. For each lecture that a trainer was not able to teach,his sadness level will be increased by **S**_{i}.

You are the main organizer of the contest. You want to find minimum total sadness of the trainers.

### EXPLANATION:

Letâ€™s assign our trainers starting from the first day of the camp. At each day adding arriving trainers to our set of trainers.

Each day should be assigned to only **one** trainer, itâ€™s obvious that we should assign the trainer with maximum sadness to this lecture, so our set (container) should be a heap sorting trainers by their sadness value. In fact we should know also the number of days each lecturer wants to serve in, so we take the lecturer with maximum sadness from our heap and decrease his demand by 1. In case he still has lectures he would like to do, we keep him in the heap, otherwise we just pop him out.

After finishing all days, some teachers may have some remaining lectures they wanted to teach but we couldnâ€™t find such days for them. Letâ€™s denote the number of lectures the **i**^{th} trainer couldnâ€™t teach by **rem**_{i} So our answer would be :

answer = \sum_{i=1}^{i=N} rem_i * S_i

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

**AUTHORâ€™s solution**: Will be found here

**TESTERâ€™s solution**: Will be found here

**EDITORIALISTâ€™s solution**: Will be found here

4 Likes

solutions are not available yet!!

1 Like

@admin The links to the solution are not working! Please check it.

This question literally screamed â€śPRIORITY QUEUEâ€ť in my ears. One of the good questions which can be solved with knowledge of proper data type!!

Honestly, i saw priority queue code for first time in â€śCooking Scheduleâ€ť editorial (one of the answers told that â€śit can also be solved using priority queueâ€ť) and it made life so simple for me here.

My code- https://www.codechef.com/viewsolution/14436208

14 Likes

community - need help to understand what is missing https://www.codechef.com/viewsolution/14559868. only 40 pts

Can anyone explain where I went wrong? 40 pts.

https://www.codechef.com/viewsolution/14561290

Hi!

The link to practice and main contest are incorrect. Please update.

can anyone explain why i m getting WA for last 2 subtask.

https://www.codechef.com/viewsolution/14601668

@lord_ozb:

You have used a double loop here which caused the time to exceed the limit.

```
for(int i = 0; i < d; i++){
int x = -1;
int max = Integer.MIN_VALUE;
for(int j = 0; j <= i; j++){
if(queue[j].size() != 0){
Trainer temp = queue[j].peek();
if(temp.sad > max){
max = temp.sad;
x = j;
```

1 Like

**inside practice, contest link is given while in contest, practice session link is given, plz interchange those at top of editorial**

practice link is not workingâ€¦please fix thisâ€¦

If I solve the above question using heaps as stated, then on popping out the trainer which doesnâ€™t have any lecture remaining and at the very same time maintaining the sort would require the complexity O(n).

On the other hand if we just extract him from the heap and heapify using time complexity O(lg n) would disturb the sort. How do i proceed?

Links to practice and competition are backwards.

I guess I had gone mad because I couldnâ€™t think of such a simple solution. So I did this using segment trees.

O(n*log(n)*log(n))

https://www.codechef.com/viewsolution/14497188

Can anyone help me? Author solution I seem that complexity O(N*T).Here N=100000 and T=100000 according to Constraints.How itâ€™s passed all test case.May be something i miss.Thanks in advance.

1 Like

Links for all tutorials of July long challange for practice and contest seem to be swapped. Please consider correcting them .

Could someone please tell me why Iâ€™m a getting a TLE in my solution. Iâ€™ve used priority queue.

https://www.codechef.com/viewsolution/16505429

please explain how to implement priority queue here?? i am not able to understand plz tell @vijju123

1 Like