PartialRaceResults
SRM 813 · 2021-09-15 · by misof
Problem Statement
A race just finished. Some contestants took part in the race. There were no ties in the race, each contestant finished it in a different amount of time.
Each contestant was assigned a different character (either a letter or a digit). The order in which the contestants finished the race can therefore be represented by a string that contains each of those characters exactly once.
(The first character of the string is the winner of the race, and so on. For example, if "x7X" are the results of a race, contestant 'x' won, contestant '7' was second and contestant 'X' was third.)
You would like to know the results of the race, but you could not find them posted anywhere. So you decided to interview some of the contestants and to deduce the results from what they can tell you.
Each contestant you happened to interview only managed to remember two other contestants: one that finished before them and one that finished after them. So, for example, contestant X could have given you the information "I finished the race somewhere between contestants Y and Z". We will denote this information "X:YZ" for short. Note that order matters: "X:ZY" is not the same information as "X:YZ".
Each such interview tells us something about the results of the race. For example, if we have the contestants a,b,c,d,X,Y,Z and the information "X:YZ", some possible results of the race are "YaXbcZd", "abcdYXZ", and "YdaXbZc".
On the other hand, the following results are no longer possible: "XYZabcd", "ZaXbcYd", and "YaZbXdc".
You are given the
Assume that the set of all contestants is exactly the set of those contestants who appear in memories. (All of them, not just those that were interviewed.)
Determine whether there are some results of the race that are consistent with all the given memories. If yes, find and return any one such result of the race. If no, return an empty string instead.
Constraints
- memories will contain between 1 and 500 elements, inclusive.
- Each contestant is represented by a letter or a digit (a-z, A-Z, 0-9).
- Each element of memories will have the form "X:YZ", where X, Y, and Z represent contestants.
{"B:AC"}
Returns: "ABC"
{"B:AD", "7:BD"}
Returns: "AB7D"
{"A:BC", "B:AC", "C:AB"}
Returns: ""
{"A:bc", "A:cb"}
Returns: ""
{"0:39", "2:05", "1:37", "2:18", "5:78", "6:29", "5:46"}
Returns: "4310725869"
There are multiple valid answers. For example, "3104275869" is also a valid answer.
{"A:AA"}
Returns: ""
This is also considered impossible. This contestant must be mistaken, as they could not have finished better or worse than themselves.
{"a:bc", "0:12", "X:YZ"}
Returns: "1YbX0ac2Z"
With so few interviews (and ones that clearly aren't in conflict), there are very many valid answers.
Submissions are judged against all 115 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PartialRaceResults with a public method string reconstruct(vector<string> memories) · 115 test cases · 2 s / 256 MB per case