SequenceSync
SRM 238 · 2005-04-14 · by AdminBrett
SRM 238 · 2005-04-14 · by AdminBrett · Dynamic Programming, Search
Problem Statement
Problem Statement
State machines occur frequently in computer science literature. At any given point in time, a state machine is in a particular state p. After receiving an input symbol, the machine updates its state. The potential input symbols in this problem are 0, 1, 2, or 3. The String[] transitions describes how the state machine M behaves. Each element of transitions will contain 4 space delimited integers. The integers in element i (0-based) describe how M reacts to input while in state i. For example, if element 3 is "0 4 2 3", then M will transition from state 3 to state 0, 4, 2, or 3 depending on whether 0, 1, 2, or 3 are received as input, respectively.
Our state machine M is unfortunately out of control. We do not know which state M is currently in. To rectify the situation, we want to find a string s and a state h such that, after feeding s into M one symbol at a time, M will definitely be in state h. Considering all possible pairs of s and h, return the length of the shortest s. If no such pairs exist, return -1.
Our state machine M is unfortunately out of control. We do not know which state M is currently in. To rectify the situation, we want to find a string s and a state h such that, after feeding s into M one symbol at a time, M will definitely be in state h. Considering all possible pairs of s and h, return the length of the shortest s. If no such pairs exist, return -1.
Constraints
- transitions will contain between 1 and 20 elements inclusive.
- Each element of transitions will have the form "w x y z" where w, x, y, and z are integers, without extra leading zeros, between 0 and k-1 inclusive. Here k is the number of elements in transitions.
Examples
0)
{"1 1 1 1",
"1 1 1 2",
"0 2 2 2"}
Returns: 2
The string "33" forces the machine into state 2.
1)
{"1 1 1 1",
"2 2 2 2",
"3 3 3 3",
"0 0 0 0"}
Returns: -1
There are no strings that work here.
2)
{"0 0 0 0"}
Returns: 0
A string of length 0 works here.
3)
{"1 1 1 0",
"2 2 2 1",
"3 3 3 2",
"4 4 4 3",
"5 5 5 5",
"6 6 6 6",
"7 7 7 0",
"0 0 0 8",
"8 8 8 8",
"9 9 9 8"}
Returns: 15
4)
{"0 0 0 0",
"1 1 1 1",
"2 2 2 2",
"3 3 3 3",
"4 4 4 4",
"5 5 5 5",
"6 6 6 6",
"7 7 7 7",
"8 8 8 8",
"9 9 9 9",
"10 10 10 10",
"11 11 11 11",
"12 12 12 12",
"13 13 13 13",
"14 14 14 14",
"15 15 15 15",
"16 16 16 16",
"17 17 17 17",
"18 18 18 18",
"19 19 19 19"}
Returns: -1
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SequenceSync with a public method int getLength(vector<string> transitions) · 80 test cases · 2 s / 256 MB per case