phhp's blog

By phhp, history, 13 days ago, In English,

I am a beginner so soory if the question sound too easy. If in the question it is given there are n cities and n-1 roads connecting them, solve something. The input is given as n (the number of cities) followed by n-1 roads (format u v meaning that there is a bidirectional road from u to v). How do I represent such a tree. I want a parent array to store the parent of each node. But how do I get the parent of each node assuming the root of tree is 1 always. An adjacency list stores for each vertex all the neighbouring vertices but it doesn't have any info about parent. Now if I want to find LCA in such a case, I need the parent array. So how to go about that. Thanks.

Read more »

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

By phhp, history, 5 weeks ago, In English,

Here is the link: RoadOrFlightHard I got the solution but it takes dp[400000][40][2] which is very huge as far as memory is concerned. In the editorial they have added a line that city(i) calculation depends on city(i+1). I was not able to get that observation and I am not getting how to implement it. I saw one code but still did not understand. Thank You.

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By phhp, history, 5 weeks ago, In English,

By Graham Scan O(n*n*logn) would be possible for online construction of convex hull. Can you help me with O(n*n) algorithm. Also what is the difference between 2D CH construction and 3D CH construction

And in graham scan there is a function to sort according to polar order which i did not understand. Please help.

bool polar_order(Point a, Point b){
        //ccw is a function that returns 0 if collinear -1 if counter-clockwise and 1 if clockwise
        //pivot is the lowest y-coordinate point(tie broken by lowest x-coordinate)
	int order = ccw(pivot,a,b);
	if(order==0)
		return sqrdist(pivot,a) < sqrdist(pivot,b);
	return (order==-1);
}

Also if there are some problems you know of convex hull, please share them. Thank you.

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it