CommonLounge is a community of learners who learn together. Get started with the featured resources above, ask questions and discuss related stuff with everyone.
DP On Trees Problem (CodeForces)
This is a DP on Trees problem. Unless I'm mistaken, the question basically requires us to:
Divide the tree into a number of (different) connected subsets of nodes (or sub-trees) in the tree, with at least one of the sub-trees having exactly K nodes. Then, output the number of edges connecting the different sub-trees.
Any hints? The editorial is unavailable unfortunately. :/
Solution here at my blog, if anyone is interested:
This seems to be quite an interesting problem from IOITC 2013.
Problem in Short: You are given N distinct points on a plane where distances are measured using the Manhattan metric. Find the number of ordered triplets of distinct points (A;B;C) such that the sum of distances from A to B and B to C is equal to the distance from A to C.
I have been trying this problem for quite some time but unable to come up with a solution to pass the following constraints: N<=10^5 and |xi|<=10^9 , |yi|<=10^9.
Some hints to get me unstuck would be highly appreciated. Thank you.
I've been doing some past IOITC problems for a while now, but due to lack of time before TC I started only from 2014 onwards. I was wondering if there are some more interesting, non-trivial problems from before 2014 besides the one I tried, Facebook, 2012. Would be great help if you named a few!