×

# IPCTRAIN - Editorial

Primary Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah

Easy

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 ith trainer arrives on day Di and then stays till the end of the camp. He also wants to teach exactly Ti lectures. For each lecture that a trainer was not able to teach,his sadness level will be increased by Si. 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 ith trainer couldn't teach by remi 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

This question is marked "community wiki".

1181134
accept rate: 0%

 8 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. answered 17 Jul '17, 15:30 15.5k●1●20●66 accept rate: 18% 2 Solution : Great! Comments : Extraordinary :D (17 Jul '17, 15:38) Lol XD. It just came into my mind when i read "A trainer who comes to the camp stays there till end of camp" :p (17 Jul '17, 15:40)
 2 I have used Segment Trees answered 17 Jul '17, 16:52 51●1 accept rate: 0%
 1 @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;  answered 18 Jul '17, 09:05 21●1 accept rate: 0%
 1 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. answered 20 Jul '17, 20:47 2★aseem_cu 11●1 accept rate: 0%
 0 solutions are not available yet!! answered 17 Jul '17, 15:20 21●6 accept rate: 0%
 0 community - need help to understand what is missing https://www.codechef.com/viewsolution/14559868. only 40 pts answered 17 Jul '17, 18:58 21●1 accept rate: 0%
 0 Can anyone explain where I went wrong? 40 pts. https://www.codechef.com/viewsolution/14561290 answered 17 Jul '17, 21:26 2★lord_ozb 31●3 accept rate: 0%
 0 Hi! The link to practice and main contest are incorrect. Please update. answered 18 Jul '17, 08:32 1 accept rate: 0%
 0 can anyone explain why i m getting WA for last 2 subtask. https://www.codechef.com/viewsolution/14601668 answered 18 Jul '17, 09:05 1 accept rate: 0%
 0 inside practice, contest link is given while in contest, practice session link is given, plz interchange those at top of editorial answered 18 Jul '17, 17:15 533●1●12 accept rate: 3%
 0 I solved it using set https://www.codechef.com/viewsolution/14578928 answered 18 Jul '17, 17:57 76●2 accept rate: 6%
 0 practice link is not working..please fix this.... answered 18 Jul '17, 18:24 15●4 accept rate: 0%
 0 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? answered 18 Jul '17, 19:37 1 accept rate: 0% use c++ Priority Queue (19 Jul '17, 01:28)
 0 Links to practice and competition are backwards. answered 19 Jul '17, 03:18 1●2 accept rate: 0%
 0 I guess I had gone mad because I couldn't think of such a simple solution. So I did this using segment trees. O(nlog(n)log(n)) https://www.codechef.com/viewsolution/14497188 answered 19 Jul '17, 18:25 0 accept rate: 0%
 0 Links for all tutorials of July long challange for practice and contest seem to be swapped. Please consider correcting them . answered 25 Jul '17, 04:14 3★aman935 120●1 accept rate: 0%
 0 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 answered 08 Dec '17, 17:47 1●1 accept rate: 0% Your code into infinite loop for cases like this- 1 3 6 2 2 300 1 1 1000 2 2 300 (08 Dec '17, 19:23)
 0 please explain how to implement priority queue here?? i am not able to understand plz tell @vijju123 answered 30 Jan '18, 00:51 12●2 accept rate: 0%
 0 Need help! My solution is passing Subtask 1 completely but it fails Subtask 2 completely. Can anyone please help me figure it out where am i doing wrong? Here is my link to solution. https://www.codechef.com/viewplaintext/18941549 answered 24 Jun '18, 22:07 1 accept rate: 0%
 0 My solution is also failing for Subtask 2 don't know why. Though the logic is same as explained in editorial. https://www.codechef.com/viewsolution/19193154 answered 13 Jul '18, 01:18 0★sgrpwr 1●1 accept rate: 0% long sadness = 0; for(Teacher t: remaining) { sadness += t.lectures*t.sadness; Declare t.sadness as long instead of int or use type casting as sadness+=1LL * t.lectures * t.sadness; - because product of 2 int is stored in the int type and then the overflowed result is stored in sadness. (13 Jul '18, 10:10)
 0 Could someone please tell me why I'm a getting WA https://www.codechef.com/viewsolution/20412633 answered 10 Oct '18, 10:20 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,851
×3,820
×1,024
×279
×229
×138
×34

question asked: 15 Jul '17, 07:23

question was seen: 6,579 times

last updated: 10 Oct '18, 10:20