FGFS - Editorial

easy
editorial
greedy
jan14
sorting

#4

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


#5

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


#6

@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


#7

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


#8

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.


#9

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

http://www.codechef.com/viewsolution/3160692 (using vector)

http://www.codechef.com/viewsolution/3160968 (using structure)

i’d appreciate if anyone willing to answer … :slight_smile:


#10

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…


#11

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:


#12

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


#13

I got runtime error please help me .solution id:
https://www.codechef.com/viewsolution/9963237.


#14

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

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

Can someone please point the errors


#15

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

What’s wrong with the approach? Please help


#16

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

Thanks a lot for giving your time.

Here is my code.


#17

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


#18

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


#19

Probably due to the doubled time limit for Java?


#20

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


#21

My sol. was getting TLE due to sort function. http://www.codechef.com/viewsolution/3250997

But I have seen some sol. using the same approach and getting accepted. Can you explain the flaw in my sol.?


#22

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:


#23

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