ESCTRE - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

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

DIFFICULTY:

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 comment(linker, "/stack:200000000")
//#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;
	}
	//report answer
	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 :slight_smile:

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