I thought of writing reviews after the topcoder matches, whenever I felt like it. The reviews would be personal and may not be of use to you at all. I promise to warn you with the title of such posts.
The 250 was simple but KawigiEdit slowed me down. The return type was double and the answers that my program was producing in KawigiEdit were nowhere close to the actual answers. I do not mean the precision. They were as different as “0.6666″ and “0.3333″. Weird. Luckily, before attempting to debug, I tested the program in the arena and it turned out to be right. It wasn’t a terribly slow submission.
The 500 is why I wanted to write the post. I actually GOT the solution DURING the match. That I horribly messed up the implementation like an imbecile is another story that sadly doesn’t bother me at all. The problem statement is here.
My approach:
Make a graph with the buyers as the vertices. An edge exists between two vertices if they have at least one stamp in common. Since the maximum number of buyers that can want a stamp is two, the maximum degree of every vertex is also two. Hence, the graph is made of components such that every component is either just a path or just a cycle. The maximum total price of a set of vertices in a component such that no two of those vertices are adjacent, say T(i) for component i, can be calculated by dynamic programming, for every component. The answer is the sum of T(i) of all the components.
How I wish I had coded this right! It is not everyday that you get sparks like this one during a contest.
Sigh.