TopCoder problem "LiftScheduler" used in MM 33 (Division I Level One)



Problem Statement

    You are to direct a lift system in a building with N floors, M lifts, and a capacity of C people per lift. The simulation runs for four days. When individuals wish to make a journey between floors, they press a button at their starting floor indicating the direction (up or down) in which they wish to travel. When they enter the lift, they press a button in the lift indicating which floor they wish to travel to. Your task is to schedule the lifts to minimize the time spent travelling by the occupants of the building.



Time is split up into ticks, periods of length 3 seconds. In each tick, the following events occur.
  1. New journeys are created. If the button indicating their direction of travel on their starting floor is unlit, they press it. They then join the back of the queue on that floor. Anyone who has been queueing for at least twenty minutes gives up and takes the stairs.
  2. You are given the list of newly pressed buttons, from people starting journeys this tick, and from people who ended up entering lifts in the previous tick. You then tell the lifts what to do this tick.
  3. The lifts move, open/close their doors, or stay still. If the lift's doors are open, a light above the lift indicate which direction it is travelling in. People enter the lift if it is going in their chosen direction of travel. People who have arrived at their destination also exit the lift. If a lift with open doors has no entries or exits in that tick, it closes its doors at the end of the tick.
  4. On entering the lift, people press buttons, indicating which floor to go to.
You must supply two methods. At the start of each of the four days initialise is passed the arguments N,M,and C. It is then the case that every tick your method step is called and passed parameters upRequests, downRequests, liftRequests, and state. upRequests and downRequests contain lists of any floors at which buttons have been pressed in this tick desiring to go up or down. LiftRequests and destinationRequests show which buttons in lifts have been pressed; in particular, liftRequests[x] is the index of the lift in which the button is pressed, and destinationRequests[x] is the destination requested. state is a string of characters representing the state of each lift.



Each lift can be in one of five states: U (travelling upwards), D (travelling downwards), S(stationary, with doors closed), L(loading, having claimed to be about to be going up), M(loading, having claimed to be about to be going down). If moving, lifts travel one floor per tick. You may not change the state of a lift that is loading in either direction (the doors will close automatically when loading is finished, changing the state to 'S'). With the one exception of 'U' to 'D' and vice versa, all other state transitions are allowed. step must return a String ans of states, where ans[i] represents the new state for lift i.



Buttons are lit when pressed; when a lit button is pressed you are not informed. Floor buttons become unlit when that floor is arrived at by a lift claiming to be going in that direction, and lift buttons are unlit when the lift arrives at the requested floor. Floor buttons are then relit if individuals still wish to go in a particular direction, and no lifts are currently loading at that floor to go in that direction. Individuals having a choice of getting on multiple lifts will always choose the lift in the lowest numbered shaft. Lifts all start the day at floor zero. The simulation runs from 7a.m. to 8p.m. No journeys are generated after 7p.m.



Test Generation

Test cases are generated by choosing integers N in [5,40], M in [10,50], C in [5,30], P in [25,200], B in [1,20], and a double businessprob in [0,1].



The test cases are generated to simulate a building with some retail floors and some business floors. The business floors have about P employees per floor, while the retail floors have about P/10 per floor. Each employee arrives in the morning and leaves in the afternoon, and takes about one break per ten hours where they go down to the bottom floor. Shoppers come and go from the retail floors at a rate of about P per floor per hour, with fewer people early in the morning and late in the afternoon. The shoppers also move between retail floors with about P/2 of them leaving each floor for some other floor per hour. Finally, there is some random traffic, at a rate of about B people leaving each floor for some other floor per hour. Some more details of the test generation are below. For the precise implementation, see the source code.



Each non-ground floor is denoted business with probability businessprob, and retail otherwise. totretail is then the total number of retail floors. Then arrtimes, deptimes, arrdevs, depdevs, are generated, each of size N (with integer elements). Elements of arrtimes are randomly generated in [1200,3600] (8a.m. to 10a.m.), deptimes in [10800,13200](4p.m. to 6p.m.), and arrdevs and depdevs in [100,600](5-30 minutes). In expectation, each business floor has about P employees and retail floors have about P/10 employees. The employees of a floor have (roughly) Gaussian arrival times with means from arrtimes and deviations from arrdevs. Similarly for their departure times. We can calculate expi,t, the expected fraction of staff present on floor i at time t (this peaks at close to 1 for the whole of the middle period of the day). The staff on each floor take breaks at a rate of about 1/10 per hour. Thus, about expi,t*P/10 people leave each business floor for the ground level each hour (and a similar number return), while 1/10 as many leave and return each retail floor.



