We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I try to solve this problem (in Java) without using object Node. I spent 70% time to make algorithm and last 30% time to deal with the issue that the input is not like what i assumed.
I passed 6 cases and failed the others with time limitation. The code must be wrong somewhere. :((( (My English was bad)
classResult{/* * Complete the 'cutTheTree' function below. * * The function is expected to return an INTEGER. * The function accepts following parameters: * 1. INTEGER_ARRAY data * 2. 2D_INTEGER_ARRAY edges */publicstaticintcutTheTree(List<Integer>data,List<List<Integer>>edges){// Write your code here//Using undirected adjacent list (ArrayList<LinkedList<Integer>(3)>) -> Space: O(n)//Read data from edges to build graph -> Time: O(n^2)List<List<Integer>>graph=read(edges,data.size());//For-loop every egdes to check (Brute force)//Consider cutting chosen edge and calculate total value in each tree.//Before cutting, remember the edge cut and repair the edge after iterationintmin=Integer.MAX_VALUE;for(inti=edges.size()-1;i>=0;i--){//->O(n^2)inttemp=cutAndCal(edges.get(i),graph,data);//->O(n)if(min>temp)min=temp;}returnmin;}publicstaticList<List<Integer>>read(List<List<Integer>>edges,intsize){List<List<Integer>>graph=newArrayList<>(size);//O(n)for(inti=0;i<size;i++)graph.add(newArrayList<Integer>(3));//[parent, child1, child2], except root 0 (node 1) with [0, child 1, child 2]// int rootIdx = 0; //node 1graph.get(0).add(0);//O(1)//While-loop check existed node in edge, sort (~~Selection sort)//Worst case: O(n^2)intidx,i;idx=i=0;while(i<edges.size()){intfirst=edges.get(i).get(0)-1;intsecond=edges.get(i).get(1)-1;//Check if ith edge has existed, add to graph, swapif(!graph.get(first).isEmpty()||!graph.get(second).isEmpty()){graph.get(first).add(second);graph.get(second).add(first);//Swapif(i!=idx){List<Integer>temp=edges.get(idx);edges.set(idx,edges.get(i));edges.set(i,temp);}//Updatei=++idx;}//Else i++elsei++;}// for(List<Integer> l : edges){// int first = l.get(0) - 1;// int second = l.get(1) - 1;// graph.get(first).add(second);// graph.get(second).add(first);// }returngraph;}publicstaticintcutAndCal(List<Integer>edge,List<List<Integer>>graph,List<Integer>data){intfirst=edge.get(0)-1;intsecond=edge.get(1)-1;//Identify 2 root (node 1(0) and another)introot2Idx=findNewRoot(edge,graph);//O(1)intparent=first+second-root2Idx;//parent may not always first//Remove edge, remember edgegraph.get(parent).remove(Integer.valueOf(root2Idx));graph.get(root2Idx).remove(Integer.valueOf(parent));graph.get(root2Idx).add(0,-1);//Calculateintcal1=cal(0,graph,data);//0 is root1Idxintcal2=cal(root2Idx,graph,data);//->O(n)cal2=(int)Math.abs(cal2-cal1);//Repair treegraph.get(parent).add(root2Idx);//O(1)graph.get(root2Idx).remove(Integer.valueOf(-1));graph.get(root2Idx).add(0,parent);returncal2;}publicstaticintcal(introotIdx,List<List<Integer>>graph,List<Integer>data){//O(n)intsum=0;Queue<Integer>q=newLinkedList<>();q.add(rootIdx);//Calculate sum by level-traversal using queue.while(!q.isEmpty()){intidx=q.poll();sum+=data.get(idx);// q.addAll(graph.get(idx));for(inti=1;i<graph.get(idx).size();i++){q.add(graph.get(idx).get(i));}}returnsum;}publicstaticintfindNewRoot(List<Integer>edge,List<List<Integer>>graph){//O(1)intfirst=edge.get(0)-1;intsecond=edge.get(1)-1;if(graph.get(second).get(0)==first){//Then first is parent absreturnsecond;}returnfirst;}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Cut the Tree
You are viewing a single comment's thread. Return to all comments →
I try to solve this problem (in Java) without using object Node. I spent 70% time to make algorithm and last 30% time to deal with the issue that the input is not like what i assumed. I passed 6 cases and failed the others with time limitation. The code must be wrong somewhere. :((( (My English was bad)