Editorial for Another Contest 1 Problem 1 - Binary String Operations


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 intended solution for this problem is to maintain an augmented balanced binary search tree (BBST) on the string. We will not be covering full implementation details for the BBST, but will cover how to perform the update and query operations.

We'll start with the query. Each node needs to maintain the maximal length prefix of only 1's, maximal length suffix of only 1's, and maximal length substring of only 1's. For a leaf node, these values are all identically either 0 or 1 depending on the character. When we're merging the result for a non-leaf node, the maximal prefix and suffix can be computed directly by casework. The maximum length substring of only 1's is then either entirely contained within the children, or it must span the non-leaf node, in which case it uses the maximal suffix of the left child and the maximal prefix of the right child.

For the update, imagine that we have a BBST that corresponds to exactly the given string. We flip a lazy reverse flag on the node. If we ever need to propagate the reverse later on, we swap the left and right children of the root node and flip the reverse flags on the children. We also need to flip the prefix and suffix lengths for the node.


Comments

There are no comments at the moment.