PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter:
Tester: Rahul Dugar
Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
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;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
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());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
VIDEO EDITORIAL:
Feel free to share your approach. Suggestions are welcomed as always.