Editorial for TLE '16 Contest 6 (Mock CCC) J4 - Ski Rentals


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

To simulate the movement of the queues, we can use a series of three queues. After pushing each skier into its own respective queue, we have to simulate the passing of time by subtracting the wait time of the first skier by one. Don't forget to keep a timer variable to keep track of the time. By modulating the timer variable by 30 (and checking for a remainder of 0), we can determine the intervals of 30 seconds. After this time period, we have to identify the length of all the lines. If all the lines have a different length, then we will pop the person from the end of the queue and push it into the line with the least amount of people. You can use a simple if/else condition block to determine which lines are longer than the other (there should be 6 different scenarios in the if/else logic). Remember to check for an empty queue at every iteration and break out of your loop! Also, watch out for a continuous section of people with a wait time of 0 (this means multiple people can exit the line every second). Remember to remove people with zero wait time before and after you add every second. Once all of your queues have a length of 0, you can finally print out your time-tracker variable!

Instead of iterating through each skier on a one-second basis, we can iterate through the queues 30 seconds at a time. If we receive a negative number, we can append the time difference to the next skier. Once all the queues are empty, we will pick the line that has the highest negative number and take the difference in relation to our total time to determine the number of seconds it would take for all skiers to receive their equipment.

Time Complexity: \mathcal{O}(\sum W)


Comments

There are no comments at the moment.