Need help in solving problem ICPC Trainer DS Heaps

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

1 Like
2

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
1 Like
3

Thanks for your help i don’t have the enough reputation points to upvote but thanks a lot.

4

Bro you gave me your points… It was very nice of you… :slight_smile: Thanks…
I upvoted your question but that did not give you any point though… :frowning: btw, Will be happy to help next time… :slight_smile:

5

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 :slight_smile:

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