FGFS - Editorial

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

@betlista >> Ofcourse, that would never go 10^9 iterations. Damn! :frowning: :smiley:

Good to see you playing with the STL. Cheers!

2 Likes

Thanks @bugkiller, actually it was the first time I used an iterator to iterate over a map, so I was really happy with it :smiley:

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

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

http://www.codechef.com/viewplaintext/3170241

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 :

  1. If the next customer needs a different slot(all requests for current slot is done) accept the one with us and hold on to the new one.
  2. Else, if the next customer arrives after the customer with us would leave - we can cater to the customer with us. So increment the count and hold the new customer now.
  3. Else, if the next customer can leave earlier than our current - shoo away the current and keep the new one.

@f03nix >> Nice implementation :slight_smile:

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! :smiley: 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.