INTREECTIVE2 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Satyam
Tester: Abhinav Sharma, Manan Grover
Editorialist: Lavish Gupta

DIFFICULTY:

Easy-Medium

PREREQUISITES:

You should be familiar with the concepts of Binary Search and Graph Traversal algorithms like Breadth First Search and Depth First Search

PROBLEM:

This problem is similar to the problem “INTREECTIVE”. The only difference between them is the number of queries allowed — in this problem, up to 11 queries can be made. In Div. 1 and Div. 2 this problem is worth 60 points and “INTREECTIVE” is worth 40. In Div. 3 this problem is non-scorable.

This is an interactive task

You are given a tree consisting of N nodes, numbered from 1 to N. Chef selected an arbitrary node and marked it.

Chef gave you a judge to play with, using which you can ask queries about the given tree.

In each query, you give the judge a non-empty set S of nodes. The judge returns 1 if there exists u and v(not necessarily distinct) such that u,v \in S and the marked node lies on the shortest path from u to v, or 0 otherwise.

You have to find the marked node.

For each test case, you can use at most 11 queries.

Constraints

  • 1 \le T \le 1000
  • 1 \le N \le 1000
  • The input graph is a tree
  • Sum of N does not exceed 5 \cdot 10^4 over all test cases
  • At most 11 queries can be made.

QUICK EXPLANATION

Because we have 1000 nodes, we can do one complete Binary Search on the nodes in 10 queries. We have 11 queries, so we can do only one Binary Search.

Also, let us consider Node 1 as the root node.

Solution 1

  • Let’s do a DFS on the tree starting at the node 1. As soon as we visit a node for the first time, we insert that node into an array arr.
  • Analyze this array arr. If we consider the shortest path from 1 to arr[i], then all the nodes that lie in that path are already present in the array as arr[j], such that j < i.
  • We can do a Binary Search on this array to find the marked node.

Solution 2

  • Let’s consider a component of the graph having N/2 nodes, such that for any two nodes (u, v) in this component, all the nodes that lie in the shortest path from u to v lies in this component.
  • Ask a Query in this component. If answer is Yes, we now have N/2 nodes to consider. Otherwise we can replace this component by a dummy node, and consider the new graph of N/2 + 1 nodes.

EXPLANATION:

Detailed Explanation will be added soon.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's Solution
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long  
const ll INF_MUL=1e13;
const ll INF_ADD=2e18;  
#define pb push_back               
#define mp make_pair        
#define nline "\n"                           
#define f first                                          
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()   
#define vl vector<ll>         
#define vvl vector<vector<ll>>    
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif     
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;} 
void _print(string x){cerr<<x;}     
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;   
const ll MAX=500500;  
void solve(){                  
    ll n; cin>>n;
    vector<ll> adj[n+5];
    set<ll> possible;
    for(ll i=1;i<n;i++){
        ll u,v; cin>>u>>v;
        adj[u].pb(v); adj[v].pb(u);
        possible.insert(u); possible.insert(v);
    }
    vector<ll> skip(n+5,0);
    while(possible.size()!=1){
        ll len=possible.size();
        len/=2;
        cout<<"? "<<len<<" ";
        ll root=-1;
        for(ll i=1;i<=n;i++){
            if(adj[i].size()==1){
                root=i;
            }
        }
        debug(possible);
        debug(root);
        vector<ll> visited(n+5,0);
        queue<ll> track;
        visited[root]=1;
        set<ll> now;
        if(possible.count(root)){
            now.insert(root);
        }
        track.push(root);
        while(!track.empty()){
            auto it=track.front();
            track.pop();
            for(auto chld:adj[it]){  
                if(now.size()==len){
                    break;
                }
                if(visited[chld]){
                    continue;
                }
                visited[chld]=1;
                track.push(chld);
                if(possible.count(chld)){  
                    now.insert(chld);
                }
            }
        }
        for(auto it:now){
            cout<<it<<" ";
        }
        cout<<endl;
        ll q; cin>>q;
        if(q==1){
            vector<ll> new_adj[n+5];
            for(ll i=1;i<=n;i++){
                for(auto it:adj[i]){
                    if(visited[i]&&visited[it]){
                        new_adj[i].pb(it);
                    }
                }
            }
            possible=now;
            for(ll i=1;i<=n;i++){
                adj[i].clear(); adj[i]=new_adj[i];
            }
        }
        else{
            for(ll i=1;i<=n;i++){
                if(visited[i]){
                    if(possible.count(i)){
                        possible.erase(i);
                    }
                }
            }
            vector<ll> new_adj[n+5];
            for(ll i=1;i<=n;i++){
                for(auto it:adj[i]){  
                    if((visited[i])&&(visited[it])){
                        continue;
                    }
                    ll l=i,r=it;
                    if(visited[l]){  
                        l=root;
                    }
                    if(visited[r]){
                        r=root;
                    }
                    new_adj[l].pb(r);
                }
            }
            for(ll i=1;i<=n;i++){
                adj[i].clear(); adj[i]=new_adj[i];
            }
        }  
    }
    ll y=*possible.begin();
    cout<<"! "<<y<<endl;
    return;               
}                               
int main()                                                                         
{
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);                         
    #ifndef ONLINE_JUDGE               
    freopen("input.txt", "r", stdin);                                           
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                        
    #endif         
    ll test_cases=1;                   
    cin>>test_cases;
    while(test_cases--){   
        solve();     
    }
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
} 
Tester-1's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
 
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;

