FGFS - Editorial

I am trying to solve Bon appetit problem from Jan challenge 2014 from 6 days.Still couldn’t solve it out… So it would be really nice if someone could help me to solve out this. I am trying to solve it in the following way.

1.Sort customers according to departure time.(quicksort)

2.Then go through each customer and directly retrieve a recent customer in that compartment.

if it results in an overlap(discard the customer).

else
increment count and update the recent customer in the specified compartment.

I came to know that a hashmap would serve the purpose.Each compartment would be mappped to certain index by the hashing function and then we would directly go there.

Questions.

1.How can i build a hash function so that given a compartment it would map it to certain index and when again a customer of this compartment appears i would directly go to this compartment in 1 operation.

2.Would this approach give me WA or TLE?

Please help…

My solution did not get accepted because TLE. (I used JAVA)

Here is the code for that solution.
But now i canged the data type values. (I used long data type and i changed them to int) Then my code got accepted. Here is that accepted code.
(This is not a problem in the algorithm i suppose, The code is almost same, I think to overcome the TLE problems we should aware of these kind of problems too :smiley: Changing data types will get you accepted :smiley: I would really like to know why this is happening )

Can anybody explain why this is happening.

thanks in advance :slight_smile:

Can someone explain the time complexity given in the editorial? Does it take the time taken to sort the intervals into account?

I got runtime error please help me .solution id:
CodeChef: Practical coding for everyone.

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

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

Can someone please point the errors

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

What’s wrong with the approach? Please help

I am getting TLE. Can someone please find the reason.

Thanks a lot for giving your time.

Here is my code.

Hm? I was able to do that in Java and had no problem with TLE (but I used DP)…

“exclusive at two ends”, it was left closed and right opened [from, to ) but probably it changes nothing…

1 Like

Probably due to the doubled time limit for Java?

“times were up to 10^9 (so not possible to use array for DP), but N is up to 10^5” Exactly! This was the area that required to be hit in the problem.

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.