B - Shorten ARC Editorial by evima
In a contiguous substring of \(S\), we call a maximal string of the form A…ARC…C
a block. Also, we call the blocks in \(S\) Block \(1, 2, \ldots, M\) from left to right.
When no more operation is possible in a block, it has one of the forms A…AC…C
, R
, A…AR
, RC…C
. From this, we can see that an operation never combines multiple blocks into one.
The above observation allows us to rephrase the problem into the following, where \(X_i\) is \(\mathrm{min}\)(number of A
’s, number of C
’s).
You are given a sequence of positive integers \(X=(X_1,X_2,\ldots,X_M)\). At most how many times can the operation below be performed?
- In an odd-numbered operation, choose a positive element from \(X\) and decrease it by \(1\).
- In an even-numbered operation, choose a positive element from \(X\) and delete it.
We will consider this problem. It is easy to show the following: in an odd-numbered operation, it is optimal to choose the smallest element at least \(2\) if it exists; in an even-numbered operation, it is optimal to delete the smallest element.
This greedy strategy solves the problem in \(\mathrm{Ο}(N\log N)\) time.
We can also solve it in linear time. Let us consider an upper bound for the number of operations.
Since each even-numbered operation removes a positive element from \(X\), there can be at most \(2M\) operations. Also, since each operation decreases the sum of \(X\) at least \(1\), there can be at most \(\sum_i X_i\) operations.
Therefore, \(\mathrm{min}(2M, \sum_i X_i)\) is an upper bound for the number of operations, which turns out to be always achievable.
Thus, the problem is solved in \(\mathrm{Ο}(N)\).
posted:
last update: