Editorial for COCI '19 Contest 6 #5 Trener

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.

For the first subtask, you could have checked each possibility. The complexity is $\mathcal O(K^N)$ $O (K^{N})$ .

For the next two subtasks, it was necessary to build a directed acyclic graph (DAG) and count the number of paths from nodes on the first level to the nodes on the last level. This can be done using dynamic programming and we leave it as an exercise to the reader. Let's describe what kind of DAG will be built.

On each of the $N$ $N$ levels, we will have a node for each distinct surname with length equal to that level. The value of that node is equal to the number of surnames it represents. The edges are built naturally – from nodes on level $i$ $i$ towards nodes on level $i+1$ $i + 1$ . Edge from node $A$ $A$ to node $B$ $B$ exists if surname in node $A$ $A$ is different in exactly one letter from surname in node $B$ $B$ . Depending on how efficient you have built this DAG, you could have scored only the second subtask or the full score.

Comments

There are no comments at the moment.