can someone explain more for this problem (510C - Fox And Names)?
I read editorial but I didn't get that
Thanks for your help
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | adamant | 157 |
6 | awoo | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
can someone explain more for this problem (510C - Fox And Names)?
I read editorial but I didn't get that
Thanks for your help
Name |
---|
In this problem you have to find a permutation of characters 'a' to 'z', c1 c2 ... c26 such that if we suppose that c1 is lexicographically smaller than c2, c2 is smaller than c3 and so on, the given names will be sorted lexicographically.
Let's suppose that the characters are nodes of a graph, and an edge between two nodes u and v means that the character u is lexicographically smaller than v.
As I said before every character ci comes before all characters cj (j > i), we need to find an order which makes this constraint satisfied and this is actually a topological sort.
e.g. alphabet is: {a, b, c}
what is graph for this?
If a < b < c the graph is