Overview

This is a problem where we replace all ? with either R or W to minimize the absolute difference between the number of red votes and white votes, \(|R-W|\). We reduce it to simply deciding how many of the ? to assign as R (the rest become W).

Analysis

First, count the fixed votes:

• Number of R: \(r\)
• Number of W: \(w\)
• Number of ?: \(q\)

Now, suppose we interpret \(x\) of the ? as R and the remaining \(q-x\) as W. Then the final counts are:

• Red votes: \(r + x\)
• White votes: \(w + (q-x)\)

So the difference is [ (r+x) - (w+q-x) = (r-w) + 2x - q ] Therefore, the value we want to minimize is [ \left| (r-w) + 2x - q \right| ]

Key Insight

The expression above is the absolute value of a linear function in \(x\), so its graph is V-shaped, and the minimum is achieved “where the inner expression is closest to 0.” That is, we want to choose an integer \(x\) close to the solution of [ (r-w) + 2x - q = 0 ] Solving this gives [ x = \frac{q - (r-w)}{2} ]

However, since \(x\) must be an integer satisfying \(0 \le x \le q\):

• Check the floor and ceiling of the target value \(x^\* = \dfrac{q-(r-w)}{2}\) (in implementation, \(x1\) and \(x1+1\))
• Also check the endpoints (\(0\) and \(q\)) in case the target falls outside the valid range

This is sufficient.

(You could also brute-force over all \(x=0..q\), but this method guarantees finding the minimum by “checking just 4 candidates.”)

Algorithm

1. Count the numbers \(r, w, q\) of R, W, ? from the input.
2. If \(q=0\), the answer is simply \(|r-w|\).
3. Otherwise, define the difference function [ diff(x) = (r-w) + 2x - q ]
4. Consider the target [ x^* = \frac{q-(r-w)}{2} ] and in implementation, enumerate the candidates:
   • \(x1 = \left\lfloor x^\* \right\rfloor\)
   • \(x1+1\)
   • The endpoints \(0, q\)
5. Clamp each candidate \(x\) to \([0,q]\), and output \(\min |diff(x)|\) as the answer.

Complexity

• Time complexity: \(O(N)\) (counting takes \(N\) steps, candidate checking is constant time)
• Space complexity: \(O(1)\) (only counters)

Implementation Notes

• Verifying that the difference formula is always [ diff(x) = (r-w) + 2x - q ] helps reduce implementation mistakes.

• The optimal \(x\) is near \(\dfrac{q-(r-w)}{2}\), so to handle integer rounding, check both the floor and floor+1.

• Since \(x\) may fall outside the range \(0..q\), candidates must be clamped to \([0,q]\).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    r = w = q = 0
    for i in range(1, n + 1):
        s = data[i]
        c = s[:1]
        if c == b'R':
            r += 1
        elif c == b'W':
            w += 1
        else:
            q += 1

    if q == 0:
        print(abs(r - w))
        return

    num = q - (r - w)  # want x close to num/2
    x1 = num // 2
    candidates = {0, q, x1, x1 + 1}
    ans = 10**18
    for x in candidates:
        if x < 0:
            x = 0
        elif x > q:
            x = q
        diff = (r - w) + 2 * x - q
        ans = min(ans, abs(diff))
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.