Editorial for WC '17 Contest 1 J4 - Canuck Detection


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.

The most direct solution is to consider all possible ordered triples of indices (i, j, k) which contain the required characters for the subsequence our – in other words, such that i < j < k, S[i] = o, S[j] = u, and S[k] = r. This can be accomplished with 3 nested loops, iterating over all possible combinations of these indices. If we find any triple of indices meeting these requirements, then they correspond to the subsequence our and we can output Y.

Unfortunately, the above solution is too slow to get full marks. It requires considering almost N^3 combinations of indices in the worst case, which in formal computer science terms means that it has a "time complexity" of \mathcal O(N^3). It's possible to instead solve the problem by only considering each index at most once, with a time complexity of \mathcal O(N). If we find the first o in S, then it can't help us to use a later o instead. So, we should instead then find the first u after that first o, and then the first r after that u. If we find all 3 required letters in order like this, then we've found the subsequence our. On the other hand, if we're unable to find the next required letter at any point, then the subsequence must not exist in S.


Comments

There are no comments at the moment.