Guess the tree#11769

Guess the tree (Editorial)

Problem Author:	Illia Shevchenko
Prepared by:	Maksym Shvedchenko
Editorial by:	Maksym Shvedchenko

To determine the degree of a vertex $p_{i}$ p_i among the vertices $p_{1}, \dots, p_{i - 1}$ p_1, \dots, p_{i-1}, we can use a query. By leveraging the permutation and its reverse, we can compute the degree of each vertex.

Next, we iteratively identify a leaf, find its neighbor, and remove it from consideration. For any given leaf, based on multiple random permutations, we know that its neighbor must either be immediately to its left or right in at least one of these permutations. By intersecting these candidate sets across all permutations, we can uniquely identify the true neighbor.

If we use $q - 2$ q-2(2 queries was used to identify the degree) random permutations, the probability of incorrectly identifying a non-neighbor as the true neighbor decreases exponentially, specifically to $1/ 2^{q - 2}$ 1/2^{q-2}. Thus, with $q = 50$ q = 50, the probability of error becomes negligible.


#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 2011, inf = 1000111222;


int n;

inline vector <int> ask (vector <int> &p) {
    cout << "?";
    for (int i : p) {
        cout << ' ' << i + 1;
    }
    cout << endl;
    vector <int> res(n);
    for (int i = 0; i < n; i++) {
        cin >> res[i];
    }
    return res;
}


mt19937 rng(228);
template<typename T = int>
inline T randll(T l = INT_MIN, T r = INT_MAX) {
    return uniform_int_distribution<T>(l, r)(rng);
}

inline ld randld(ld l = INT_MIN, ld r = INT_MAX) {
    return uniform_real_distribution<ld>(l, r)(rng);
}

vector <int> edge[max_n];


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    vector <int> p(n);
    iota(all(p), 0);
    auto res1 = ask(p);
    reverse(all(p));
    auto res2 = ask(p);
    vector <int> deg(n);
    for (int i = 0; i < n; i++) {
        deg[i] += 1 - res1[i];
        if (i) {
            deg[i] += res1[i - 1];
        }
    }
    for (int i = 0; i < n; i++) {
        deg[i] += 1 - res2[n - i - 1];
        if (i + 1 < n) {
            deg[i] += res2[n - (i + 1) - 1];
        }
    }

    vector <vector <int> > query, gg;

    for (int i = 0; i < 48; i++) {
        shuffle(all(p), rng);
        gg.pb(p);
        query.pb(ask(p));
    }
    queue <int> q;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 1) {
            q.push(i);
        }
    }
    vector <pii> ans;
    vector <int> who(n), was(n);
    int timer = 0;
    for (int it = 0; it + 1 < n; it++) {
        int v = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            who[i] = i != v;
        }
        int y = 0;
        for (auto &x : query) {
            ++timer;
            for (int i = 0; i < n; i++) {
                if (v == gg[y][i]) {
                    int val = 1 - x[i];
                    if (i) {
                        val += x[i - 1];
                    }
                    for (int to : edge[v]) {
                        if (was[to] == timer) {
                            --val;
                        }
                    }
                    if (val == 0) {
                        for (int j = 0; j < i; j++) {
                            who[gg[y][j]] = 0;
                        }
                    }
                    else {
                        assert(val == 1);
                        for (int j = i + 1; j < n; j++) {
                            who[gg[y][j]] = 0;
                        }
                    }
                    break;
                }
                was[gg[y][i]] = timer;
            }
            ++y;
        }
        int pos = -1;
        for (int i = 0; i < n; i++) {
            if (who[i]) {
                assert(pos == -1);
                pos = i;
            }
        }
        ans.pb({pos, v});
        edge[pos].pb(v);
        edge[v].pb(pos);
        --deg[pos];
        if (deg[pos] == 1) {
            q.push(pos);
        }
    }
    cout << "!\n";
    for (auto &i : ans) {
        cout << i.first + 1 << ' ' << i.second + 1 << '\n';
    }
}