Overview

This is a problem where we count the number of times adjacent participants (\(i\) and \(i+1\)) shake hands and the glove colors that touch are the same — in other words, we count the number of pairs where \(R_i = L_{i+1}\).

Analysis

Since handshakes only occur between “adjacent pairs,” there are only \(N-1\) positions to check.
For each \(i=1,2,\ldots,N-1\), we examine:

• The right hand of the left person \(i\): \(R_i\)
• The left hand of the right person \(i+1\): \(L_{i+1}\)

If they match, it is “awkward,” so we increment the count.

For example, when \(N=4\), we check the following 3 positions:

• \((1,2)\): \(R_1\) and \(L_2\)
• \((2,3)\): \(R_2\) and \(L_3\)
• \((3,4)\): \(R_3\) and \(L_4\)

Checking all of these gives us the answer.

If we naively “check all pairs (\(N(N-1)/2\)),” we would examine non-adjacent pairs unnecessarily, resulting in \(O(N^2)\) time complexity, which is too slow for \(N \le 2\times 10^5\).
Since this problem only involves adjacent pairs, a single pass in \(O(N)\) is sufficient.

Algorithm

1. Read \(N\) and each participant’s \((L_i, R_i)\) from input.
2. For \(i=1\) through \(N-1\), compare \(R_i\) with \(L_{i+1}\).
3. If they match, increment the counter by \(+1\).
4. Output the counter.

Complexity

• Time complexity: \(O(N)\) (comparing each of the \(N-1\) adjacent positions once)
• Space complexity: \(O(N)\) (for storing \(L, R\) in arrays)

Implementation Notes

• Since the input can be up to \(2\times 10^5\) lines, using sys.stdin.buffer.read() for fast input in Python is recommended to be safe.

• The check is just a single line if R[i] == L[i+1]:, making it hard to introduce bugs.

• This problem can also be solved without storing arrays by “remembering the previous \(R_i\) and comparing it with the next \(L_{i+1}\)” (space \(O(1)\)). However, the provided code stores values in arrays for clarity.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    L = [None] * n
    R = [None] * n
    for i in range(n):
        L[i] = next(it).decode()
        R[i] = next(it).decode()

    ans = 0
    for i in range(n - 1):
        if R[i] == L[i + 1]:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.