Editorial for WC '15 Contest 4 J2 - Mission Briefing
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 001
…009
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 -based indices, one way to solve the problem is to keep track of occurrences with a boolean array (accessible from indices to ) initialized to false. We loop through the input string, starting at index and ending at index , where is the length of the string. We check the last 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 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 per call on the length of the string. We have to make calls, one for each digit from through .
Comments