Overview

This problem asks you to evaluate a mathematical expression given in Polish notation (prefix notation), and also to compute the result after flipping the operator at a specified position using +↔-, *↔/.

Analysis

Key Insight

In Polish notation, operators come first and operands come after, so scanning the token sequence from right to left makes processing straightforward.

• Scanning from the right, numbers (values of subexpressions) appear first and are pushed onto a stack
• When an operator appears, the top two elements of the stack are its operands
  (Since the form is op A B, reading from right to left means the values of \(A, B\) are already available)

For example, reading * + 3 5 2 from right to left:

• Push 2
• Push 5
• Push 3
• + appears, so compute \(3+5=8\) and push
• * appears, so compute \(8*2=16\) and push

The single value remaining on the stack is the answer.

Why the Naive Approach is Dangerous

If you “recursively parse and evaluate the expression” following the recursive definition, the recursion depth can be \(O(N)\) in the worst case, and with \(N \le 2\times 10^5\), there is a risk of recursion limit errors or stack overflow. Additionally, building an expression tree tends to be heavy in terms of memory and implementation.

Therefore, we evaluate in a single pass using iteration (loops) + a stack.

Handling the Flipped Expression

Since the flip positions \(p_i\) are given in the input:

• Prepare a boolean array flip of length \(N\), and set flip[p_i]=True
• During evaluation, if the token at that position is an operator, flip it before computing

This way, the flipped expression can be processed using the same evaluation logic.

Algorithm

1. Store the input token sequence t_1..t_N in an array.
2. From the set of flip positions \(\{p_i\}\), create the array flip (length \(N\)) (converting from \(1\)-indexed to \(0\)-indexed).
3. Evaluate using the function evaluate(tokens, flip):
   • Prepare an empty stack st
   • Iterate in reverse from \(i=N-1\) down to \(0\)
     • If tokens[i] is an operator (a single character matching +,-,*,/)

          - If necessary, flip the operator according to `flip[i]`
          - Pop `a=st.pop()`, `b=st.pop()`, compute `a op b`, and push the result
       

     • Otherwise, it is an integer, so push int(tokens[i])
   • Finally, st[0] is the value of the entire expression
4. Evaluate the original expression with flip=None and the flipped expression by passing flip, then output both results.

Truncated Division (Division Toward Zero)

Python’s // rounds toward negative infinity for negative numbers, which does not match the problem’s definition (truncation toward \(0\)).
Therefore: - Compute the absolute value of the quotient as abs(a)//abs(b) - Restore only the sign using (a<0) xor (b<0)

This implements \(a/b\) (truncated) as defined in the problem.

Complexity

• Time complexity: \(O(N)\) (a single evaluation is \(O(N)\), and doing this twice is still \(O(N)\) overall)
• Space complexity: \(O(N)\) (for the stack and the flip array; the flip array is not created when unnecessary)

Implementation Notes

• Checking whether a token is an operator must be done by verifying it is a single character that exactly matches one of +,-,*,/. For example, -3 is not an operator but an integer.

• In the right-to-left scan, the order of popping for operators is important: pop a=pop(), b=pop(), then compute a op b (to preserve the order of op A B).

• Division must always use tdiv(a,b); do not use Python’s // directly.

  Source Code

import sys

def tdiv(a: int, b: int) -> int:
    q = abs(a) // abs(b)
    return -q if (a < 0) ^ (b < 0) else q

def evaluate(tokens, flip):
    st = []
    for i in range(len(tokens) - 1, -1, -1):
        tok = tokens[i]
        if tok == b'+' or tok == b'-' or tok == b'*' or tok == b'/':
            op = tok
            if flip is not None and flip[i]:
                if op == b'+':
                    op = b'-'
                elif op == b'-':
                    op = b'+'
                elif op == b'*':
                    op = b'/'
                else:
                    op = b'*'
            a = st.pop()
            b = st.pop()
            if op == b'+':
                st.append(a + b)
            elif op == b'-':
                st.append(a - b)
            elif op == b'*':
                st.append(a * b)
            else:
                st.append(tdiv(a, b))
        else:
            st.append(int(tok))
    return st[0]

def main():
    data = sys.stdin.buffer.read().split()
    it = 0
    N = int(data[it]); it += 1
    tokens = data[it:it+N]; it += N
    K = int(data[it]); it += 1

    flip = None
    if K > 0:
        flip = [False] * N
        for j in range(K):
            p = int(data[it + j]) - 1
            flip[p] = True
        it += K

    ans1 = evaluate(tokens, None)
    ans2 = evaluate(tokens, flip)
    sys.stdout.write(f"{ans1}\n{ans2}\n")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.