Problem C — Moroccan Carpet Patterns

Game of Codes 4 · INSEA, Rabat, Morocco · February 08, 2026

This is one of the problems our team Hmama Miyта tackled during the contest. It turns out to be an elegant little problem hiding behind a beautiful cultural setting — Jihad, a master carpet weaver from the medina of Fes.

Problem Statement

Jihad creates Moroccan carpets represented as a sequence of $n$ colored tiles. A carpet pattern is called harmonious if it can be split into exactly two parts where both parts contain the same number of each color tile.

Given a carpet pattern, determine if it's harmonious.

Input

• First line: an integer $n$ where $2 \leq n \leq 100$ and $n$ is even — the number of tiles
• Second line: $n$ integers $a_1, a_2, \ldots, a_n$ where $1 \leq a_i \leq 100$ — the tile colors

Output

Print YES if the pattern is harmonious, NO otherwise.

Key Insight

This simplifies the problem dramatically. We don't need to think about how to partition — only whether the counts allow it.

Why is this equivalent?

Suppose every color $c$ appears $f_c$ times. For a valid split into two equal parts, each part must contain exactly $f_c / 2$ tiles of color $c$. This is only an integer when $f_c$ is even. Conversely, if all $f_c$ are even, such a split is always constructible:

Walkthrough of Examples

Solution

Complexity

• Time: $O(n)$ — one pass to count, one pass to check
• Space: $O(C)$ where $C = 100$ is the number of distinct possible colors

Implementation

from collections import Counter

n = int(input())
tiles = list(map(int, input().split()))

freq = Counter(tiles)

if all(count % 2 == 0 for count in freq.values()):
print("YES")
else:
print("NO")

Common Pitfalls

Reflection

This was a quick solve for us during the contest — a clean, satisfying problem that rewards reading carefully. The cultural framing around Moroccan carpet weaving gave it a lovely flavor that matched the INSEA setting perfectly.

Part of our Game of Codes 4 series — see the main article for the full contest recap.