vector<vector<int> > adj;
vector<int> eul;

void dfs(int c, int p){
    eul.push_back(c);
    for(auto h:adj[c]){
        if(h!=p) dfs(h,c);
    }
}

void solve()
{   

    int n = readIntLn(1,1000);
    sum_n += n;
    max_n = max(max_n,n);

    adj.assign(n, vector<int>());
    eul.clear();
    int x,y;

    rep(i,n-1){
        x = readIntSp(1,n);
        y = readIntLn(1,n);

        --x,--y;

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs(0,-1);

    assert(eul.size()==n);

    int l=0, r=n-1;

    while(l<r){
        int mid = (l+r)>>1;

        cout<<"? "<<mid-l+1<<" ";
        rep_a(i,l,mid+1) cout<<eul[i]+1<<" ";
        cout<<endl;

        int f = readIntLn(0,1);

        if(f) r=mid;
        else l=mid+1;
    }

    cout<<"! "<<eul[r]+1<<endl;
}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,1000);
    
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    assert(getchar() == -1);
    assert(sum_n<=5e4);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_n <<'\n';
    cerr<<"Maximum length : " << max_n <<'\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}

Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
void dfs(int x, int pr, vector<int> tr[], vector<int> &a){
  a.push_back(x);
  for(int i = 0; i < tr[x].size(); i++){
    int y = tr[x][i];
    if(y != pr){
      dfs(y, x, tr, a);
    }
  }
}
int main(){
  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    vector<int> tr[n + 1];
    for(int i = 0; i < n - 1; i++){
      int u, v;
      cin>>u>>v;
      tr[u].push_back(v);
      tr[v].push_back(u);
    }
    vector<int> a;
    dfs(1,0,tr,a);
    int l = 0, r = n - 1;
    while(l != r){
      int mid = (l + r) / 2;
      cout<<"? "<<mid - l + 1<<" ";
      for(int i = l; i < mid + 1; i++){
        cout<<a[i]<<" ";
      }
      cout<<"\n";
      int temp;
      cin>>temp;
      if(temp){
        r = mid;
      }else{
        l = mid + 1;
      }
    }
    cout<<"! "<<a[l]<<"\n";
  }
  return 0;
}

Nice Problem.

I think the time complexity should be \mathcal{O}(N \log N).

2 Likes

I was implementing solution 2, but instead of replacing the subtree with a dummy node, I am just neglecting it. It is giving WA, can anyone help? (Solution: 59880703 | CodeChef)

Let C be our centroid; C_i be its i^{th} neighbour; S_i be the set of vertices whose shortest path from C includes C_i; S_x be the largest set. Note that there is no limit to how small |S_x| can be; if our graph was star, it could be 1 also. Therefore we must choose some subgraph such that its length is \left \lceil{n/2}\right \rceil , after that, whether you put a dummy node or just ignore them, it should be fine.