Editorial for Mock CCC '18 Contest 5 S4 - Sparse Binary String Counting
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
One way to count all such substrings is to count the number of such substrings that contain the first one as the leftmost one, then count the number of such substrings that contain the second one as the leftmost one, and so on. This is doable in linear time.
Comments