You are not logged in. Please login at to post your questions!


Need help in solving problem ICPC Trainer DS Heaps

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 .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

droy0528's gravatar image

accept rate: 16%

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:

        topPriorPerson = heapq.heappop(sadnessQueue)[1]
        if topPriorPerson[1] != 1:
            topPriorPerson[1] -= 1

    answer = 0
    while sadnessQueue:
        person = heapq.heappop(sadnessQueue)[1]
        answer += person[1]*person[2]

    print answer

answered 23 Aug '17, 11:34

kauts_kanu's gravatar image

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) kauts_kanu5★

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

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 22 Aug '17, 22:08

question was seen: 205 times

last updated: 23 Aug '17, 22:54