euler circuit ?

Revision en2, by faresbasbas, 2020-07-21 23:58:45

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 :)

Tags #graph theory, #strings, euler tour, #cses

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English faresbasbas 2020-07-23 17:18:43 628
en7 English faresbasbas 2020-07-23 15:40:41 11
en6 English faresbasbas 2020-07-23 15:39:54 597
en5 English faresbasbas 2020-07-23 00:46:38 20 Tiny change: 'dvance :) ' -> 'dvance :) \n\nedit : solved :)'
en4 English faresbasbas 2020-07-22 00:04:38 4
en3 English faresbasbas 2020-07-21 23:59:21 24
en2 English faresbasbas 2020-07-21 23:58:45 70
en1 English faresbasbas 2020-07-21 23:57:13 1303 Initial revision (published)