TopCoder SRM 447 Div 1 Medium (PeopleYouMayKnow)

Problem link : http://www.topcoder.com/stat?c=problem_statement&pm=10580

This is a nice problem because it can be solved in different ways - dynamic programming, maximum flow or bipartite matching.

The solution of the problem in one line would be

calculate maximum number of node disjoint paths from node p1 to p2 whose length is less than or equal to 3.

TopCoder SRM 477 Div 1 Medium (PythTriplets)

Problem Link : http://www.topcoder.com/stat?c=problem_statement&pm=10766&rd=14157

In this problem, given some integers (at most 200) in the range [1, 999999] you have to find maximum number of disjoint pairs (a,b) such that a^2 + b^2 = c^2 for some integer c and a & b are co-prime.

Now this is a classic example of a bipartite matching problem although it may not be evident how to split the numbers in two bipartite sets. Lets consider the different cases possible according to the parity of the numbers in a pair -