Topcoder SRM 633 Div. 1 600 - DoubleTree

Problem Statement:
SRM 633 Div. 1 600 - DoubleTree

Solution:
It is interesting to know that this problem is actually a Maximum Flow problem. When we fix a node as the root of both of the trees, we reduce the problem to maximum weight connected sub graph problem. Let's say we have chosen a root R. R will be inside the subset S in question. We run a depth first search on both tree starting at R, forming two trees A and B. Then we build a graph G such that:
1. for each node v, we connect v with its parent u in A and B each with an edge with infinite capacity. This means that if we pick node v, then we have to also pick u, so we ensure that v and R is connected.
2. introduce two new nodes, source s and sink t. For each v in G, if v has a positive score m, add an edge between s to v with capacity m. Otherwise, m is negative, then we connect v with t using an edge with capacity -m.

a bit of topcoder: SRM 633 Div. 1

(My first Div 1, OMG damn difficult)

First Problem (250 pts)
Problem Statement
633 Div. 1 250 - PeriodicJumping

Summary:
Can u build a polygon with a periodic sequence of segments \(a_1,a_2,a_3,\ldots,a_t\) by using the segments sequentially? If so, what is the minimum segments needed?

Solution:
Firstly it is always possible to build a polygon using these segments. Secondly, to solve this problem we need to know the "Polygon Inequality", which is a generalization of Triangle Inequality:

Triangle Ineq: \(a\leq b\leq c\) are the sides of a triangle if and only if \(c \leq a+b\)
Extended to polygons (by Induction I suppose)
Polygon Ineq: \(a_1,a_2,\ldots, a_n\) are sides of polygons iff the max side is \(\leq\) the sum of the rest of the sides.

So to build the polygon, we have to iterate through the segments one by one until we manage to fulfill the inequality. The idea sounds simple but whenever it is computational geometry, there are corner cases that must be taken care of..