 # SETQUER - Editorial

Setter:
Tester: Rahul Dugar
Editorialist: Taranpreet Singh

Easy

Just observation

# PROBLEM

Given a triangle free graph hidden from you. You only know the degree of each node and an additional integer K such that K*K \leq N

You need to partition all nodes into sets S and R such that

• |S| \geq K
• S is an independent set i.e. no two nodes in S have a direct edge.
• For each node u \in R, there exist a node v \in S such that edge (u, v) is present in graph.

You are allowed to make queries, first query adds node u into S, and returns the list of neighbours, second query returns list of neighbours of u without adding node u into S (You can only make this query once), and query 3 to determine when you are done partitioning (made only once).

# QUICK EXPLANATION

• If there exists a node with degree \geq K, we can make a query of second type from this node, and add all neighbours of this node into S.
• Now, for all nodes not in S, nor having a neighbour in S, we add it to S and mark that node and their neighbours. We repeat this till all nodes are either in S, or have a neighbour in S

# EXPLANATION

What we can do is, consider following procedure.
Consider all nodes as unmarked for now. Pick a unmarked node, add it to S and mark this node and all it’s neighbours. Keep repeating this procedure till all nodes are marked.

We can see that at every step, all neighbours of nodes in S are marked, we never add two nodes in S which are directly connected. We can also prove that all nodes are either in S or have a neighbour in S.

This satisfies all constraints, except it may cause set S to have fewer than K nodes.

For example, if the hidden graph is a star graph rooted at 1 and we pick node 1 to be added in S, the procedure will end immediately, with only one node in S.

There’s many facts we haven’t used till now.

• K*K \leq N
• Degree of each node
• No query of type 2
• The graph is triangle free.

The third fact means that if there are x nodes directly connected with node u, there cannot be an edge between any pair of nodes between these x nodes. Hence, these x nodes form an independent set, which can be added into S.

Hence, if there exists a node with degree at least K, we can query all it’s neighbours (without adding it to set S), add all neighbours in S and the repeat our first procedure to partition remaining graph into sets S and R. Since we already added K nodes in S, |S| \geq K is also satisfied now.

Remaining Case
Hence, now we are left with case where all nodes have degree < K. This means, that when we pick a node (say u) to be added to S, there can be at most K-1 neighbours which would be marked, plus node u would be marked.

This means that at most K nodes are marked in each iteration, and exactly one node is added in each step. Since K*K \leq N, This procedure is guarantee to run at least K times, hence adding K elements to S

# TIME COMPLEXITY

The time complexity also depends upon the number of edges in graph, which is half the sum of degrees mentioned in problem constraints.

The time complexity is O(N+M) per test case.

# SOLUTIONS

Setter's Solution
Tester's Solution
Editorialist's Solution
import java.util.*;
import java.io.*;
class SHAANK{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), K = ni();
int[] deg = new int[N];
for(int i = 0; i< N; i++)deg[i] = ni();
int cand = -1;
for(int i = 0; i< N; i++)if(deg[i] >= K)cand = i;
boolean[] mark = new boolean[N];
if(cand != -1){
ArrayList<Integer> list = query2(cand);
for(int x:list){
mark[x] = true;
ArrayList<Integer> ban = query1(x);
for(int y:ban)mark[y] = true;
}
}

for(int node = 0; node < N; node++){
if(mark[node])continue;
mark[node] = true;
ArrayList<Integer> ban = query1(node);
for(int v:ban)mark[v] = true;
}
end();
}
ArrayList<Integer> query1(int u) throws Exception{
ArrayList<Integer> list = new ArrayList<>();
pni("1 "+(1+u));
int n = ni();
for(int i = 0; i< n; i++)list.add(ni()-1);
return list;
}
ArrayList<Integer> query2(int u) throws Exception{
ArrayList<Integer> list = new ArrayList<>();
pni("2 "+(1+u));
int n = ni();
for(int i = 0; i< n; i++)list.add(ni()-1);
return list;
}
void end(){pni(3);}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = false;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new SHAANK().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


# VIDEO EDITORIAL:

Feel free to share your approach. Suggestions are welcomed as always. 2 Likes

Managed to get AC by doing this procedure with a random permutation of nodes. Looking at the solution, I can see why this worked. If all nodes have degree <K, the solution is trivial, but when a node has degree>=K it must occur in the permutation before any of its neighbours, the probability of which decreases with increase in its degree.

The case where this would most likely fail is a star graph of N=4 and K=2 where it only has a 75% chance of not putting the central node in S. Probably not the dev intended solution.

1 Like

Cool