Very Strict Time Limit! Even with the sort functions removed, it gets a TLE.
Probably because O(k^2) solutions were forced NOT to pass the time limits.
1 Like
I have sometimes problem with greedy algorithms, because sometimes its not easy to see if it works or not… From my point of view the DP is more “deterministic”.
The key idea is that compartments are independent as written in editorial.
You can use this DP:
- for max to time MT, we know that max guests starting at MT + 1 is 0
- for all times T = MT downto 0 we can do: if there comes guest at time T and leaves at time L, the max for time T is max( T + 1, 1 + dp[L] )
at the end the result is dp[0] for each compartment.
Implementation was tricky - times were up to 109 (so not possible to use array for DP), but N is up to 105, so at most 2 * 105 different times. My first idea was to do “normalization” → map those at most 2 * 105 different times to numbers 0…200000 and use array for DP (a lot of work needed here), but than I made it using tree maps - see my Java solution for details and ask if something is unclear…
1 Like
I have used map data structure, coupled with fast I/O and good code organization and got AC with relative ease.
If you know the algorithm and some good data structures, using scanf()/printf() is almost always enough!
As a bonus, if you know your way around how the I/O system works, you can even get AC with cin/cout as my solution submitted few seconds ago in practice section proves:
http://www.codechef.com/viewsolution/3251027
Think algorithmically above all,
Bruno 
4 Likes
I’ve used the same approach given in the editorial but I thought of it as Earliest Deadline First(EDF) scheduling, allot a compartment to the customer who leaves earliest And in order to keep track of free/occupied compartments I used map, using compartment number as key and the leaving time as data. STL sure makes programming in C++ a lot simpler. Here’s my solution.
@shangjingbo i just wanted to know what’s wrong in the solution here. In this i sort the array two times. First i sort it with respect to “room no” then in the chunks of same room no’s i sort them wrt deadlines. At least can you tell me which test case does it fail. Please help
Could someone post an AC solution in Python ? I don’t even know if it’s possible since no pythonista managed to get AC for this problem. I would love to learn how to solve it
I tried the same approach after finding an article on Interval scheduling at wiki.
To maintain all stuff sorted, I completely ignored the value of K and managed a map mapping compartment value to a set containing all input values of entry and exit time.
Although first solution could have passed, I kept on optimizing it after TLEs only to realize the input data is so large that I need to read input fast.
Two similar codes(almost), one getting RUNTIME error & the other got AC
first i submitted using vector (i have done this earlier in other problems successfully ) but got runtime error & same code i submitted using structure(everything was same except i stored the value in struct variable instead of vector ) & … got AC . lol !!
CodeChef: Practical coding for everyone (using vector)
CodeChef: Practical coding for everyone (using structure)
i’d appreciate if anyone willing to answer …
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 
Changing data types will get you accepted I would really like to know why this is happening )
Can anybody explain why this is happening.
thanks in advance
Can someone explain the time complexity given in the editorial? Does it take the time taken to sort the intervals into account?
https://www.codechef.com/viewsolution/11861897
https://www.codechef.com/viewsolution/11861658
Can someone please point the errors
I am getting TLE. Can someone please find the reason.
Thanks a lot for giving your time.
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.?