SETQUER - Editorial

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. :slight_smile:

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