At time t, shoppers arrive and travel to floor i and leave floor i at a rate that is proportional to expi,t, peaking at P people per hour during the middle part of the day when expi,t=1. In addition, shoppers move between retail floors. At peak traffic, about P/2 people leave each retail floor for some other (randomly chosen) retail floor per hour. Thus, if there are R retail floors, the retail traffic from one to another peaks at P/2/(R-1). The i->j traffic is multiplied by expi,t and expj,t, reducing it early in the morning and late in the afternoon.



Finally, there is some random traffic between every pair of floors, at a rate of B/N people for each pair of floors per hour.



Scoring

Your preliminary score for a test case is the sum of the squares of the times (in ticks) of all journeys taken. If someone gives up and takes the stairs, that journey is scored as if it had taken 60 minutes. Anyone still in the system at 8p.m. shall be scored as if they had finished their journey at 8p.m.. The benchmark score is the sum over all journeys of (d+3)2, where d is the distance between the departure and arrival floors. Your final score for the test case is equal to sqrt((preliminary score+1)/number of journeys)-sqrt(benchmark score/number of journeys). In the event that your program crashes, exceeds the time limit or returns invalid output, your score for that case is zero. Your final score is the sum over all test cases where you have a non-zero score of BEST/YOUR where BEST is the least non-zero score for that test-case, and YOUR is your score for that case.

Visualization

A tool is available at http://www.topcoder.com/contest/problem/LiftScheduler/vis.html.
 

Definition

    
Class:LiftScheduler
Method:initialise
Parameters:int, int, int
Returns:int
Method signature:int initialise(int N, int M, int C)
 
Method:step
Parameters:int[], int[], int[], int[], String
Returns:String
Method signature:String step(int[] upRequests, int[] downRequests, int[] liftRequests, int[] destinationRequests, String state)
(be sure your methods are public)
    
 

Notes

-All generation that is not otherwise specified is uniform.

-There are 50 provisional tests.
-The memory limit is 1024MB and the time limit is 30 seconds.
 

Constraints

-M is in [10,50]
-N is in [5,40]
-P is in [25,200]
-C is in [5,30]
-B is in [1,20]
 

Examples

0)
    
"0"
Returns: 
"SEED = 0
N: 29
M: 33
C: 28
P: 184
B: 16
Number of Retail Floors /  Business Floors = 16 / 12
"
1)
    
"1"
Returns: 
"SEED = 1
N: 38
M: 48
C: 12
P: 66
B: 15
Number of Retail Floors /  Business Floors = 34 / 3
"
2)
    
"2"
Returns: 
"SEED = 2
N: 9
M: 48
C: 5
P: 132
B: 10
Number of Retail Floors /  Business Floors = 1 / 7
"
3)
    
"3"
Returns: 
"SEED = 3
N: 19
M: 20
C: 17
P: 126
B: 9
Number of Retail Floors /  Business Floors = 5 / 13
"
4)
    
"4"
Returns: 
"SEED = 4
N: 31
M: 46
C: 18
P: 175
B: 8
Number of Retail Floors /  Business Floors = 26 / 4
"
5)
    
"5"
Returns: 
"SEED = 5
N: 40
M: 20
C: 5
P: 57
B: 7
Number of Retail Floors /  Business Floors = 2 / 37
"
6)
    
"6"
Returns: 
"SEED = 6
N: 12
M: 20
C: 23
P: 123
B: 2
Number of Retail Floors /  Business Floors = 3 / 8
"
7)
    
"7"
Returns: 
"SEED = 7
N: 21
M: 33
C: 8
P: 181
B: 1
Number of Retail Floors /  Business Floors = 16 / 4
"
8)
    
"8"
Returns: 
"SEED = 8
N: 33
M: 18
C: 11
P: 54
B: 13
Number of Retail Floors /  Business Floors = 27 / 5
"
9)
    
"9"
Returns: 
"SEED = 9
N: 6
M: 33
C: 21
P: 48
B: 20
Number of Retail Floors /  Business Floors = 1 / 4
"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8747

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12199&pm=8747

Writer:

Unknown

Testers:

Problem categories:

Simulation