My sol. was getting TLE due to sort function. CodeChef: Practical coding for everyone
But I have seen some sol. using the same approach and getting accepted. Can you explain the flaw in my sol.?
My sol. was getting TLE due to sort function. CodeChef: Practical coding for everyone
But I have seen some sol. using the same approach and getting accepted. Can you explain the flaw in my sol.?
Even O(K) will be slow, so O(K log(K)) and O(K^2) are slow tooā¦ But similar to my approach, there are customers for at most N compartments, so you have to take care only those onlyā¦
Just try to replace your for(int i=0; i<k; i++) {
with map iterator, same for next for loop
Good to see you playing with the STL. Cheers!
Thanks @bugkiller, actually it was the first time I used an iterator to iterate over a map, so I was really happy with it
I was using similar approach, but was new with STLās, yet got to learn very new things from this question.
My approaches:
http://www.codechef.com/viewsolution/3205739
http://www.codechef.com/viewsolution/3205773
http://www.codechef.com/viewsolution/3206699
http://www.codechef.com/viewsolution/3249418
finally saw your solution just after completion, liked the way of your coding.
Nice job though, playing with the multimap
Usually, whenever I see a multimap question I always tend to ādegenerate itā into a map of map<key, vector > as it is more intuitive to me.
Regarding your approach, I guess you can separate the multimap from the data structure and thus speed up your code quite considerably
You didnāt even need the k, i used a greedy approach as well and passed within time O(N).
Basically, my algo was as follows:
Sort the customers segregated by first the compartments, then by their arrival time. Hold one customer with us,start by the first customer :
Yes, DP is feasible for this problem. Congratulations for you Accept!
I think greedy is much easier to implement, since we donāt need to remap the times.
I have sometimes problem with greedy algorithms, because sometimes its not easy if it works or notā¦
Just a comment, in this specific case, the correctness of the greedy approach can be proven.
(cf. the linked wiki page about Activity Selection Problem)
I have implemented the same method and solution is accepted with 2.02s but I can see solution with similar approach accepted in less than 1s. Is it only because of the fast IO or some other tweak in the code ?
My solution : CodeChef: Practical coding for everyone
I used radix sort for sorting finishing time and preferred components, and then used the activity selection problem, coupled with fast I/O and got AC. Link: CodeChef: Practical coding for everyone
but is my approach correct and if it is how to implement it?
Vectors of vector is extremely time consuming for such large data. POD works better here.
Your struct is supposed to take 3 members at compile time, so it is faster. On the other hand, a vector is generic and ready to accommodate more elements (members) although you donāt supply it.
Plus vector keep track of currently allocated memory and size behind the scene that is more expensive than PODs(more@Passive data structure - Wikipedia) without any constructor/destructor cost.
@anonymousins read my answer above, Iāve used the same idea. When searching for hash functions I came across STL maps, read about them, implemented them in my code and voila! AC! STL map takes care of hasing, I read that its insert, delete and lookup operations are of O(logn) complexity.
Will you please help me checking why am I getting WA for the problem.
http://www.codechef.com/viewsolution/3256692
how can we do it in c?
I think it should be caused by different implementation. STL is always a little slower.