Editorial for DMPG '19 S4 - Confusing Crossword Conundrum


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AvaLovelace

For the first subtask, for each query, we can do a BFS from each word that starts with b to determine which one has the shortest distance from a.

Time Complexity: \mathcal O\left(\left(N + M\right)^2Q\right)

For the second subtask, for each query, we can start the BFS from a instead. This will give us its distance to all other words in \mathcal O(N + M) time. We can then iterate through all the words that start with b to determine which one is closest to a.

Time Complexity: \mathcal O\left(\left(N + M\right)Q\right)

For the final subtask, notice that there are only 26 distinct values of b, the 26 English letters. By simultaneously starting BFS's from each word starting with a given letter b, we can find the answer to a b for every word a in \mathcal O(N + M). Breaking ties alphabetically can be done simply by pushing the initial words in alphabetical order into the queue.

Thus, we can precompute the answers for all 26 values of b in \mathcal O(N + M) time, then answer each query in \mathcal O(1).

Time Complexity: \mathcal O\left(N + M + Q\right)


Comments

There are no comments at the moment.