Learning Park Directions with XOR Queries
Autumn Tournament (2018)
Submission name: park.cpp
Problem summary
A directed park graph has vertices 1..2N+2 and edges between labels differing by one or two. It is acyclic, with unique source 1 and unique sink 2N+2. Discover every edge direction by querying XORs of selected edge directions. A positive direction goes from the smaller label to the larger. The full-score target is at most ceil(16N/11) queries, including against an adaptive grader.
Input
This is a grader task, not a standard-input problem. Submit park.cpp including park.h and implement void run(int n). The grader provides bool get_xor(const vector<pair<int,int>>&) and void state_direction(const pair<int,int>&,bool). The LOCAL demonstration reads N then 4N+1 direction bits in order (1,2),(1,3),(2,3),(2,4),...,(2N+1,2N+2).
Output
Report every direction once through state_direction. Do not print a judge answer. The LOCAL driver prints its query count and all recovered bits in input order; this output is a demonstration only.
Constraints
1 ≤ N ≤ 100,000. More than 3N queries earns zero; the official scoring thresholds are 3N, 2N, ceil(3N/2), and ceil(16N/11). This implementation targets the final, full-score threshold.
Worked example
An independently prepared valid example; output follows the implementation below.
Input
1 1 1 0 1 1
Output
1 1 1 0 1 1
Solution analysis
- First use the park restrictions, not a general graph-learning algorithm. Peeling the consecutive triangles from the source shows that every difference-two edge points forward. The first and last difference-one edges also point forward. Among the consecutive difference-one edges, two neighboring negative directions would form a directed triangle with a forward difference-two edge, so the unknown bits contain no consecutive zeros.
- Group the remaining 2N consecutive-edge bits into blocks of length 11. A valid length-l block has F(l+2) possible patterns, because it either begins with 1 followed by a valid shorter block, or begins with 01 followed by one two bits shorter. For length 11 there are only 233 possibilities, so eight binary answers could distinguish them. The important additional requirement is that each question must be a parity of selected positions.
- The Decoder constructs and verifies a small parity decision tree. At each node enumerate all nonempty query masks, partition the remaining patterns by parity, and consider the most balanced partitions first. Reject a split with more than 2^(remaining depth−1) candidates in a child, recursively requiring successful children. The finite search succeeds for every length 1..11; for length 11 the maximum depth is eight. The resulting tree is built once and reused for every full block.
- At runtime, translate each decision mask into its difference-one edges, ask get_xor, follow the corresponding child, and report the unique leaf pattern. The decision process works even with an adaptive grader: after every answer, all still-possible valid patterns lie in exactly the selected child. For the tail of length l≤10, depths for l=1..10 are 1,2,3,3,4,5,6,6,7,8; each is at most ceil(8l/11). Hence total queries are at most ceil(16N/11).
- Worked example N=1: edges (1,3),(2,4),(1,2) are positive. The two remaining consecutive edges (2,3),(3,4) form a no-00 block. For input 0,1 the first decision asks the first bit and receives 0. Because 00 is forbidden, this immediately identifies 01 in one query; other branches may require two. The local driver reports both recovered bits and checks all five edge reports.
Why it works
The graph restrictions imply the forced directions and no-00 condition. Each internal decision node partitions its candidate set exactly by an allowed parity query; a successful recursively constructed tree therefore identifies every possible block. Exhaustive finite construction covers all valid blocks of lengths up to eleven and enforces the stated depth limits. Summing eight queries per full block and the verified tail depths gives the full-score bound. Ignoring constraints across block boundaries only adds harmless candidates; it cannot remove the real pattern.
Watch out. Do not submit the LOCAL main function to the judge. Query and report genuine park edges only, and report directions relative to increasing labels even if pair endpoints are supplied reversed. Merely asking each unknown bit separately misses the full-score query limit. The finite decision-tree generation must retain its recursive success check, not assume that any balanced split will work.
Commented C++17 solution
Official grader implementation uses park.h and has no main. Compile with -DLOCAL for the included independent local protocol driver, which checks reported directions and the full-score query budget.
#include<algorithm>
#include<iostream>
#include<map>
#include<numeric>
#include<stdexcept>
#include<utility>
#include<vector>
#ifndef LOCAL
#include"park.h"
#else
using Edge=std::pair<int,int>;
std::map<Edge,bool>hidden,reported;
int queries=0;
bool get_xor(const std::vector<Edge>&edges){
++queries;
bool result=false;
for(auto edge:edges){
if(edge.first>edge.second){
std::swap(edge.first,edge.second);
}
if(!hidden.count(edge)){
throw std::runtime_error("Invalid queried edge");
}
result^=hidden.at(edge);
}
return result;
}
void state_direction(const Edge&original,bool direction){
Edge edge=original;
if(edge.first>edge.second){
std::swap(edge.first,edge.second);
}
if(!hidden.count(edge)||hidden.at(edge)!=direction||reported.count(edge)){
throw std::runtime_error("Incorrect or duplicate edge report");
}
reported[edge]=direction;
}
#endif
using namespace std;
int popcount(int value){
int result=0;
while(value){
value&=value-1;
++result;
}
return result;
}
struct Decision{
int query=0;
int zero=-1;
int one=-1;
int pattern=-1;
};
class Decoder{
vector<Decision>nodes;
int build(const vector<int>&possible,int depth,int length){
if(possible.size()==1){
nodes.push_back({0,-1,-1,possible[0]});
return static_cast<int>(nodes.size())-1;
}
struct Choice{
int worst,size,query;
bool operator<(const Choice&other)const{
if(worst!=other.worst){
return worst<other.worst;
}
if(size!=other.size){
return size<other.size;
}
return query<other.query;
}
};
vector<Choice>choices;
for(int query=1;query<(1<<length);++query){
int ones=0;
for(int pattern:possible){
ones+=popcount(pattern&query)%2;
}
int worst=max(ones,static_cast<int>(possible.size())-ones);
if(ones&&ones<static_cast<int>(possible.size())&&worst<=(1<<(depth-1))){
choices.push_back({worst,popcount(query),query});
}
}
sort(choices.begin(),choices.end());
for(const Choice&choice:choices){
vector<int>part[2];
for(int pattern:possible){
part[popcount(pattern&choice.query)%2].push_back(pattern);
}
size_t checkpoint=nodes.size();
int zero=build(part[0],depth-1,length);
if(zero==-1){
nodes.resize(checkpoint);
continue;
}
int one=build(part[1],depth-1,length);
if(one==-1){
nodes.resize(checkpoint);
continue;
}
nodes.push_back({choice.query,zero,one,-1});
return static_cast<int>(nodes.size())-1;
}
return -1;
}
int root,length;
public:
explicit Decoder(int size):length(size){
vector<int>possible;
for(int mask=0;mask<(1<<length);++mask){
int zeros=((1<<length)-1)^mask;
if((zeros&(zeros>>1))==0){
possible.push_back(mask);
}
}
int depth=0;
while((1<<depth)<static_cast<int>(possible.size())){
++depth;
}
root=build(possible,depth,length);
if(root==-1){
throw runtime_error("No parity decision tree within the proved bound");
}
}
int identify(int first)const{
int node=root;
while(nodes[node].pattern==-1){
vector<pair<int,int>>edges;
for(int bit=0;bit<length;++bit){
if((nodes[node].query>>bit)&1){
edges.emplace_back(first+bit,first+bit+1);
}
}
bool answer=get_xor(edges);
node=answer?nodes[node].one:nodes[node].zero;
}
return nodes[node].pattern;
}
};
void run(int n){
// All difference-two edges and the first difference-one edge are forced positive.
for(int u=1;u<=2*n;++u){
state_direction({u,u+2},true);
}
state_direction({1,2},true);
int remaining=2*n;
int first=2;
if(remaining>=11){
Decoder full(11);
while(remaining>=11){
int mask=full.identify(first);
for(int bit=0;bit<11;++bit){
state_direction({first+bit,first+bit+1},(mask>>bit)&1);
}
remaining-=11;
first+=11;
}
}
if(remaining!=0){
Decoder tail(remaining);
int mask=tail.identify(first);
for(int bit=0;bit<remaining;++bit){
state_direction({first+bit,first+bit+1},(mask>>bit)&1);
}
}
}
#ifdef LOCAL
int main(){
int n;
cin>>n;
vector<Edge>order;
for(int u=1;u<=2*n+1;++u){
for(int difference=1;difference<=2;++difference){
if(u+difference<=2*n+2){
Edge edge={u,u+difference};
bool direction;
cin>>direction;
hidden[edge]=direction;
order.push_back(edge);
}
}
}
run(n);
if(reported.size()!=hidden.size()||queries>(16*n+10)/11){
throw runtime_error("Incomplete report or query budget exceeded");
}
cout<<queries<<'\n';
for(size_t i=0;i<order.size();++i){
if(i){
cout<<' ';
}
cout<<reported.at(order[i]);
}
cout<<'\n';
}
#endif