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 :) ↵
↵
edit : solved :)↵
↵
edit: my AC solution↵
↵
I knew the solution but it was just an intuition i still don't have a proof, But that's it↵
↵
You just have to number the strings like if you have string s = "aab#a"↵
↵
every "a" should have something to differentiate from others so I numbered them↵
↵
so the string will be a1 a2 b1 # a3↵
↵
also the sorted string the same↵
↵
sorted = "#aaab" so it will be # a1 a2 a3 b1↵
↵
so overall it's↵
↵
"# *** a1"↵
"a1 *** a2"↵
"a2 *** b1"↵
"a3 *** #"↵
"b1 *** a3"↵
↵
then the graph is↵
↵
'# -> a1 -> a2 -> b1 -> a3 -> #↵
↵
then the answer is a1 a2 b1 a3 which is "aaba"↵
↵
and that's it :)
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 :) ↵
↵
edit : solved :)↵
↵
edit: my AC solution↵
↵
I knew the solution but it was just an intuition i still don't have a proof, But that's it↵
↵
You just have to number the strings like if you have string s = "aab#a"↵
↵
every "a" should have something to differentiate from others so I numbered them↵
↵
so the string will be a1 a2 b1 # a3↵
↵
also the sorted string the same↵
↵
sorted = "#aaab" so it will be # a1 a2 a3 b1↵
↵
so overall it's↵
↵
"# *** a1"↵
"a1 *** a2"↵
"a2 *** b1"↵
"a3 *** #"↵
"b1 *** a3"↵
↵
then the graph is↵
↵
'# -> a1 -> a2 -> b1 -> a3 -> #↵
↵
then the answer is a1 a2 b1 a3 which is "aaba"↵
↵
and that's it :)
