Problem 5 - Pairing Cards

We will discuss the solution to Pairing Cards from AIO 2025.

Solution

Subtask 1: S = 0 and N ≤ 1000

Since S = 0 and A_i ≥ 1 for all i, it is impossible for any pair to add to S in this subtask. All pairs must have a difference of D.

A card with a value of A_i could be paired with a value of either A_i - D or A_i + D and it's not clear which one we should choose. But if we instead look at the card with the smallest value (A₁) there is only one option to pair it with: A₁ + D (we can ignore A₁ - D because it has a smaller value which contradicts the fact that A₁ has the smallest value). If there is no card with value A₁ + D then we can output NO and stop our program. Otherwise, we pair A₁ with A₁ + D, remove these two cards, and repeat this process using the new smallest card.

Below is my code in Python and C++ for this subtask. I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck. Make sure your code works when D = 0 because this case can be tricky!

Python 3
C++

import sys

# N is the number of cards.
N = 0
# D and S are the allowed difference and sum of paired cards.
D = 0
S = 0

# A contains the values on the cards. Note that the list starts from 0, and so
# the values are A[0] to A[N-1].
A = []

# Read the values of N, D, S, and the values on the cards.
N, D, S = map(int, input().strip().split())
A = list(map(int, input().strip().split()))

while len(A) > 0:
  # pair A[0] with A[0]+D
  value = A[0]
  A.remove(value)
  if value+D not in A:
    print("NO")
    sys.exit(0) # this ends the program
  else:
    # A[0]+D from the list
    A.remove(value+D)
    
print("YES")

#include <cstdio>
#include <vector> // for std::vector
#include <algorithm> // for std::find

/* N is the number of cards. */
int N;
/* D and S are the allowed difference and sum of paired cards. */
int D;
int S;

std::vector<int> A;

int main(void) {
  /* Read the values of N, D, S, and the values on the cards. */
  scanf("%d%d%d", &N, &D, &S);
  for (int i = 0; i < N; i++) {
    int a;
    scanf("%d", &a);
    A.push_back(a);    
  }

  while (!A.empty()) {
    int value = A[0];
    A.erase(A.begin());
    auto it = std::find(A.begin(), A.end(), value+D);
    if (it == A.end()) {
      printf("NO\n");
      return 0;
    } else {
      A.erase(it);
    }
  }

  printf("YES\n");
}

Subtask 2: D = 0 and N ≤ 1000

In this subtask we can either pair equal values or values that add to S.

Assume for now that all values are distinct and so our only option is to pair values that add to S. In this case we don't need to make any pairing decisions: for each value A_i our only option is to pair it with a card of value S - A_i. This allows us to use code similar to subtask 1: we continuously try pairing cards until either we can't (so we print NO) or all the cards are paired (so we print YES).

When the values are not all distinct then we need to make a choice. For example, if there are two cards with value A_i = x we need to choose whether to pair them together or to pair them both with cards of value S - x. The first option (pair them together) is always optimal — try to prove it yourself and then read my proof.

Proof

We will use a type of proof called an exchange argument. In this proof style, we start with a solution that does not meet the criteria of our observation and we prove that we can change it so that it does meet our criteria.

Assume we did not pair the two cards together. Then, we paired the two cards of value x with two cards of value S - x. However, we could swap the pairs around so that the two x's are paired together and the two S - x's are also paired together.

Our solution is: first pair cards of equal value until no such pairs remain. Then, all remaining cards have distinct values and we can use the method described above.

Subtask 3 and Full Solution

In these subtasks each card has three options for what it could be paired with:

A_i + D,
A_i - D, and
S - A_i.

If we consider the smallest card (A₁) then similarly to subtask 1 we remove one of the options (A₁ - D) and so only two options remain: A₁ + D and S - A₁. If there are no cards with either of these values then it is impossible and we can print NO. If only one of these options appears on a card then we must do that pairing. Otherwise we can assume that there are cards with both values A₁ + D and S - A₁. We can greedily decide which one to pair A₁ with:

If S - A₁ = A_N, then we are allowed to pair the smallest and biggest values. Similarly to subtask 2 we can prove that this pairing is optimal using an exchange argument: if we did not pair A₁ with A_N then we must instead pair A₁ with A₁ + D and A_N with A_N - D (because A₁ is the smallest card and A_N is the largest card). However, since (A₁ + D) + (A_N - D) = A₁ + A_N = S, we can instead pair A₁ with A_N and A₁ + D with A_N - D.
Otherwise, if S - A₁ ≠ A_N then we know that S - A₁ < A_N (this is because A_N is the biggest card and so S - A₁ cannot be greater than A_N). In this case we do not know what to pair A₁ with. However, we do know what to pair A_N with. Specifically, we can rearrange S - A₁ < A_N to S - A_N < A₁ meaning that there is no card with value S - A_N. Therefore there is only one option for A_N: we must pair it with a card of value A_N - D.

We can repetitively apply this process until either a pairing is impossible or all cards are paired.

Depending on the time complexity of your solution it will pass either subtasks 1-3 or the full problem.

Two examples of this algorithm are shown below.

Click here to go back.