This blog does not introduce anything essentially new, though it may sound like it. This was previously discovered (and improved, generalized, etc.) here
Hello Codeforces,
Around a year ago, the problem Boardgame Expo was set in CEOI 2025. I think the editorial mentions using a DSU adapted to have deque-like undoing. Upon trying to actually upsolve this problem earlier this year, I remembered only that "deque-like undoing" was necessary, so I tried coming up with it. I'd actually note that the problem itself doesn't require the full range of deque-like operations, as the data structures only need to pop. So, the standard queue-like implementation works here, though with maybe some additional considerations.
So, realizing I've been duped, I decided to maybe publish this absolutely brilliant discovery with the world. I acknowledge that it is likely it is wrong.
The algorithm
One may wonder why queue-like doesn't work here. One may also be quick to realize that the push/pop operations that may occur on the same end of the deque are complements of each other, which, given queue-like works on amortized time complexity, means that one could repeatedly do the supposed amortized operations to result in quadratic time complexity.
My brilliant idea was the following:
In my view, though better implementations may not necessarily structure the code around this idea, the queue-like algorithm interweaves two stack-like structures with the following property:
- The stack is formed of multiple buckets
- Each bucket has a fixed capacity and it may never hold a partial amount of elements in it (i.e. they're either full or empty)
- The effective stack is represented as the read of the elements from the last bucket to the first
Queue-like then establishes a list of buckets as powers of two. It works because as you push elements on a stack elements' potential increases (up to $$$log$$$ per element, depending on index of bucket any element is from), and when, from the same stack, you start popping elements, the count of operations is limited by the total sum of potentials (you may not move an element further left than the number of buckets actually are left).
Illustration of the structure of the queue-like algorithm.
