ananth94's blog

TLE on a codechef problem (MCHEF) using multiset.
By ananth94, history, 9 years ago, In English

Hello Codeforces community! I recently took part in the July 2015 long challenge on www.codechef.com . There was a problem called Masterchef( Problem code: MCHEF). I used a multiset as a priority queue to calculate the minimum cost for each dish. In the author's solution, they used a set instead of a multiset. The complexities are the same but my solution TLEs for the second subtask. Could someone please help me out here?

This is my solution: https://www.codechef.com/viewsolution/7352429 This is the editorial: http://discuss.codechef.com/questions/71856/mchef-editorial

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You are using long long everywhere instead of int which makes your solution very slower as compared to other solutions , also it would be good if you use priority_queue instead of set as they are much faster.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used a multiset because there are duplicate values which as far as I understand are not accomodated by priority queues.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Changing long long to int worked slightly but not well enough.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've solved it using multiset link
so multiset might not be the reason for TLE

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can't think of any other reason. Could it be that I'm allocating too much memory during by testcases for loop?

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I also solved it by multiset. My solution is here. And also I used long long without getting TLE.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Also, I've written two solutions one of which is giving me a wrong answer with the only difference being that I declared the array outside. What is the difference?

  1. https://www.codechef.com/viewsolution/7517631
  2. https://www.codechef.com/viewsolution/7517613
→ Reply