GUESSPFMX - Editorial

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

I am doing exactly the same thing as mentioned in the editorial. Can anyone point out where my mistake is?

https://www.codechef.com/viewsolution/93375705

I need to test my code for this problem by submitting in the practice section. When will I be able to do so?
Submitting is currently disabled for this problem (or maybe for other interactive problems too). This is a bit annoying, given how long it has been since the judging system migration post. Can anyone please help?

Reference:

@iceknight1093 @admin

Putting my code here, just to be able to easily retrieve later.

Code
#include <bits/stdc++.h>

using namespace std;

inline vector<int> interact(const vector<int> &q) {
  cout << '?';
  for (const int x : q) {
    cout << ' ' << x;
  }
  cout << '\n';
  int k;
  cin >> k;
  vector<int> out(k);
  for (int &x : out) {
    cin >> x;
  }
  return out;
}

inline vector<int> solve(const int n) {
  vector<int> q(n);
  iota(q.begin(), q.end(), 1);
  for (int move = 1; move < n; move++) {
    const vector<int> &out = interact(q);
    const int i = out[(int) out.size() - move] - 1;
    q.insert(q.begin() + (n - move + 1), q[i]);
    q.erase(q.begin() + i);
  }
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    p[q[i] - 1] = i + 1;
  }
  return p;
}

int main() {
  int test_cases;
  cin >> test_cases;
  while (test_cases-- > 0) {
    int n;
    cin >> n;
    const vector<int> &p = solve(n);
    cout << '!';
    for (const int x : p) {
      cout << ' ' << x;
    }
    cout << '\n';
  }
  return 0;
}