Hello, everyone!
An editorial for our round will be posted here in some time.
Unfortunately, both AndreySergunin and I are rather busy (we are at different summer camps at the moment) so it'll take some time to write the editorial.
Sorry for the inconvenience.
556A - Case of the Zeros and Ones
If there still exist at least one 0 and at least one 1 in the string then there obviously exists either substring 01 or substring 10 (or both) and we can remove it. The order in which we remove substrings is unimportant: in any case we will make max(#zeros, #ones) such operations. Thus the answer is |#ones - #zeros|.
Time: O(N); memory: O(N) or O(1).
Notice that after pressing the button n times gears return to initial state. So the easiest solution is to simulate the process of pressing the button n times and if at some step the active teeth sequence is 0, 1, ... , n - 1 output "Yes" else "No". But this solution can be improved. For instance, knowing the active tooth of the first gear you can quickly determine how many times pressing the button is necessary, go to that state and check the sequence only once.
Time: O(N) or O(N2); memory: O(N) or O(1); solutions: 11822751 (O(N)) and 11822759 (O(N2))
