The world's first traffic light dates back to 1868. It was installed in London to control traffic for... horse-drawn vehicles! Today, traffic lights can be found at street intersections in almost every city in the world, making it safer for vehicles to go through them.
Traffic lights have at least two states, and use one color (usually red) to signal "stop", and another (usually green) to signal that cars can proceed through. The very first traffic lights were manually controlled. Nowadays they are automatic, meaning that they have to be carefully designed and timed in order to optimize the overall travel time for all the participants in traffic.
Given the description of a city plan and planned paths for all cars in that city, optimize the schedule of traffic lights to minimize the total amount of time spent in traffic, and help as many cars as possible reach their destination before a given deadline.
The city plan consists of one-way streets and intersections. Each street:
Figure 1. A city plan with 4 intersections (0, 1, 2, and 3) and 7 streets (a, b, ... , g-street). Intersections 0 and 2 are directly connected both ways through a-street and b-street. c-street uses a bridge over a-street and b-street and does not intersect with those two streets.
Note that while the streets are one-way, it is still possible to have two one-way streets connecting two intersections in opposite directions (see intersections 0 and 2 and a-street and b-street in Figure 1). However, there will never be two streets connecting two intersections in the same direction.
There is a traffic light at the end of every street (just before the intersection). Each traffic light has two states: a green light indicates that the cars from that street can cross the intersection and head towards any other street, while a red light indicates that the cars from that street need to stop. At most one traffic light will be green at each intersection at any given time. While the light is green for an incoming street, only cars from this street will be allowed to enter the intersection (and move to any outcoming street), all other cars have to wait.
When the light at the end of a street is red, arriving cars queue up waiting for the light to turn green. When the light is green, one car can cross the intersection every second. This means that if a green light for a given street lasts for $$$T_i$$$ seconds then only the first $$$T_i$$$ cars from that street will continue their travel (see Figure 2). Others will need to wait for the following green light.
Figure 2. Consider an intersection with two incoming streets (a-street with 3 waiting cars and b-street with 2 waiting cars), and two outgoing streets (c-street and d-street). There are two traffic lights, one at the end of a-street with $$$T_1=2$$$ and one at the end of the b-street with $$$T_2=3$$$. Initially, the traffic light of a-street is green, and the first (yellow) car starts moving. At $$$T=1$$$, the next (green) car from a-street starts moving. At $$$T=2$$$, a-street has a red light, and the last (red) car waiting there needs to stop. At the same time, the traffic light of b-street turns green, and the first (purple) car queued there starts moving. At $$$T=3$$$ and $$$T=4$$$, the two (purple and blue) cars that were initially on b-street have already passed the traffic light and continued their path. At $$$T = 5$$$, the light at a-street turns back to green and the (red) car that was waiting there can now move.
For each intersection we can set a traffic light schedule. The traffic light schedule determines the order and duration of green light for the incoming streets of the intersection and repeats itself until the end of the simulation. The schedule is a list of pairs: incoming street and duration. Each street can appear at most once in the schedule. The schedule can ignore some of the incoming streets – those will never get a green light.
The traffic light schedule is controlled by your submissions. You don't have to specify the schedule of all traffic lights. By default all lights on all intersections are red (yes, cars stuck there will have to wait until the end of simulation).
In the following example, an intersection has 3 streets leading to it (a, b, and c-street), and one leaving the intersection (d-street). We consider three different example schedules for these traffic lights:
No traffic light schedule (default).
Figure 4 (a). If no traffic light schedule is set for an intersection, all of the traffic lights remain red throughout the simulation. Any cars that are scheduled to pass through a, b, or c-street will be blocked and not reach their destination.
Schedule that covers only one street.
Figure 4 (b). In this example the traffic light schedule covers only one incoming street (b-street). In this case b-street always has a green light. Αny cars coming from b-street will always go through the intersection directly, while any cars scheduled to pass through either a-street or c-street will be blocked and not reach their destination.
Schedule that covers all streets.
Figure 4 (c). In this example, the traffic light schedule
covers all incoming streets (c-street, then a-street, then b-street). For
each street we can define a different
Ti, meaning different duration during which that traffic light remains green.
Each car is described by the path (a sequence of streets) it is going to drive through. The paths are defined by the input datasets and can't be altered. In the input datasets we guarantee that each car can go through a single intersection at most once.
Initially, all cars start at the end of the first street in their path, waiting for the green light (in case the traffic light is red), or ready to move (if it's green). If two cars start at the end of the same street, the car listed first in the input file goes first. Each car then follows a given path, while obeying the traffic lights, and needs to reach the end of the last street in that path.
Cars are queued up at the end of each street. The first car in the queue can cross the intersection immediately after the light turns green. There is no delay while a car passes through an intersection. Cars after that cross the intersection one after another, one car every second.
When a car enters the last street of its path, it completes its drive until the end of the street and then is immediately removed from it. This means that the car does not queue up at the end of the last street of its path and does not enter the intersection at the end of it.
Figure 3. This figure shows the state of three cars at exactly $$$T$$$ seconds, with the simulation starting at $$$T=0$$$ and ending at $$$T=5$$$. The street has $$$L=3$$$, meaning that any car needs 3 seconds to go from its beginning to the end. The light turns green on the left intersection at $$$T=1$$$ and turns red again 2 seconds later. The cars are queuing up at the end of the street, with yellow being the first one. At $$$T=1$$$, the first (yellow) car immediately starts moving and reaches the end of the street 3 seconds later, at $$$T=4$$$. The second (red) car has to wait 1 second before it starts moving and arrives at the end of the street 3 seconds later, at $$$T=5$$$. The third (purple) car did not have enough time to enter the street, as the light already turned red. Note that this figure only shows two streets for simplicity: when a traffic light is shown to be red, this means that another one in the same intersection has turned green.
Each input data set is provided in a plain text file. The file contains only ASCII characters with lines ending with a single '\n' character (also called “UNIX-style” line endings). When multiple numbers are given in one line, they are separated by a single space between each two numbers.
The first line contains five numbers:
The next $$$S$$$ lines contain descriptions of streets. Each line contains:
The next $$$V$$$ lines describe the paths of each car. Each line contains:
Figure 5. The streets and intersections, as given by the example input data set, as well as the two cars at their initial positions.
Your submission describes the traffic light schedules you want to set for specific intersections.
The first line must contain a single integer $$$A$$$ ($$$0 \leq A \leq I$$$), the number of intersections for which you specify the schedule.
Then, the submission file must describe the intersection schedules, in any order. Each schedule must be described by multiple lines:
Each intersection can only be listed once in the submission file. And each street name can only be listed once per schedule. If the street name is not present in intersection configuration it means its traffic light is always red. If an intersection configuration is not present in the submission file then all of its traffic lights are always red.
A score is awarded for each car that finishes its path before the end of the simulation. For a car that finishes its path at time $$$T$$$, the awarded score is $$$F$$$ points (fixed award for finishing the path) and additionally $$$D - T$$$ points. (One point for each second left when the car finished the path.)
In other words: if a car finishes at time $$$T$$$ it scores
The score for the solution is the sum of scores for all cars.
For instance, in the example above, the first car:
This first car would have reached the end of rue-de-rome at $$$T = 7$$$, but this is past the deadline of the run (defined in the input data set). Meaning that 0 points are assigned to this car.
The second car:
So the second car finishes before the deadline, and gets a score of $$$1000 + (6 - 4) = 1002$$$ points.
The final score for this submission is 1002.
Note that there are multiple data sets representing separate instances of the problem. The final score for your team will be the sum of your best scores for the individual data sets.