PROBLEM LINK:
Setter: Lewin Gan
Tester: Radoslav Dimitrov
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
Hard
PREREQUISITES:
properties of binary trees, observations
PROBLEM:
Given a binary tree whose vertices are labelled with inorder traversal indices.
pseudocode to label vertices
integer index = 1
function dfs(node n):
if n has left_child:
dfs(n.left_child)
n.label = index
index += 1
if n has right_child:
dfs(n.right_child)
run dfs(root)
subtree of node x can be described by two integers a_x and b_x in the following way: the nodes a_x,a_x+1,…b_x all belong to the subtree of node x and all other nodes do not belong to this subtree.
We want to reconstruct the tree by asking queries of the form “x l r” (lets use query(x,a,b) to represent a query below), it returns true if a_x=l and b_x =r otherwise false.
EXPLANATION
Lets call a parent p of vertex x right parent of x if x is a right child of p. (Similarly we will call y a right ancestor of x if x lies in the right child’s subtree of y). Similar notion for left parent and left ancestor also. Lets call z first left ancestor of x if z is the deepest left ancestor (first occuring left ancestor on path from x to root) of x.
One example of a tree structure labelled using above pseudocode.
vertices with
1 as first left ancestor : \{\} , a_1=1,b_1=1
2 as first left ancestor : \{1\} , a_2=1,b_2=3
3 as first left ancestor : \{\} , a_3=3,b_3=3
4 as first left ancestor : \{2,3\} , a_4=1,b_4=7
5 as first left ancestor : \{\} , a_5=5,b_5=5
6 as first left ancestor : \{5\} , a_6=5,b_6=7
7 as first left ancestor : \{\} , a_7=7,b_7=7
8 as first left ancestor : \{4,6,7\} , a_8=1,b_8=10
9 as first left ancestor : \{\} , a_9=9,b_9=10
10 as first left ancestor : \{\} , a_{10}=10,b_{10}=10
vertices with no left ancestor at all : \{8,9,10\}
Claim 1: Let the first left ancestor of x be y. Then b_x = y-1.
Proof: After the inorder traversal of right subtree of x, the first vertex we visit will be y (because as long as its in the right subtree we just return to the parent and when in its in left subtree we go to that vertex and give next possible index to it). Also with this, we can see that x \lt y because y is given index after x.
Claim 2: If x does not have left child, then a_x=x.otherwise let left child of x be y, a_x = a_y.
Proof: If x does not have left child, only its right child subtree are its descendants which are all visited after x. Hence a_x=x.
If y is left child of x. then left child subtree are the only descendants of x which are visited before x. So smallest index of vertex in subtree of y will be a_x which is nothing but a_y.Hence a_x=a_y.
First I will describe the algorithm and then prove its correctness.
I will describe each of the variables in the loop when loop is entered for i=8 and i=6
Algorithm :
vector<int> vec;
stack<int> st;
// st contains all the vertices whose parent is not found
// in decreasing order i.e its topmost element will be highest.
for(i=1;i<n+1;i++){
vec.clear();
// when i =8,st will be {4,6,7} (7 is the top of the stack)
//when i=6, st = {4,5} {5 is top of the stack}
while(!st.empty() && query(st.top(),a[st.top()],i-1)){
// when i=8,we will enter loop in the order of 7,then 6 and then 4 from the stack.
// when i 6, we will enter only for 5 from the stack.
// we will enter here only for vertices whose first left
//ancestor is i. Also we will enter the loop
//in highest to lowest order i.e its left
//child's rightmost descendant, and then its parent
// and so on till left child of i.
vec.pb(st.top());
st.pop();
}
// when i=8, vec will be {7,6,4}
// when i=6, vec will be {5}
int siz=vec.size();
for(j=0;j<siz-1;j++){
par[vec[j]]=vec[j+1];
// since the next vertex will be parent of this vertex,
// we are assigning them.
}
if(!vec.empty()){
par[vec[siz-1]]=i;
//if i has left child, we are assigning a[i] from the left child.
a[i]=a[st.top()];
}
else{
// if i does not have left child
a[i]=i;
}
// adding i to stack.
st.push(i);
}
// finally we will be left in stack with root, root's right child, right child of root's
// right child,.... and so on till rightmost element of the tree (i.e element with index
// n) because these are the elements with no left ancestor.
// After exiting loop , st = {8,9,10} (10 is top of the stack)
Claim 3: We will find parent of each vertex before we add its first left ancestor to the stack. Also we will assign correct a array value for each vertex before adding it to stack.
Proof: Proof by induction.
When 1st vertex is added, we assign a_1 = 1 (which is the smallest possible index hence it must be a_1).From claim 1 all such vertices for which 1 is first left ancestor must have index less than 1. Hence, 1 is not first left ancestor of any vertex. Hence, parents of all such vertices are assigned trivially.
Now, that we proved base case.
Lets say at some instant when i has to be added, stack contains all the vertices for which their first left ancestor is still not iterated over and also for all the vertices in the stack we assume their a array values are assigned correctly. Now, lets see what are the vertices that will have i as their first left ancestor. they will be i's left child, right child of i's left child, and so on. Also, these are the only vertices, since any other vertex in i's left child subtree will meet a left ancestor before reaching i. So now query(x,ax,i-1) will be true for all such vertices. Also these vertices are iterated just before vertex i. since its left subtree is just visited before i is visited. Hence, they will have index values greater than other elements in the stack. So iterating in stack from highest to lowest will give us the all such vertices in the order mentioned in the algorithm before some element for which we fail the condition. Now we assign parents to all such vertices. Also to the left child of i. Now from claim 2, using a value of left child of i (if exists), we can assign a value of i otherwise a_i=i.
Hence, we assigned parent to all vertices who have their first left ancestor iterated. Also assigned correct value of a_i.Hence above claim is true.
Hence, above algorithm finally ends up with stack having vertices not having a left ancestor which will be root, root’s right child, right child of root’s right child and so on… in this order. So we can assign parents for them by iterating the stack finally. And root will be last(bottom most) element in the stack.
TIME COMPLEXITY
while adding each vertex, we do atmost one false query. Hence, a total of atmost n false queries because of n elements being added to the stack.
whenever a query is true, we remove a vertex from stack, since there can be atmost n removals. Hence, a total of atmost n true queries.
Therefore a total of atmost 2*n queries.
Regarding time complexity, all the operations inside the while are O(1). And while loop is entered only when query returns true, Hence O(n) times. Hence, total complexity is O(n).
SOLUTIONS:
Setter's Solution
import sys
t = int(raw_input())
c = {}
def ask(x,l,r):
if (x,l,r) in c:
return c[x,l,r]
print "Q",x+1,l+1,r+1
sys.stdout.flush()
ans = raw_input()
c[x,l,r] = (ans == "Yes")
return c[x,l,r]
for __ in xrange(t):
n = int(raw_input())
c.clear()
left = [-1 for __ in xrange(n)]
right = [-1 for __ in xrange(n)]
lb = [i for i in xrange(n)]
rb = [i for i in xrange(n)]
parent = [-1 for __ in xrange(n)]
stack = []
proot = -1
for i in xrange(n):
if proot != -1:
parent[proot] = i+1
left[i] = proot
lb[i] = lb[proot]
proot = -1
stack.append(i)
while len(stack) > 1 and ask(stack[-2], lb[stack[-2]], rb[stack[-1]]):
parent[stack[-1]] = stack[-2] + 1
right[stack[-2]] = stack[-1]
rb[stack[-2]] = rb[stack[-1]]
stack.pop()
if len(stack) > 0 and ask(stack[-1], lb[stack[-1]], rb[stack[-1]]):
proot = stack.pop()
print "A", " ".join(map(str, parent))
sys.stdout.flush()
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
bool query(int x, int l, int r)
{
cout << "Q " << x << " " << l << " " << r << endl << flush;
string ret;
cin >> ret;
return ret == "Yes";
}
int n;
void read()
{
cin >> n;
}
int par[MAXN];
int L[MAXN];
void solve()
{
for(int i = 1; i <= n; i++)
par[i] = -1;
vector<int> st;
for(int i = 1; i <= n; i++)
{
L[i] = i;
int last_on_slope = -1;
// while "i" is NOT in the subtree of st.back()
while(!st.empty() && query(st.back(), L[st.back()], i - 1))
{
// Recalculate the leftmost child of "i"
L[i] = L[st.back()];
if(last_on_slope != -1) par[last_on_slope] = st.back();
last_on_slope = st.back();
st.pop_back();
}
if(last_on_slope != -1) par[last_on_slope] = i;
st.pb(i);
}
int last_on_slope = -1;
while(!st.empty())
{
if(last_on_slope != -1) par[last_on_slope] = st.back();
last_on_slope = st.back();
st.pop_back();
}
cout << "A ";
for(int i = 1; i <= n; i++)
cout << par[i] << " \n"[i == n];
cout << flush;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T--)
{
read();
solve();
}
return 0;
}
Editorialist's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int query(int x,int a,int b){
cout<<"Q "<<x<<" "<<a<<" "<<b<<endl;
fflush(stdout);
string str;
cin>>str;
if(str[0]=='Y')
return 1;
return 0;
}
int par[12345];
int lef[12345];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
int t1=t;
while(t--){
int n;
cin>>n;
int i,j;
f(i,1,n+1){
lef[i]=i;
par[i]=-1;
}
vi vec;
stack<int> st;
f(i,1,n+1){
vec.clear();
while(!st.empty() && query(st.top(),lef[st.top()],i-1)){
vec.pb(st.top());
lef[i]=lef[st.top()];
st.pop();
}
int siz=vec.size();
rep(j,siz-1){
par[vec[j]]=vec[j+1];
}
if(!vec.empty()){
//cout<<"das"<<" "<<vec[siz-1]<<" "<<i<<endl;
par[vec[siz-1]]=i;
}
st.push(i);
}
vec.clear();
while(!st.empty()){
vec.pb(st.top());
st.pop();
}
int siz=vec.size();
rep(j,siz-1){
par[vec[j]]=vec[j+1];
}
cout<<"A ";
rep(j,n){
cout<<par[j+1]<<" ";
}
cout<<endl;
fflush(stdout);
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 