RailroadSwitchOperator
SRM 676 · 2015-11-03 · by cgy4ever
Problem Statement
Alice is a railroad switch operator. She is in charge of a network of rails that has the topology of a perfectly balanced binary tree with N leaves. N is a power of two. Each non-leaf node of the tree has a left child and a right child. The leaves are numbered from 1 to N from the left to the right.
There will be some trains that will pass through Alice's railroad network. Each of these trains will enter the network in the root of the tree and leave it in one of the leaves. Each non-leaf node contains a railroad switch that can send an incoming train either towards the left child or towards the right child of that node. Initially all switches point to the left.
You are given the information about the trains in
More formally, for each integer z = 1, 2, 3, ... the following steps happen, in order:
- If there is a train with t[i] = z, at time z that train will appear in the root.
- Immediately after that happens, Alice decides whether she wants to take an action. If she doesn't, nothing happens. If she does, she may flip as many switches as she likes. All these flips happen in an instant.
- All trains leave their current nodes according to the state of the switches in those nodes.
- During the time interval (z, z+1) each train travels along an edge of the tree to the next node.
- Any train that just reached a leaf leaves the network.
Alice must route all trains to their desired destinations. Given this requirement, she would like to minimize the number of actions she has to take. (Note that she only cares about the number of actions. The total number of times a switch is flipped does not matter.)
Compute and return the smallest number of actions Alice has to take in order to route all trains correctly.
Constraints
- N will be a power of 2 between 2 and 131,072 (= 2^17), inclusive.
- The number of elements in t will be between 1 and 2,500, inclusive.
- x will have exactly the same number of elements as t.
- Each element of x will be between 1 and N, inclusive.
- Each element of t will be between 1 and 5,000, inclusive.
- t[i] < t[i+1] for all valid i.
2
{1,2,1,2,1,2,1,2}
{1,2,3,4,5,6,7,8}
Returns: 7
This network is very simple: one root and two leaves. Trains appear in the root at time 1, 2, ..., 8. The first train can use the default setting of the switch. For each of the 7 remaining trains Alice must take an action to flip the switch.
4
{1,4,4,4,4,4,4,4,4,4}
{1,2,4,8,16,32,64,128,256,512}
Returns: 1
32
{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32}
Returns: 20
131072
{1,1,1,1,1,1,1}
{10,300,500,676,800,950,1000}
Returns: 0
1024
{1,1024,2,512,4,256,8,128,16,64,32}
{1,2,3,5,8,13,21,34,55,89,144}
Returns: 10
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RailroadSwitchOperator with a public method int minEnergy(int N, vector<int> x, vector<int> t) · 76 test cases · 2 s / 256 MB per case