Editorial for COCI '16 Contest 1 #3 Cezar
Submitting an official solution before solving the problem yourself is a bannable offence.
First, we need to sort the words in the order which corresponds to the permutation. Now we see that, after encoding, a word must be lexicographically smaller than all the words that come after it.
Word is smaller than word
if one of the two conditions is met:
is a prefix of
and
differ in the
letter and
is lexicographically smaller than
(
is the
letter of
,
is the
letter of
)
To ensure that comes after
is not smaller than
because of the first condition, it is sufficient to observe all pairs and check if
is a prefix of
.
The second condition is checked by constructing a directed graph consisting of nodes, where each node represents one letter of the English alphabet. The graph contains a directed edge
if and only if there exist words
and
such that
comes before
and they differ for the first time in the
letter. In other words, if there exists a directed edge
, then the letter that will be replaced with
must be lexicographically smaller than the letter which will be used to replace
.
Obviously, the solution will not exist if there is a cycle in the graph. Given the fact that the number of nodes is quite small, a cycle can be detected in various ways. One of the simpler ways is using the Floyd–Warshall algorithm that performs in the time complexity , where
is the number of nodes.
If the graph doesn't have cycles, then the graph is DAG (directed acyclic graph), which means that its nodes can be topologically sorted. For each node , it holds that all nodes which are accessible from
in a topologically sorted array come before it.
From the aforementioned conditions, we can see that the letter that is represented by the first node in a topologically sorted array must be assigned the letter a
, the second node the letter b
, and so on.
Comments