Overview

\(N\) participants are standing in a line, and an “awkward handshake” occurs when the color of the “left person’s right hand” matches the color of the “right person’s left hand” for an adjacent pair. The problem asks us to find the total number of positions where such awkward handshakes occur.

Analysis

The key point for solving this problem is to accurately understand “which hand touches which hand.”

According to the problem statement, when participant \(i\) and participant \(i+1\) shake hands, the following two hands come into contact: - Participant \(i\) (left side)’s right hand: \(R_i\) - Participant \(i+1\) (right side)’s left hand: \(L_{i+1}\)

We need to check whether the colors of \(R_i\) and \(L_{i+1}\) match for all adjacent pairs (from \(i = 1\) to \(N-1\)).

For example, consider the case where three participants’ gloves are as follows: 1. Participant 1: Left \(L_1\)=N, Right \(R_1\)=S 2. Participant 2: Left \(L_2\)=S, Right \(R_2\)=S 3. Participant 3: Left \(L_3\)=N, Right \(R_3\)=N

• Handshake between participants 1 and 2: Compare \(R_1\)(S) and \(L_2\)(S) \(\rightarrow\) They are the same, so it’s awkward
• Handshake between participants 2 and 3: Compare \(R_2\)(S) and \(L_3\)(N) \(\rightarrow\) They are different, so it’s a good handshake

Since we only need to examine adjacent elements in order, this can be solved with a single loop. Although \(N\) can be up to \(2 \times 10^5\), this approach is well within the time limit.

Algorithm

1. Read the number of participants \(N\) and each participant’s glove colors \(L_i, R_i\) as input.
2. Initialize a variable awkward_count to 0 to count the number of awkward handshakes.
3. Repeat the following process for \(i = 1\) to \(N-1\):
   • Compare participant \(i\)’s right hand color \(R_i\) with participant \(i+1\)’s left hand color \(L_{i+1}\).
   • If the colors are the same, increment awkward_count by 1.
4. Output the final value of awkward_count.

Complexity

• Time complexity: \(O(N)\)
  • Since we check each of the \(N-1\) pairs exactly once, the computation finishes in time proportional to the number of participants.
• Space complexity: \(O(N)\)
  • When storing all inputs in a list or similar structure, memory proportional to the input size is used.

Implementation Notes

• Fast input: Since \(N\) can be large, in Python we can use sys.stdin.read().split() to read all input at once and process it efficiently.

• Index management: When obtaining input data as a flat list, we need to accurately calculate the positions in the list corresponding to participant \(i\)’s right hand \(R_i\) and participant \(i+1\)’s left hand \(L_{i+1}\).

  • In the provided code, the loop is structured so that tokens[2 * i] corresponds to \(R_i\) and tokens[2 * i + 1] corresponds to \(L_{i+1}\).

    Source Code

import sys

def solve():
    # 標準入力から全てのトークンを取得します。
    # sys.stdin.read().split() は大量の入力を高速に処理するのに適しています。
    tokens = sys.stdin.read().split()
    
    # 入力が空の場合の例外処理
    if not tokens:
        return
    
    # 参加者の人数 N
    n = int(tokens[0])
    
    # 気まずい握手の数をカウントする変数
    awkward_count = 0
    
    # 各参加者 i について、左手 L_i と右手 R_i の色は以下のように格納されています。
    # tokens[0] : N
    # tokens[1] : L_1, tokens[2] : R_1
    # tokens[3] : L_2, tokens[4] : R_2
    # ...
    # 一般に、参加者 i の右手 R_i は tokens[2 * i] に、
    # 参加者 i+1 の左手 L_{i+1} は tokens[2 * (i+1) - 1] = tokens[2 * i + 1] にあります。
    
    # i = 1 から N-1 までの隣り合うペアをチェックします。
    for i in range(1, n):
        # 参加者 i の右手 R_i
        r_i = tokens[2 * i]
        # 参加者 i+1 の左手 L_{i+1}
        l_next = tokens[2 * i + 1]
        
        # 手袋の色が同じであれば気まずい握手
        if r_i == l_next:
            awkward_count += 1
            
    # 結果を出力
    print(awkward_count)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.