PROBLEM LINK:
Setter: jtnydv25
Testers: gamegame
Editorialist: aryanag_adm
DIFFICULTY:
3118
PREREQUISITES:
Graph theory, binary search
PROBLEM:
There is a hidden tree T = (V, E) with |V| = N \leq 1000 nodes. You can ask queries to the judge. Each query consists of a subset S of these V. A vertex v \in S is isolable if \exists \ e \in E such that, if you remove e from E, the other vertices in S become unreachable from v. The judge replies to each query with an arbitrary isolable vertex from S, along with the sum of isolable vertices in S.
You have to find the edges of the hidden tree.
You are allowed to ask 10^4 queries to the judge.
EXPLANATION:
Note that log(N) = 10 \implies N \cdot log(N) = 10^4, which is the limit on the number of queries. In most interactive problems, this is a dead giveaway that some kind of binary search is required.
Claim 1: If you query any connected subgraph T' of T, the isolable vertex returned by the query will always be a leaf vertex v in T'.
Proof 1: If v is a leaf in T', it has only one edge that connects it to other vertices in T'. Removing that edge disconnects it, which implies that v is isolable. Now, assume that a vertex v is not a leaf in T'. Then it has two edges that connect it directly to other vertices in T', which implies that it is not isolable.
Now, the idea is the following:
- We first query V_N = V, the entire set of vertices. Since V is connected, by Claim 1, the query returns a leaf to us. We call this leaf v_n.
- Now, we query V_{N-1} = V_N \setminus \{v_N\}. Since V_N was connected and v_n was a leaf in V_N, V_{N-1} is also connected. Therefore, by Claim 1, the query returns a leaf to us. We call this leaf v_{n-1}.
- We continue this process. In step i, we query V_{N +1 -i} = V_{N +2 -i} \setminus \{v_{N+2-i}\}, which is connected since V_{N+2-i} is connected and v_{N+2-i} is a leaf node. By Claim 1, the query returns a leaf node v_{N+1-i}.
- Finally, we get to a point where we have V_1 which consists of a single node v_1. We call this the root node.
- Note that \forall \ 1\leq i \leq N, V_i forms a connected subgraph of V and V_i = V_{i-1} \cup \{v_i\}. We are going to try to find E_i, the set of edges in the induced subgraph of V_i. We consider the tree to be rooted at v_1.
- We start with (V_1 = \{v_1\}, E_1 = \emptyset).
- Now, v_1 is obviously the parent of v_2. Therefore we have (V_2 = \{v_1, v_2\}, E_2 = \{v_1-v_2\}).
- It gets trickier from here. Assume we have solved for V_{i-1}. We need to find the parent of v_i in (V_{i-1}, E_{i-1}). We do this by binary searching on the levels of the tree. Let T_0 be the tree containing only the root, and T_x be the tree consisting of the first x levels of (V_{i-1}, E_{i-1}). Let f(S) be the sum returned on querying the set S. For simplicity, assume that the parent of v_i is not v_1. Now, for any given x, how is f(T_x \cup v_i) different from f(T_x)? Let’s say that the parent of v_i is at level k. If x \leq k, then note that exactly one ancestor of v_i must be a leaf in T_x, and not isolable in T_x \cup v_i - which implies f(T_x \cup v_i) = f(T_x) + v_i - y, where y is some ancestor of v_i. If x > k, then v_i does not share any edge with any vertex in T_x - which implies f(T_x \cup v_i) = f(T_x) + f(v_i) = f(T_x) + v_i. Therefore, if g(x) = f(T_x) + v_i - f(T_x \cup v_i) is \leq 0, then x > k, else x \leq k and g(x) is the lowest ancestor of v_i in T_x.
- Therefore we have a monotonic function g(x) which tells us whether x \leq k, and if it is, then it also tells us the lowest ancestor of v_i in T_x. Using this function, we can trivially binary search for k. Finally E_i = E_{i-1} \cup (g(k) - v_i).
- However, this uses slightly too many queries. There are a few tricks needed to reduce the number of queries.
- Firstly, we already know T_x. Therefore, we can find the leaves ourselves instead of querying for f(T_x) in the binary search.
- Secondly, right at the beginning of the algorithm (when we were removing leaves), we did not exploit the sums of the queries. Note that if f(V_{i}) \neq f(V_{i+1}) - v_{i+1}, it means that the removal of v_{i+1} has caused another vertex in V_{i+1} to become a leaf. Obviously, this implies that an edge exists between v_{i+1} and that vertex. The index of that vertex can be found by y = f(V_i) - f(V_{i+1}) + v_{i+1}. Therefore, we already know that the parent of v_{i+1} is y, and we can skip binary searching for it later.
- Now, every node that is not a leaf in T becomes a leaf at some point in this process, and we therefore find the parent of the node that we removed right before that. Therefore, we only have to binary search for the parent of k nodes, where k is the number of leaves in T.
- Therefore, we use N + k\cdot log(h) queries where h is the height of T when rooted at v_1.
- k+h \leq N \leq 1000, therefore, k \cdot log(h) \leq 7000 (you can verify this easily).
- Therefore, the total number of queries used is clearly within the limit.
Note: there is an edge case I did not consider, when the parent of v_i is the root itself. You can work around this in a number of ways quite easily
TIME COMPLEXITY:
Time complexity is O(N^2 \cdot {log}(N)).
SOLUTION:
Editorialist's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
//#define int long long
#define double long double
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
void remove(vector<int> &v, int x){
vector<int> temp;
for(int j: v){
if(j!=x) temp.push_back(j);
}
v.clear();
for(int j: temp) v.push_back(j);
}
pair<int, int> query(vector<int> s){
if(s.size() <= 2){
return {s[0], s[0]};
}
cout<<"? ";
cout<<s.size()<<" ";
for(int j: s) cout<<j<<" ";
cout<<endl;
int a, b;
cin>>a;
if(a==(-1)) exit(0);
cin>>b;
return {a, b};
}
signed main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
if(n==2){
cout<<'!'<<endl;
cout<<"1 2"<<endl;
int x;
cin>>x;
continue;
}
vector<int> currset;
pair<int, int> curr;
int par[n+1];
int val[n+1];
int deg[n+1];
int lev[n+1];
val[0] = 0;
for(int i = 1;i<=n;i++){
lev[i] = 0;
val[i] = 0;
par[i] = -1;
deg[i] = 0;
currset.push_back(i);
}
curr = query(currset);
vector<pair<int, int>> e;
vector<int> levels[n+1];
stack<int> st;
st.push(curr.first);
int currlev = 0;
for(int i = 3;i<n;i++){
remove(currset, curr.first);
pair<int, int> temp = query(currset);
int ex = curr.second - curr.first;
if(temp.second > ex){ //temp.second - ex is the parent of our guy
par[curr.first] = temp.second - ex;
}
curr = temp;
st.push(curr.first);
}
par[curr.first] = (currset[0] + currset[1] + currset[2] - curr.second);
remove(currset, curr.first);
par[currset[0]] = currset[1];
st.push(currset[0]);
st.push(currset[1]);
levels[0].push_back(st.top());
st.pop();
for(int i = 0;i<=n;i++) val[i] += levels[0][0];
while(!st.empty()){
int j = st.top();
st.pop();
int lo = 0, hi = currlev;
if(par[j]>0){
goto atend;
}
while(lo <= hi){
int m = mid(lo, hi);
//check if an ancestor of j exists at level m
//if yes, we know to search at levels > m
currset.clear();
currset.push_back(j);
for(int i = 0;i<=m;i++){
for(int x: levels[i]) currset.push_back(x);
}
int ex = val[m] + j;
pair<int, int> temp = query(currset);
if(temp.second != ex){ //it's here
par[j] = (ex - temp.second);
lo = m + 1;
}
else hi = m - 1;
}
atend:
e.push_back({par[j], j});
lev[j] = lev[par[j]] + 1;
levels[lev[j]].push_back(j);
currlev = max(currlev, lev[j]);
deg[j]++;
deg[par[j]]++;
for(int i = lev[j];i<=n;i++){
val[i] += j;
if(deg[par[j]] == 2) val[i] -= par[j];
}
}
cout<<"!"<<endl;
for(pair<int, int> lol: e){
cout<<lol.first<<" "<<lol.second<<endl;
}
cin>>n;
if(n == (-1)) exit(0);
}
}