- Prepare
- Algorithms
- Graph Theory
- DAG Queries
- Discussions

# DAG Queries

# DAG Queries

+ 0 comments https://zeroplusfour.com/dag-queries-hackerrank-solution/

Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

+ 0 comments we can't solve this problem using simple dfs because that will have a complexity of O(n^2) >=10^10. So some lazy propagation is needed. The editorial says it requires sqrt decomposition.

+ 2 comments import java.io.*; import java.util.*; //we use adjacency list representation of a DAG class Graph { int vertices;//no of vertices //ArrayList<Integer> reachable = new ArrayList<>(); long a[] = new long[10];//a value of all the vertices LinkedList<Integer>[] l1 = new LinkedList[10]; boolean visited[] = new boolean[10]; Graph(int vertices) { this.vertices = vertices; for(int i=0;i<vertices;i++) { l1[i] = new LinkedList<Integer>(); l1[i].add(i); //a vertex is reachable from itself visited[i]=false; } } void addEdge(int v1, int v2) { l1[v1].add(v2);//since directed } void do_dfs_1(int v1, long x)//dfs for 1st type of instruction { /** for(int i=0;i<l1[v1].size();i++) System.out.print(l1[v1].get(i) + " "); */ visited[v1] = true; a[v1]= x; //System.out.print(v1 + " "); for(int i=0;i<l1[v1].size();i++) { if(visited[l1[v1].get(i)]==false) { visited[l1[v1].get(i)]=true; //System.out.print(l1[v1].get(i)+ " "); do_dfs_1(l1[v1].get(i), x); } //set to x even if true a[l1[v1].get(i)] = x; } } void do_dfs_2(int v1, long x)//dfs for 1st type of instruction { /** for(int i=0;i<l1[v1].size();i++) System.out.print(l1[v1].get(i) + " "); */ visited[v1] = true; if(a[v1]>x) a[v1]=x; //System.out.print(v1 + " "); for(int i=0;i<l1[v1].size();i++) { if(visited[l1[v1].get(i)]==false) { visited[l1[v1].get(i)]=true; //System.out.print(l1[v1].get(i)+ " "); do_dfs_2(l1[v1].get(i), x); } if(a[l1[v1].get(i)]>x) a[l1[v1].get(i)]=x; } } } public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();//no of vertices int m = sc.nextInt();//no of edges int q = sc.nextInt();//no of queries ArrayList<Long> ans = new ArrayList<>(); //there are three types of queries /** * Type 1:- 1 u x where all the nodes v reachable from u have their av turned to x(a vertex is reachable from itself) * Type 2:- 2 u x where all the nodes v reachble from u have their av turned to x(if av>x) * Type 3: 3 u which will print the av value of u */ Graph g1 =new Graph(n); int a[] = new int[n]; for(int i=0;i<m;i++) { int start =sc.nextInt(); int end = sc.nextInt(); g1.addEdge(start-1, end-1); } //now for instructions for(int k=0;k<q;k++) { int type = sc.nextInt(); if(type==1) { int source = sc.nextInt(); long x = sc.nextLong(); //all reachable to x /** for(int l=0;l<g1.l1[source-1].size();l++) { a[g1.l1[source-1].get(l)]=x; } */ g1.do_dfs_1(source-1, x); } if(type==2) { int source = sc.nextInt(); long x = sc.nextLong(); g1.do_dfs_2(source-1, x); } if(type==3) { int source = sc.nextInt(); ans.add(g1.a[source-1]); //System.out.print(a[source]); } } for(int i=0;i<ans.size();i++) { System.out.println(ans.get(i)); } } }

+ 0 comments Hello! I decided to download a number of test cases to compare the expected output against that of my Python3 solution. The diff shows that both the expected output and my output are exactly the same. Yet, the test case marks 'Wrong Answer'. My solution is in Python 3. It uses a DFS to mark a dictionary of paths before processing the queries. It's O(N x N) + O(Q x N). I'm not getting any errors with timeout or any other errors for that matter. This only occurs when the test case has M=100000. As another user has already pointed out, there are currently no Python 3 solutions with more than ~36 points which is extremely unusual. If any of the moderators have time, could someone please look into why this might be the case. I can post my solution upon request.

Also, the description of the problem states that queries 1 and 2 should update all v where there is a path from u to v, but the examples demonstrate that u is to be updated as well. I don't believe that this is consistent with the definition of a path. Could the description be updated to explicitly require that a of u be updated as well?

+ 0 comments Previous accepted code now fails with timeout. Even the problem setter's code fails with timeout.

What happenned?

Sort 9 Discussions, By:

Please Login in order to post a comment