Editorial for WC '17 Finals J2 - Redundant Formations
Submitting an official solution before solving the problem yourself is a bannable offence.
Our overall approach should be to consider each possible substring of , check whether or not it's redundant, assemble a list of distinct substrings which are, and output the number of substrings in this list at the end.
We can do so by iterating over all pairs of indices , such that . Each such pair corresponds to the substring , with a length of . We can then consider each index between and (inclusive), and check if the substring is equal to (note that should also be capped at to avoid considering substrings which would go past the end of ). If such an index is found, then a pair of overlapping equal substrings has also been found, meaning that must be redundant.
What remains is maintaining the list of distinct redundant substrings, and being able to add to it if not already present. One option is to maintain this list as an array, and loop over all of its existing entries to check if is equal to any of them. A more elegant option is to use a built-in data structure such as a C++ set
, which will automatically ensure that its entries are all distinct.
The time complexity of the solution described above is , which is comfortably fast enough, though it's also possible to optimize it to .
Comments