×

Need help in solving problem ICPC Trainer DS Heaps

 1 This is a question of July long challenge 2017. I tried hard but i get tle in subtask #2. I know my algorithm is too slow.First i simply sort the array depending upon priority. But then i realized it will take O(NLOGN) time. But after seeing the editorial i find heap is most suitable. Then i studied heaps and find it will take less time. Since it will take O(n) time to build heap and for each time it will take O(logn) to max heapify. So it will be more better.But still i can't find the suitable way to assign the lectures to suitable day.I know the priority trainer will first be considered but i can't find the suitable way to allocate days to trainer.Its my first question on codechef forum hope i will get the answer of my question.The link to my solution is https://www.codechef.com/viewsolution/14522626 .Please let me know if u don't get the question. I have added //complicated comment from there after i need help. Thank YOU. This question is marked "community wiki". asked 22 Aug '17, 22:08 4★droy0528 95●6 accept rate: 16%

 1 Hope this solution with proper variable names will help you.. import Queue import heapq for _ in range(input()): n,d = map(int, raw_input().split()) daywisePeople = sorted([map(int, raw_input().split()) for i in range(n)]) peopleIndex = 0 sadnessQueue = [] for dayIndex in range(1,d+1): while peopleIndex < n and daywisePeople[peopleIndex][0] <= dayIndex: heapq.heappush(sadnessQueue, (-daywisePeople[peopleIndex][2],daywisePeople[peopleIndex])) peopleIndex += 1 if not sadnessQueue: continue topPriorPerson = heapq.heappop(sadnessQueue)[1] if topPriorPerson[1] != 1: topPriorPerson[1] -= 1 heapq.heappush(sadnessQueue,(-topPriorPerson[2],topPriorPerson)) answer = 0 while sadnessQueue: person = heapq.heappop(sadnessQueue)[1] answer += person[1]*person[2] print answer  answered 23 Aug '17, 11:34 1.1k●1●10 accept rate: 19% Thanks for your help i don't have the enough reputation points to upvote but thanks a lot. (23 Aug '17, 19:18) droy05284★ Bro you gave me your points.. It was very nice of you.. :) Thanks.. I upvoted your question but that did not give you any point though.. :( btw, Will be happy to help next time.. :) (23 Aug '17, 20:02) 1 That's because the question is marked "community wiki". @droy0528 generally you do not need to do that, it's meant for editorials and posts on the forum where others members can contribute :) (23 Aug '17, 20:35) meooow ♦6★ I have very less knowledge of codechef forum so i just tick the community wiki option next time i will take care of it @meoow . @kauts_kanu First i thought no one will answer my question but u answered so i think to give points u deserve thanks for help. (23 Aug '17, 22:54) droy05284★
 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:

×2,718
×6
×3

question asked: 22 Aug '17, 22:08

question was seen: 205 times

last updated: 23 Aug '17, 22:54