Codeforces Round #748 Changing Brackets Solution (Java/C++)

Solution:

First of all, according to the description of the problem, we can know that the direction of the brackets does not affect the result at all. So naturally, we only need to consider the parity of different types of brackets.

So we noticed that if there are an even number of round brackets between two adjacent square brackets (and vice versa), then there must be no cost. For example [(((([, the four round bracket in the middle can be paired with each other.
And we noticed that if there is an even number of round brackets between the two square brackets, then the parity of the index of the two square brackets must be opposite.
Conversely, if there are an odd number of round brackets between the two square brackets, at least a cost of 1.

Therefore, the number of square brackets on the odd digits and the square brackets on the even digits should correspond one-to-one, and each non-correspondence will require an operation.
Therefore, we use two prefixes sum to maintain the number of square brackets at odd positions and the number of square brackets at even positions. The final answer is the absolute value of the difference between the number of square brackets at odd positions and the number of square brackets at even positions in the interval.

Code:

Java

Submission #132180619 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #132180753 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge