IPCTRAIN java solution 100pts. TLE

general
,
1

Guys,
Can anyone suggest how to get 100 pts on this one ??(I have used a hash map)

https://www.codechef.com/viewsolution/14622106

2

Hey, my solution is very similar to yours. Except for the fact that instead of sorting for the entire set of days I used a Priority Queue. Instead of sorting the entire ArrayList when you add a trainer(s) you could initially maintain a single Priority Queue and prevent complexity spent in sorting. Here’s the link have a look:


[1] 

Also, removing from an arrayList takes quite some time: [Refer Here!][2] 



  [1]: https://www.codechef.com/viewsolution/14437252
  [2]: https://stackoverflow.com/questions/24462513/time-complexity-for-java-arraylist-removeelement
3

Any one having Easy and simple solution for ipctrain beginners

4

I have done it without using Priority Queues. Check it out
https://www.codechef.com/viewsolution/14500374

1 Like
5

Hey thanks, that made sense. Also one last thing.I have seen people check the documentation for time complexity of functions provided by java but when I tried, I couldn’t find it in the docs. May be it is an IDE specific implementation. Can u suggest something???

6

It’s from JavaDocs page example for Priority Queue :
https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
and for ArrayList : ArrayList (Java Platform SE 7 )
between the clauses you’ll find complexity given. Hope that helps.
Still if you dont find it, try searching for your specific needs on google, StackOverflow must be having the answers.

7

thanks…that helped.

8

@ssaxena36 Hey, I tried both ur optimizations…still getting a TLE. CodeChef: Practical coding for everyone …Can u suggest some other improvement???

9

My solution is simple if you know priority queue.

10

ok @vijju123 thanks i will check

11

remove this line Collections.sort(l); when you’re adding incoming trainers in the map it is costing you a lot. Now, this is because, you don’t need to do that, that is why Priority Queue is handling the stuff.

12

Can you tell something about your approach??

13

@vijju123 I used quick sort to sort the sadness levels(in descending order). Then the highest sadness levels were cancelled off till the remaining no of days is zero. The sadness levels which weren’t cancelled add on to the total sadness level. With some optimizations, I was able to get the answer. But yes, priority queue approach is much simpler. I hope I am clear.