PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: rivalq
Preparer: kugo
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
There is a hidden permutation P of length N. Find it using at most N-1 queries of the following type:
- Provide a permutation Q of length N to the judge.
- The judge will create the permutation \overline{P}, where \overline{P}_i = P_{Q_i}
- Then, the judge will return the set of prefix maximum positions of \overline{P}.
EXPLANATION:
If we are able to find N-1 elements of P, that automatically fixes the last element as well.
So, ideally we’d like to be able to find one new element with each operation we perform.
One simple observation that can be made is that the last prefix maximum will always be the position of N, since it’s the unique maximum of the permutation.
This allows us to easily find the position of N in P: use Q = [1, 2, 3, \ldots, N], and the last element of the prefix maximum returned is the position of N.
Now that we know where N is, we can choose exactly where to place it in \overline{P}.
In particular, suppose we set \overline{P}_N = N and permute the other elements in some way.
Then, the last element of the prefix maximums will be N, and the element before the last will be the position of N-1, since the first N-1 elements of \overline{P} essentially form a permutation of length N-1 on their own.
It’s easy to see that this process can be similarly repeated to find N-2, then N-3, and so on. That is,
- At the start of the i-th iteration, we know the positions of exactly i-1 elements, namely N, N-1, \ldots, N+2-i.
- Choose Q such that these i-1 elements form the suffix of \overline{P}, i.e, \overline{P} = [\ldots, N-2, N-1, N]
- The prefix maximum array of \overline{P} will have these i-1 positions as its last i-1 elements; and then the position of N+1-i in \overline{P} as the next one. With this information and Q, the position of N+1-i in P can be found.
In this way, we find the positions of N, N-1, N-2, \ldots, 2 in order; after which the position of 1 is known to us.
TIME COMPLEXITY
\mathcal{O}(N^2) per test case.
CODE:
Preparer's code (C++)
#include "bits/stdc++.h"
using namespace std;
typedef long long lol;
typedef std::pair<int,int> pii;
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fo(i,l,r,d) for (auto i=(l); (d)<0?i>(r):((d)>0?i<(r):0); i+=(d))
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
std::mt19937 rng (std::chrono::high_resolution_clock::now().time_since_epoch().count());
template <typename A, typename B> std::ostream& operator<< (std::ostream &cout, const std::pair<A, B> &p) { return cout << p.first << ' ' << p.second; } template <typename A, size_t n> std::ostream& operator<< (std::ostream &cout, const std::array<A, n> &v) { for (int i = 0; i < n - 1; ++i) cout << v[i] << ' '; return (n ? cout << v.back(): cout << '\n'); } template <typename A> std::ostream& operator<< (std::ostream &cout, const std::vector<A> &v) { for (int i = 0; i < v.size() - 1; ++i) cout << v[i] << ' '; return (v.size() ? cout << v.back(): cout << '\n'); }
template <typename A, typename B> std::istream& operator>> (std::istream &cin, std::pair<A, B> &p) { cin >> p.first; return cin >> p.second; } template <typename A, size_t n> std::istream& operator>> (std::istream &cin, std::array<A, n> &v) { assert(n); for (int i = 0; i < n - 1; i++) cin >> v[i]; return cin >> v.back(); } template <typename A> std::istream& operator>> (std::istream &cin, std::vector<A> &v) { assert(v.size()); for (int i = 0; i < v.size() - 1; i++) cin >> v[i]; return cin >> v.back(); }
template <typename A, typename B> auto amax (A &a, const B b){ if (b > a) a = b ; return a; }
template <typename A, typename B> auto amin (A &a, const B b){ if (b < a) a = b ; return a; }
void darling (const int kase) {
int n; cin >> n;
vector q(n, 0);
iota(all(q), 1);
fo(j, n, 1, -1) {
cout << "? " << q << endl;
int k; cin >> k;
if (k == -1)
exit(0);
vector v(k, 0);
cin >> v;
fo(c,0,n-j,1)
v.pop_back();
swap(q[v.back() - 1], q[j - 1]);
}
vector p(n, 0);
fo(i,0,n,1)
p[q[i] - 1] = i + 1;
cout << "! " << p << endl;
int verdict;
cin >> verdict;
assert(verdict == 1);
}
int main () {
ios_base::sync_with_stdio(0), cin.tie(0);
int t; cin >> t, assert(t >= 0);
for (int i = 0; t--; )
darling(++i);
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int32_t main()
{
int tc;
cin >> tc;
while(tc--)
{
int n;
cin >> n;
int p[n];
for(int i=0;i<n;i++)
p[i]=i;
int pos[n];
for(int i=n-1;i>0;i--)
{
cout << "? ";
for(int j=0;j<n;j++)
{
cout << p[j]+1 << " ";
}
cout << endl;
int k;
cin >> k;
int temp=0;
for(int j=0;j<k;j++)
{
int v;
cin >> v;
if(v<=i+1)
temp=max(temp,v-1);
}
pos[i]=p[temp];
swap(p[temp],p[i]);
}
int ans[n];
for(int i=0;i<n;i++)
ans[i]=0;
for(int i=1;i<n;i++)
ans[pos[i]]=i;
cout << "! ";
for(int i=0;i<n;i++)
cout << ans[i]+1 << " ";
cout << endl;
int verdict;
cin >> verdict;
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
ans = [1]*(n+1)
for i in range(n-1):
p = [0]*(n+1)
inv = [0]*(n+1)
ptr = 1
for j in range(1, n+1):
if ans[j] == 1:
p[ptr] = j
inv[j] = ptr
ptr += 1
else:
p[ans[j]] = j
inv[j] = ans[j]
print('?', *p[1:])
maxs = list(map(int, input().split()))
assert maxs[0] != -1
u = p[maxs[-1-i]]
ans[u] = n-i
print('!', *ans[1:])
assert int(input()) == 1