Ranom Numbers
Contest: Educational Codeforces Round 150 (Rated for Div. 2)
Difficulty rating: 1800
Tags: brute force, dp, greedy, math, strings

No, not "random" numbers.

Ranom digits are denoted by uppercase Latin letters from A to E. Moreover, the value of the letter A is $$$1$$$, B is $$$10$$$, C is $$$100$$$, D is $$$1000$$$, E is $$$10000$$$.

A Ranom number is a sequence of Ranom digits. The value of the Ranom number is calculated as follows: the values of all digits are summed up, but some digits are taken with negative signs: a digit is taken with negative sign if there is a digit with a strictly greater value to the right of it (not necessarily immediately after it); otherwise, that digit is taken with a positive sign.

For example, the value of the Ranom number DAAABDCA is $$$1000 - 1 - 1 - 1 - 10 + 1000 + 100 + 1 = 2088$$$.

You are given a Ranom number. You can change no more than one digit in it. Calculate the maximum possible value of the resulting number.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) consisting of uppercase Latin letters from A to E — the Ranom number you are given.

The sum of the string lengths over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the maximum possible value of the number, if you can change no more than one digit in it.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, you can get EAAABDCA with the value $$$10000-1-1-1-10+1000+100+1=11088$$$.

In the second example, you can get EB with the value $$$10000+10=10010$$$.

Example input:
4
DAAABDCA
AB
ABCDEEDCBA
DDDDAAADDABECD

Example output:
11088
10010
31000
15886

Editorial:
There are two main solutions to this problem: dynamic programming and greedy.
DP approach
Reverse the string we were given, so that the sign of each digit depends on the maximum digit to the left of it (not to the right). Then, run the following dynamic programming: $$$dp_{i,j,k}$$$ is the maximum value of the number if we considered $$$i$$$ first characters, applied $$$k$$$ changes to them ($$$k$$$ is either $$$0$$$ or $$$1$$$), and the maximum character we encountered so far was $$$j$$$ ($$$j$$$ can have $$$5$$$ possible values). The transitions are fairly simple: when we consider the state $$$dp_{i,j,k}$$$, we can either leave the current character as it is, or, if $$$k = 0$$$, iterate on the replacement for the current character and use the replacement instead (then we go to the state with $$$k=1$$$). Note that this solution can also work if we can make more than one operation. This dynamic programming has $$$O(n \cdot A \cdot m)$$$ states (where $$$A$$$ is the number of different characters, and $$$m$$$ is the maximum number of changes we can make), and each state has no more than $$$A+1$$$ outgoing transitions. In this problem, $$$A = 5$$$ and $$$m = 1$$$, so this solution easily passes.
Greedy approach
Of course, we can try to iterate on every character and check all possible replacements for it, but quickly calculating the answer after replacement can be a bit difficult. Instead, we claim the following: it is optimal to consider at most $$$10$$$ positions to replace — the first and the last position of A, the first and the last position of B, and so on. That way, we have only $$$50$$$ different candidates for the answer, and we can check each of them in $$$O(n)$$$.
How to prove that this is enough? When we replace a character, we either increase or decrease it. If we increase a character, it's easy to see why it's optimal to try only the first occurrence of each character — increasing a character may affect some characters to the left of it (turn them from positive to negative), and by picking the first occurrence of a character, we make sure that the number of characters transformed from positive to negative is as small as possible. Note that if the string has at least one character different from E, we can replace the first such character with E and increase the answer by at least $$$9000$$$ (this will be useful in the second part of the proof).
Now suppose it's optimal to decrease a character, let's show that it's always optimal to choose the last occurrence of a character to decrease. Suppose we decreased a character, and it was not the last occurrence. This means that this character will be negative after replacement, so it should be negative before the replacement. The maximum value we can add to the answer by replacing a negative character with another negative character is $$$999$$$ (changing negative D to negative A), and we have already shown that we can add at least $$$9000$$$ by replacing the first non-E character in the string with E. So, if we decrease a character and it was not the last occurrence of that character, it's suboptimal.