Proficient.
Put your skills to the test.

Problem summary

A hidden permutation contains 1 through N. A query(A,B) reports whether the value at position A divides the value at position B. Return exactly the positions holding prime numbers while using few queries. Scoring depends continuously on the average query count over random permutations.

Source clarification. This is a scored query-minimization task on random permutations. The algorithm always returns the correct set; its randomized query efficiency does not guarantee the full-score average target.

Constraints

N=1,000 or N=10,000; 100 random permutations per test. Full-score average targets: 175,000 and 1,000,000 queries respectively.

Worked example

This is an interface transcript, not console input and output. Return order is arbitrary.

Hidden permutations: [1,2,3] and [2,3,1]; grader calls solve(3) separately.

Prime-position sets: {1,2} and {0,1}.

Solution analysis

1. First find the position of 1 in N−1 queries: keep candidate c, and replace it by i whenever query(i,c) is true. Once 1 appears it can never be replaced. Exclude it. Separately sieve the known integers 1 through N to obtain the total number π(N) of primes; this does not reveal any hidden positions.
2. Maintain unresolved positions A and confirmed prime positions B. Select a pseudorandom unresolved x and query every unresolved value to collect all its divisors, including x itself. Within this small divisor set, a value is prime exactly when no other member divides it. Identify every such prime divisor, add their positions to B, and remove all their multiples from A. Cache ordered query answers within one solve call to avoid asking the same question twice.
3. Every unresolved composite retains all of its prime divisors in A: if one had already been discovered, that composite would have been removed with its multiples. Therefore the divisor test inside A is complete. Stop as soon as |A|+|B| equals π(N); every remaining unresolved value must then be prime. This avoids spending the final quadratic cleanup on primes larger than N/2.
4. For hidden [1,2,3], the first pass finds position 0 as 1. The remaining two positions already equal π(3)=2, so return {1,2} without further questions. For [2,3,1], the candidate eventually moves to position 2 and returns {0,1}. Random selection affects query efficiency, never correctness. The implementation follows the full elimination strategy but does not promise maximum score for every permutation.

Why it works

The candidate pass retains 1 if encountered and switches to it when it is first encountered, so it finds 1. Inductively every unresolved composite has all its prime divisors unresolved, because any previously extracted prime would have removed it. Thus the collected unresolved divisors of x contain all prime divisors of every collected divisor; a collected divisor has no other divisor in the collection exactly when it is prime. Removing multiples of these primes cannot remove an undiscovered prime. Each iteration discovers at least one new prime and removes it, ensuring termination. Since every still-undiscovered prime remains unresolved, equality with the known total prime count proves that all residual candidates are primes. The returned positions are therefore exact for every permutation.

Watch out. Discard 1 before primality tests. Divisibility is directed. Never carry cache answers between hidden permutations. A scoring target is not a correctness bound or a guaranteed score.

Grader function only; declare and call the supplied query(A,B). The shown example describes the official two solve(3) calls and returned sets; it is not a standard-input/output protocol.

#include<vector>
#include<random>
#include<cstddef>
bool query(int A,int B);
std::vector<int>solve(int N){
    int one=0;
    for(int i=1;i<N;++i){
        if(query(i,one)){
            one=i;
        }
    }
    std::vector<bool>sieve(N+1,true);
    sieve[0]=false;
    sieve[1]=false;
    int primeCount=0;
    for(int i=2;i<=N;++i){
        if(sieve[i]){
            ++primeCount;
            for(int j=i+i;j<=N;j+=i){
                sieve[j]=false;
            }
        }
    }
    // Cache ordered questions; the permutation is fixed within this call.
    std::vector<unsigned char>cache(static_cast<std::size_t>(N)*N,0);
    auto divides=[&](int a,int b){
        if(a==b){
            return true;
        }
        auto&entry=cache[static_cast<std::size_t>(a)*N+b];
        if(entry==0){
            entry=query(a,b)?2:1;
        }
        return entry==2;
    };
    std::vector<int>alive,answer;
    for(int i=0;i<N;++i){
        if(i!=one){
            alive.push_back(i);
        }
    }
    std::mt19937 generator(712367821);
    while(static_cast<int>(alive.size()+answer.size())>primeCount){
        int selected=alive[generator()%alive.size()];
        std::vector<int>divisors;
        for(int candidate:alive){
            if(divides(candidate,selected)){
                divisors.push_back(candidate);
            }
        }
        std::vector<int>primes;
        for(int candidate:divisors){
            bool prime=true;
            for(int divisor:divisors){
                if(candidate!=divisor&&divides(divisor,candidate)){
                    prime=false;
                    break;
                }
            }
            if(prime){
                primes.push_back(candidate);
            }
        }
        std::vector<int>remaining;
        for(int candidate:alive){
            bool removed=false;
            for(int prime:primes){
                if(divides(prime,candidate)){
                    removed=true;
                    break;
                }
            }
            if(!removed){
                remaining.push_back(candidate);
            }
        }
        answer.insert(answer.end(),primes.begin(),primes.end());
        alive.swap(remaining);
    }
    answer.insert(answer.end(),alive.begin(),alive.end());
    return answer;
}