Editorial for WC '15 Contest 4 J2 - Mission Briefing


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.

Given a string, we want to count how many substrings from the set 001009 occur. By reading the question carefully, one should notice that multiple instances of the same string should be counted only once. Namely, 001.abc.001a should only count 1 towards the final answer. Furthermore, from the sample input and output, one should understand that the string can be surrounded by anything, including other digits. Namely, an occurrence of .20001. should still be counted as 001. We should therefore not assume that strings are surrounded by punctuation. Finally, we should not consider 000 to be a valid agent.

Assuming the string has 0-based indices, one way to solve the problem is to keep track of occurrences with a boolean array (accessible from indices 1 to 9) initialized to false. We loop through the input string, starting at index 2 and ending at index N-1, where N is the length of the string. We check the last 2 indices to make sure both of them are the digit 0, and then check to make sure the current index is a digit from 1 to 9 (most programming languages support directly comparing ASCII characters). If so, set the corresponding boolean variable to true. To get the answer, count the number of true values in the boolean array. This solution runs in \mathcal O(N) time.

An alternate solution is to just use string searching functions in the standard library of your programming language (e.g. string::find() in C++), which should take \mathcal O(N) per call on the length of the string. We have to make 9 calls, one for each digit from 1 through 9.


Comments

There are no comments at the moment.