The Circle

Problem Statement Given n integers arranged in a circle, you can remove adjacent pairs whose sum is divisible by a given number k. When a pair is removed, the neighbors of the removed elements become adjacent. The goa...

Updated May 21, 2026

Track IOI

Year 1994

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

Given $n$ integers arranged in a circle, you can remove adjacent pairs whose sum is divisible by a given number $k$. When a pair is removed, the neighbors of the removed elements become adjacent. The goal is to remove as many elements as possible (or determine the order of removals).

Variant interpretation: In the IOI 1994 ``Circle'' problem, $n$ numbers are arranged in a circle. We must find the maximum number of elements we can remove by repeatedly removing adjacent pairs that sum to a multiple of $k$.

Constraints: $n \le 20$.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution Approach

Bitmask DP / Greedy with Backtracking

Given the small constraint ($n \le 20$), we can use a bitmask DP or backtracking approach:

Represent the remaining elements as a bitmask of $n$ bits.
For each state (bitmask), try all pairs of elements that are currently adjacent in the circle (considering removed elements) and whose sum is divisible by $k$.
Track the maximum number of elements removed.

Finding Adjacency in Current State

Given a bitmask, two elements $i$ and $j$ are adjacent in the current circle if there is no active element between them (wrapping around). We can find the next active neighbor of each element by scanning the bitmask.

Optimization

We use memoization on the bitmask. The number of distinct states is $2^n$, which for $n = 20$ gives about $10^6$ states --- feasible.

C++ Solution

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, k;
int a[21];
int memo[1 << 20];

// Find next active element after pos in circular order
int nextActive(int mask, int pos) {
    for (int step = 1; step < n; step++) {
        int nxt = (pos + step) % n;
        if (mask & (1 << nxt)) return nxt;
    }
    return -1; // no other active element
}

// Count of removed elements = n - __builtin_popcount(mask)
// We want to maximize removed, i.e., minimize remaining
int solve(int mask) {
    if (memo[mask] != -1) return memo[mask];

    int best = 0; // no more removals from this state
    int bits = __builtin_popcount(mask);
    if (bits < 2) return memo[mask] = 0;

    // Try each active element and its next neighbor
    for (int i = 0; i < n; i++) {
        if (!(mask & (1 << i))) continue;
        int j = nextActive(mask, i);
        if (j == -1 || j <= i) continue; // avoid double counting
        if ((a[i] + a[j]) % k == 0) {
            int newmask = mask & ~(1 << i) & ~(1 << j);
            best = max(best, 2 + solve(newmask));
        }
    }

    return memo[mask] = best;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    memset(memo, -1, sizeof(memo));
    int full = (1 << n) - 1;
    printf("%d\n", solve(full));
    return 0;
}

Complexity Analysis

Time complexity: $O(2^n \cdot n)$. There are $2^n$ possible bitmask states, and for each state we scan $O(n)$ elements to find adjacent pairs. For $n = 20$, this is about $20 \times 10^6$ operations.
Space complexity: $O(2^n)$ for the memoization table.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 1994 - The Circle
// Bitmask DP: remove adjacent pairs whose sum is divisible by k
// Time: O(2^n * n), Space: O(2^n), n <= 20
#include <bits/stdc++.h>
using namespace std;

int n, k;
int a[21];
int memo[1 << 20];

// Find next active element after pos in circular order
int nextActive(int mask, int pos) {
    for (int step = 1; step < n; step++) {
        int nxt = (pos + step) % n;
        if (mask & (1 << nxt)) return nxt;
    }
    return -1;
}

// Returns maximum number of elements removable from this state
int solve(int mask) {
    if (memo[mask] != -1) return memo[mask];
    if (__builtin_popcount(mask) < 2) return memo[mask] = 0;

    int best = 0;
    // Try each active element and its circular neighbor
    for (int i = 0; i < n; i++) {
        if (!(mask & (1 << i))) continue;
        int j = nextActive(mask, i);
        if (j == -1) continue;
        // Only try pair (i, j) where i < j to avoid double counting,
        // but allow the wrap-around pair (last active -> first active)
        if (j < i) continue;
        if ((a[i] + a[j]) % k == 0) {
            int newmask = mask & ~(1 << i) & ~(1 << j);
            best = max(best, 2 + solve(newmask));
        }
    }

    // Also try the wrap-around pair: the largest active index paired
    // with the smallest active index (which nextActive would find,
    // but we skipped it above with j < i check).
    // We need to handle this: find the smallest and largest active bits.
    int lo = -1, hi = -1;
    for (int i = 0; i < n; i++)
        if (mask & (1 << i)) { if (lo == -1) lo = i; hi = i; }
    if (lo != -1 && hi != lo && nextActive(mask, hi) == lo) {
        // (hi, lo) is an adjacent pair in the circle
        if ((a[lo] + a[hi]) % k == 0) {
            int newmask = mask & ~(1 << lo) & ~(1 << hi);
            best = max(best, 2 + solve(newmask));
        }
    }

    return memo[mask] = best;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    if (n <= 1 || k <= 0) {
        printf("0\n");
        return 0;
    }

    memset(memo, -1, sizeof(memo));
    int full = (1 << n) - 1;
    printf("%d\n", solve(full));
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/1994/circle/solution.texC++ implementationcompetitive_programming/ioi/1994/circle/solution.cpp