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:
- Given a node x, you will be given the distance of x to the special leaf node.
- 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:
- Use query 1 to find the distance d between u and s.
- 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