Overview

For each light, this problem asks you to determine the final ON/OFF state based on the initial state and the number of times the switch is pressed. The answer is determined by focusing only on the parity of the number of switch presses.

Analysis

Key Insight: Only the Parity of Switch Presses Matters

Pressing the switch once toggles the state. Pressing it once more returns it to the original state. In other words:

• Pressing an even number of times → the state remains the same (the toggles cancel each other out)
• Pressing an odd number of times → the state is the same as toggling exactly once

Let’s verify with a concrete example. For a light whose initial state is ON:

Number of presses \(K\)	State transitions	Final state
1	ON → OFF	OFF
2	ON → OFF → ON	ON
3	ON → OFF → ON → OFF	OFF
4	ON → OFF → ON → OFF → ON	ON

As we can see, an even number of presses results in the same state as the initial state, and an odd number results in the opposite of the initial state.

Why a Naive Approach Would Result in TLE

\(K_i\) can be as large as \(10^9\). If we actually simulate pressing the switch \(K_i\) times, a single light alone would require \(10^9\) operations, which is far too slow.

Solution

From the above insight, instead of using the value of \(K_i\) itself, we only need to check \(K_i \mod 2\) (whether it is even or odd), allowing us to determine the final state of each light in \(O(1)\).

Algorithm

For each light \(i\), do the following:

1. Read the initial state \(S_i\) and the number of switch presses \(K_i\).
2. If \(K_i\) is even, the state does not change, so output \(S_i\) as is.
3. If \(K_i\) is odd, the state is toggled, so output No if \(S_i\) is Yes, and Yes if \(S_i\) is No.

Complexity

• Time complexity: \(O(N)\) — performing an \(O(1)\) determination for each of the \(N\) lights
• Space complexity: \(O(1)\) — each light’s information is processed on the fly, with no need to store everything at once

Implementation Notes

• The input is read using split() to separate the string \(S_i\) and the integer \(K_i\). Since \(K_i\) is read as a string, don’t forget to convert it using int().

• Although \(K_i\) can be as large as \(10^9\), Python’s integers have arbitrary precision, so there is no concern about overflow.

• Parity checking can be written concisely as k % 2 == 0.

  Source Code

N = int(input())
for _ in range(N):
    s, k = input().split()
    k = int(k)
    if k % 2 == 0:
        print(s)
    else:
        print("No" if s == "Yes" else "Yes")

---

This editorial was generated by claude4.6opus-thinking.