 # ESCTRE - Editorial

Author: Hasin Rayhan Dewan Dhruboo
Tester: Raja Vardhan Reddy
Editorialist: William Lin

Easy-Medium

# PREREQUISITES:

Trees, Interactive

# PROBLEM:

There is a full binary tree with depth h and 2^{h+1}-1 nodes. The root is numbered 1 and the other nodes are numbered arbitrarily. There is a leaf node of this tree which is special and you need to find its number using at most 2h+1 of the following queries:

1. Given a node x, you will be given the distance of x to the special leaf node.
2. Given a node x and a distance y, you will be given some leaf node with distance y from x (or 0 if such leaf node doesn’t exist).

# QUICK EXPLANATION:

Find any leaf node u. Repeat the following h times: query the distance between u and the special leaf node, let it be d, and set u to the leaf node given by query 2 with node u and distance d.

# EXPLANATION:

Let the special leaf node be s.

First, we will find any leaf node u. To do this, we will ask a query of type 2 with x=1 (the root) and y=h (since all leaf nodes have distance h from the root).

Consider the following two steps:

1. Use query 1 to find the distance d between u and s.
2. Use query 2 to find any leaf node with distance d from u. Note that such a leaf node must exist (s is one possibility).

Before the two steps, u will be a leaf node, and after the two steps, u will become a new leaf node v.

The main observation is that if u is not s, then the distance from v to s must be at least 2 less than the distance from u to s. In other words, the distance from u to s will decrease by at least 2 when we perform these two steps. Also, if u is s, then v will still be s.

Proof

The distance from u and s is 2x for some integer x (go up x nodes from u, then go down x nodes to get to s). This means that the lowest common ancestor of u and s is the x-th ancestor of both u and s, and let that ancestor be w.

The distance from u to v is also 2x (because of how query 2 chooses v) and the lca of u and v is also w.

The tree is binary, so w has two children, w_1 and w_2. Without loss of generality, u comes from the subtree of w_1. This means that v and s come from the subtree of w_2 (otherwise w would not be the lca).

The depth of subtree w_2 is one less than the depth of subtree w, so the depth of subtree w_2 is x-1. This means that all distances within subtree w_2 (including the distance from v to s) have to be \le 2x-2, which completes the proof.

The maximum distance from any leaf node to any other leaf node is 2h. So, we just need to perform this combination of two steps h times and u will have a distance of 0 from s (and be s).

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;

int t;

int main()
{
cin >> t;
while(t--){
int h;
cin >> h;
if(h == -1) return 0;
printf("2 1 %d\n", h);
fflush(stdout);
int cur;
cin >> cur;
if(cur == -1) return 0;

while(true){
printf("1 %d\n", cur);
fflush(stdout);
int dst;
cin >> dst;
if(dst == -1) return 0;
printf("2 %d %d\n", cur, dst);
fflush(stdout);
cin >> cur;
if(cur == -1) return 0;
if(dst == 2) break;
}
printf("3 %d\n", cur);
fflush(stdout);
int tp;
scanf("%d", &tp);
if(tp == -1) return 0;
}

return 0;
}
``````
Tester's Solution
``````//raja1999

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#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)a; 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 int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//std::ios::sync_with_stdio(false);
int get2(int x,int y){
int d;
cout<<"2 "<<x<<" "<<y<<endl;
cin>>d;
return d;
}
int get1(int x){
int d;
cout<<"1 "<<x<<endl;
cin>>d;
return d;
}
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
//t=1;
while(t--){
int h,x,d,c=0;
cin>>h;
x=get2(1,h);
c++;
while(1){
d=get1(x);
c++;
if(c>2*(h+1)){
assert(0);
}
if(d==0){
cout<<"3 "<<x<<endl;
cin>>x;
break;
}
x=get2(x,d);
c++;
if(c>2*(h+1)){
assert(0);
}
if(d==2){
cout<<"3 "<<x<<endl;
cin>>x;
break;
}
}

}
return 0;
}
``````
Editorialist's Solution
``````#include <bits/stdc++.h>
using namespace std;

void solve() {
//input
int h;
cin >> h;

int u, a;
//find random leaf
cout << "2 1 " << h << endl;
cin >> u;
for(int i=0; i<h; ++i) {
//repeat process to decrease distance
cout << "1 " << u << endl;
cin >> a;
cout << "2 " << u << " " << a << endl;
cin >> u;
}
cout << "3 " << u << endl;
cin >> a;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

int t;
cin >> t;
while(t--)
solve();
}
``````

Please give me suggestions if anything is unclear so that I can improve. Thanks 5 Likes

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

I did the same thing where am I going wrong? Thanks

Same solution here. Didn’t pass, don’t know why

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

``````t = int(input())
for _ in range(t):
h = int(input())
print(2, 1, h)
leaf = int(input())
for i in range(h):
print(1, leaf)
dist = int(input())
if dist == 0:
print(3, leaf)
break
print(2, leaf, dist)
leaf = int(input())``````

Asking the last distance 0 query is not required and in the worst case gives 2h+2 queries. So break the while loop before getting 0 as the distance like in the editorial

There where no such tests where the random leaf reported in the very first query is a special node itself. Maybe @ezio_26 should add it in practice. Btw nice problem !!

Isnt it possible that we get the special node before we get a leaf node whose distance from special node is 2. In that case,setter solution wont be correct, right?

Here, we have to check that if(dist==0), then break the loop?

1 Like

I added this line, so we don’t need to check if u is already the special node

unexpectedly easy!!

Hi William,
Noob this side,

My code is almost same as urs but i don’t know why am getting WA.
Can u please have a look into my code,
https://www.codechef.com/viewsolution/30723328