Expert.
Put your skills to the test.

Problem summary

An unknown, uniformly random permutation a of0 through n−1 is fixed. A query supplies a permutation p of its original indices and receives the length of the longest strictly increasing subsequence of a[p[0]], …, a[p[n−1]]. Return the original index containing n−1. Queries do not modify a. This is a scored grader-library task: implement int find_maximum(int n), include lis.h, and call int get_lis_length(const std::vector<int>& p). Do not provide main or use standard input/output in the judge build. The complete listing includes an independently written optional LOCAL simulator; compile with -DLOCAL only for the displayed local input/output.

Source clarification. Read official A3_lis.zip author.cpp to verify the intended candidate-elimination method; no downloaded program was executed. Independent implementation and LOCAL oracle. Original n=3 communication is illustrative outside n≥8 scored constraints.

Constraints

8 ≤ n ≤200; T=5 judge calls; all hidden permutations of a given size equally likely. Subtasks: n=8 (5 points), n=20 (35), n=200 (60). All answers must be correct. For n=20 and n=200, query targets are2n² and2n respectively. At or below target the score fraction is1; otherwise0.9·(log(target)/log(q))^1.5, where q is the maximum query count in that test. No fixed full-score guarantee is claimed.

Worked example

Original LOCAL-simulator example: maximum value7 is at original index2. The original statement illustrates n=3 despite its scored constraints starting at8.

1
8
3 0 7 1 5 2 6 4

2

Solution analysis

1. Keep a permutation of original indices, not hidden values. Maintain a candidate suffix; every hidden value in the discarded prefix is smaller than every candidate. Initially the prefix is empty. Shuffle only the active suffix and query the baseline LIS length L. Randomization improves efficiency, not the correctness of comparisons.
2. For each active index except the last pivot, remove it and append it at the end. Retain indices whose move increases L. Let t be the smallest possible last hidden value of a length-L subsequence. Moving value v to the end increases L iff v>t: a length-L chain ending at t cannot contain v>t, so appending v extends it. Conversely, any new longer subsequence must end at v; removing it leaves an original length-L chain ending below v. The retained indices therefore form an upper interval of hidden values.
3. If the retained set is nonempty, it contains the maximum. Move discarded candidates and the old last pivot before the retained set, keeping the existing prefix intact. Every removed value is below every retained value, so the invariant survives. Continue with this strictly smaller suffix; sorting all values is unnecessary.
4. If nobody increases L, every longest subsequence in the active suffix ends at its maximum. Because all prefix values are smaller than all suffix values, full LIS is prefix-LIS plus suffix-LIS. Scan candidates from right to left, moving one to the beginning of the active suffix. An index after the maximum cannot be essential to a longest chain, so moving it cannot decrease L. Moving a maximum that is not first destroys every longest suffix chain and decreases L; this is the first decreasing probe. If no probe decreases L, the maximum is the first candidate.
5. Worked example: hidden active order [3,0,7,1,5,2,6,4] has L=4 and smallest possible terminal value t=4. Moving7,5,6 to the end increases L. Keep original indices [2,4,6], with hidden values [7,5,6], and place other indices first. Repeat the threshold test or finish with the essential-position scan. Return original index2, not hidden value7.
6. Trial vectors are independent copies. left marks the first active position, and every query still contains all n indices. The LOCAL oracle validates permutations and computes strict LIS using lower_bound on minimal tails. A fixed random seed makes demonstrations reproducible; the original input itself is uniformly random. This is a query-efficient interactive technique, not an offline LIS solver.

Why it works

The threshold argument proves that every nonempty retained set contains exactly the active hidden values above t, so it contains the maximum and preserves the prefix-smaller-than-suffix invariant. When none remains, every maximum-length suffix chain ends at the maximum. An index originally after that maximum leaves a longest chain intact when moved. If the maximum is not first, the suffix has a chain of length at least2; moving its maximum first reduces that optimum. Thus the rightmost decreasing probe locates it. If none decreases L, the maximum is first. Every continuing iteration strictly reduces the suffix size, guaranteeing termination and the correct original index.

Watch out. Use original zero-based indices. Every query must be a complete permutation. A move is erase-and-insert, not a swap. Compare with the unchanged iteration baseline. Never shuffle the discarded prefix. Submit without LOCAL and with lis.h. Query efficiency affects score separately from correctness.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<numeric>
#include<random>
#include<stdexcept>
#include<vector>
#ifndef LOCAL
#include"lis.h"
#else
int get_lis_length(const std::vector<int>&order);
#endif
using namespace std;
int find_maximum(int n){
    vector<int>order(n);
    iota(order.begin(),order.end(),0);
    mt19937 random(712367);
    int left=0;
    while(left+1<n){
        // Only the suffix can contain the maximum. Randomization saves queries.
        shuffle(order.begin()+left,order.end(),random);
        int baseline=get_lis_length(order);
        vector<int>candidates;
        vector<int>discarded;
        for(int position=left;position+1<n;++position){
            vector<int>trial=order;
            int moved=trial[position];
            trial.erase(trial.begin()+position);
            trial.push_back(moved);
            if(get_lis_length(trial)>baseline){
                candidates.push_back(order[position]);
            }
            else{
                discarded.push_back(order[position]);
            }
        }
        if(candidates.empty()){
            // The maximum belongs to every LIS. Locate its last essential position.
            for(int position=n-1;position>left;--position){
                vector<int>trial=order;
                int moved=trial[position];
                trial.erase(trial.begin()+position);
                trial.insert(trial.begin()+left,moved);
                if(get_lis_length(trial)<baseline){
                    return order[position];
                }
            }
            return order[left];
        }
        int pivot=order.back();
        int write=left;
        for(int index:discarded){
            order[write++]=index;
        }
        order[write++]=pivot;
        left=write;
        for(int index:candidates){
            order[write++]=index;
        }
    }
    return order.back();
}
#ifdef LOCAL
vector<int>hidden;
int calls=0;
int get_lis_length(const vector<int>&order){
    vector<int>seen(hidden.size());
    vector<int>tails;
    if(order.size()!=hidden.size()){
        throw runtime_error("Wrong query size");
    }
    ++calls;
    for(int index:order){
        if(index<0||index>=int(hidden.size())||seen[index]++){
            throw runtime_error("Query is not a permutation");
        }
        auto place=lower_bound(tails.begin(),tails.end(),hidden[index]);
        if(place==tails.end()){
            tails.push_back(hidden[index]);
        }
        else{
            *place=hidden[index];
        }
    }
    return int(tails.size());
}
int main(){
    int tests;
    cin>>tests;
    while(tests--){
        int n;
        cin>>n;
        hidden.resize(n);
        for(int&value:hidden){
            cin>>value;
        }
        calls=0;
        int position=find_maximum(n);
        if(hidden[position]!=n-1){
            throw runtime_error("Incorrect maximum");
        }
        cout<<position<<'\n';
        cerr<<"queries="<<calls<<'\n';
    }
}
#endif