https://cses.fi/problemset/task/1113↵
I was solving this problem from cses , I came up with an idea which is I can know the first ans last character of each string in the lexicographical sorted rotations which is.↵
↵
The last characters is the input itself and the first characters is the sorted input↵
↵
For example: (* represents an unknown character)↵
↵
s = "cb#ab"↵
↵
Then the lexicographical sorted rotations from the input are:↵
↵
"****c"↵
↵
"****b"↵
↵
"****#"↵
↵
"****a"↵
↵
"****b"↵
↵
And the sorted input is:↵
↵
"#abbc"↵
↵
So the first characters are:↵
↵
"#****"↵
↵
"a****"↵
↵
"b****"↵
↵
"b****"↵
↵
"c****"↵
↵
By combining i will have:↵
↵
"#***c"↵
↵
"a***b"↵
↵
"b***#"↵
↵
"b***a"↵
↵
"c****b"↵
↵
Basically I will construct a graph by adding a directed edge from first to last character of each string. The graph idea if x have a direct edge to y then y is before x in the answer string. So I can just find an Euler circuit which starts at '#' and ends at '#' and it will be the answer. But the problem with the idea is if there is a character which appears more than once. The logic may break because then you will have more than one choice to choose. But actually there should be a unique answer (all the choices are wrong except one but idk how to differentiate between them)↵
Any ideas to improve the answer or any other ideas to solve the problem ?↵
Thanks in advance :)
I was solving this problem from cses , I came up with an idea which is I can know the first ans last character of each string in the lexicographical sorted rotations which is.↵
↵
The last characters is the input itself and the first characters is the sorted input↵
↵
For example: (* represents an unknown character)↵
↵
s = "cb#ab"↵
↵
Then the lexicographical sorted rotations from the input are:↵
↵
"****c"↵
↵
"****b"↵
↵
"****#"↵
↵
"****a"↵
↵
"****b"↵
↵
And the sorted input is:↵
↵
"#abbc"↵
↵
So the first characters are:↵
↵
"#****"↵
↵
"a****"↵
↵
"b****"↵
↵
"b****"↵
↵
"c****"↵
↵
By combining i will have:↵
↵
"#***c"↵
↵
"a***b"↵
↵
"b***#"↵
↵
"b***a"↵
↵
"c****b"↵
↵
Basically I will construct a graph by adding a directed edge from first to last character of each string. The graph idea if x have a direct edge to y then y is before x in the answer string. So I can just find an Euler circuit which starts at '#' and ends at '#' and it will be the answer. But the problem with the idea is if there is a character which appears more than once. The logic may break because then you will have more than one choice to choose. But actually there should be a unique answer (all the choices are wrong except one but idk how to differentiate between them)↵
Any ideas to improve the answer or any other ideas to solve the problem ?↵
Thanks in advance :)
