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)$ ~\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)$ ~\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)$ ~\mathcal O(N + M)~ time, then answer each query in $\mathcal O(1)$ ~\mathcal O(1)~.

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

Comments

There are no comments at the moment.