Number of Distinct Numbers (Editorial)

Idea

We have a hidden array $a$ of length $n$. Each query is a permutation of indices, and in response we learn for each element how many of its neighbors (in our chosen order) have the same value. We need to find the number of distinct values in the array using at most \frac{n}{2} + 1 queries.

Key observation 1: recovering neighbor equalities

Suppose we made a query with some permutation and received array $b$. Let \text{eq}[i] = 1 if p_i = p_{i+1}, and $0$ otherwise. Then:

From this we can sequentially recover all $\text{eq}[i]$:

So from a single query we learn, for every pair of adjacent elements in our permutation, whether they have the same value in array $a$.

Key observation 2: covering all pairs

To fully determine which indices share the same value, every pair of indices $(i,j)$ must appear as neighbors in at least one query.

This is a classic round-robin tournament scheduling problem: $n$ players each play against every other, and in each round every player plays exactly one match. For even $n$ this requires n - 1 rounds, but we only need \frac{n}{2} rounds where each round gives a permutation whose adjacent pairs cover all needed pairs.

The construction works as follows: if $n$ is odd, pad to m = n + 1 (even). Then for each round k = 0, 1, \ldots, \frac{m}{2} - 1 build a permutation by starting with element $k$, then alternating elements k - 1, k + 1, k - 2, k + 2, \ldots, ending with element k + \frac{m}{2} (all indices taken modulo $m$; if an index is $\ge n$, skip it).

This gives exactly \frac{n}{2} (rounded up) queries, which fits within the limit of \frac{n}{2} + 1.

Merging results with DSU

We maintain a Disjoint Set Union (DSU) structure. After each query, if \text{eq}[i] = 1, we merge indices $q[i]$ and q[i+1] (where $q$ is our permutation). After all queries, the number of components in the DSU is the answer — the number of distinct values in the array.

Why is this correct?

Two indices $i$ and $j$ end up in the same DSU component if and only if a_i = a_j. If a_i = a_j, then in the query where they are neighbors we get \text{eq} = 1 and merge them. If a_i \neq a_j, they are never merged because in every query where they are neighbors \text{eq} = 0.

Transitivity is handled by the DSU: if a_i = a_j and a_j = a_k, all three end up in the same component even if the pair $(i,k)$ was never directly checked as neighbors.

Complexity

Number of queries: O\!\left(\frac{n}{2}\right).

Building permutations: O(n^2).

DSU with heuristics: O(n \cdot \alpha(n)) per query.

Overall: O(n^2), which runs fast for n \le 2 \cdot 10^3.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n = 0) {
        p.resize(n);
        sz.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int v) {
        return p[v] == v ? v : p[v] = find(p[v]);
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

vector<vector<int>> build_queries(int n) {
    int m = n + n % 2;
    vector<vector<int>> queries;
    for (int k = 0; k < m / 2; k++) {
        vector<int> q;
        auto add = [&](int x) {
            x = (x % m + m) % m;
            if (x < n) q.push_back(x);
        };
        add(k);
        for (int t = 1; t <= m / 2 - 1; t++) {
            add(k - t);
            add(k + t);
        }
        add(k + m / 2);
        queries.push_back(q);
    }
    return queries;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    DSU dsu(n);
    auto queries = build_queries(n);

    for (auto &q : queries) {
        cout << "? ";
        for (int i = 0; i < n; i++) {
            if (i) cout << ' ';
            cout << q[i] + 1;
        }
        cout << endl;

        vector<int> b(n);
        for (int i = 0; i < n; i++) cin >> b[i];

        if (n == 1) continue;

        vector<int> eq(n - 1);
        eq[0] = b[0];
        for (int i = 1; i < n - 1; i++)
            eq[i] = b[i] - eq[i - 1];

        for (int i = 0; i < n - 1; i++)
            if (eq[i] == 1)
                dsu.unite(q[i], q[i + 1]);
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
        if (dsu.find(i) == i) ans++;

    cout << "! " << ans << endl;
    return 0;
}