Overview

Count the number of “mismatched positions” between the current answer \(S\) and the correct answer \(T\), and determine the minimum number of rewrites needed to reduce the number of incorrect answers to at most \(K\).

Analysis

For each problem (each position \(i\)), there are only two possible relationships between \(S_i\) and \(T_i\):

• Match (\(S_i = T_i\)): This position is already correct.
  If we rewrite this position, it will necessarily become different from \(T_i\), which increases the number of incorrect answers by one — counterproductive to our goal (reducing incorrect answers).
  Therefore, to minimize the number of rewrites, it is always better to never rewrite this position.
• Mismatch (\(S_i \ne T_i\)): This position is incorrect.
  By rewriting it once to match \(T_i\), we can reduce the number of incorrect answers by one.

In other words, what we need to do is: - Count the number of mismatched positions (incorrect positions) \(m\) - Determine how many mismatches we need to fix to reduce the number of incorrect answers from \(m\) to at most \(K\)

To reduce the number of incorrect answers to at most \(K\): - If \(m \le K\), the condition is already satisfied, so 0 rewrites are needed - If \(m > K\), we need to fix \(m - K\) mismatches to reduce the incorrect count down to \(K\)
(Since each fix reduces the incorrect count by exactly 1, this is the minimum)

Therefore, the answer is: $\(\max(0,\, m - K)\)$

Concrete Examples

• When \(S=01010,\ T=01100\), there are 2 mismatched positions (\(m=2\))
  • If \(K=1\), we only need to fix \(m-K=1\) position → minimum 1 rewrite
  • If \(K=3\), then \(m \le K\) → minimum 0 rewrites

Algorithm

1. Compare \(S\) and \(T\) position by position and count the number of mismatched positions \(m\).
2. Output \(\max(0, m-K)\) as the answer.

Complexity

• Time complexity: \(O(N)\) (just comparing all positions once)
• Space complexity: \(O(1)\) (no large additional storage needed besides a counter)

Implementation Notes

• Since \(N \le 10^6\), a full scan in \(O(N)\) is more than fast enough, but since the input is large, using fast input methods like sys.stdin.buffer.read() is a safe choice.

• The implementation simply involves pairing the strings with zip(S, T) and counting mismatches.

• Use max(0, mismatches - K) to ensure the result does not become negative.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    K = int(data[1])
    S = data[2]
    T = data[3]

    mismatches = 0
    for a, b in zip(S, T):
        if a != b:
            mismatches += 1

    ans = mismatches - K
    if ans < 0:
        ans = 0
    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.