TC SRM 527

p275

It is p275 so would be a bit harder than the normal p250. The problem is:
Find a tree with n nodes that achieves maximum score. The score of a tree is the sum of score of all nodes, and the score of a node depends on its degree. You are given an array scores[0..n-1] with each element between 0 and 10000, a node with degree d would have score=scores[d-1].

Thought for quite some time but no good idea. For a tree you can try recursively remove one leaf and work on the rest. Another line of attack is to notice the total deg of a tree is 2(n-1). Enumerate a node with deg=1 to n-1 and recurse on the (n-1,d-deg). However, there is no guarantee that there is a node with deg.

Archon.JK submitted this problem within 5min!

I think I understand the problem now, after reading Archon.JK's solution.

his code looks like this
dp[1][0] = 0, u[] = [0, score[]]
for i=1 to n
for j=1 to i-1
for p=1 to n-1
for q=0 to n-2
dp[i][p] = max(dp[i][p], dp[j][p-1]+dp[i-j][q]-u[p-1]-u[q]+u[p]+u[q+1])

and the answer is max of dp[n][0] to dp[n][n-1]

dp[i][j] means best score for a tree with i nodes and one of them has deg=j
The idea is to split a tree with i nodes and a node with deg=p into two subtrees, one with j nodes and the other with i-j nodes, split at deg=p, so one subtree now has a node with deg=p-1 and the other one has deg=q. After merge they become deg=p and deg=q+1.

One possible improvement is to split a tree at a leaf, at node with deg=d. The code looks like this

dp[1][0]=0;
for i=2 to n
for d=1 to i-1
dp[i][d] = max( , dp[i-1][d-1]+dp[1][0]-u[d-1]-u[0]+u[d]+u[1])
we also need to update dp[i][1] since we now have a deg=1 node
dp[i][1] = max( , dp[i][d])

Now the answer is dp[n][1]

// As I was writing this one, I realized how difficult it is to write a solution. That explains why so few people would bother to write solution or summary and even for those who do, it gets delayed or incomplete

p450
Given the rows of a matrix, in order from 0 to m-1. Each row is a string of "0,1,?"
the columns are given as well, in random order. The problem is to find a matrix that agrees with both given rows and columns, and among all feasible ones, find the lexico smallest matrix. No more than 30 rows and 30 columns.

No good idea. As usual I have no idea on level 2 problem.

OK, lyrically's solution makes sense now.
Since we want lexico minimum solution, for each pos, from row 0 to m-1, col 0 to n-1, if cell is '?', we try '0', if the resulted subproblem has a feasible solution, then we fix this '?' to '0', otherwise we put a '1' here.

The subproblem is a bipartite matching problem, cardinality only, without weights. We can construct col[0] to col[n-1] from the rows. If there is a perfect match to the permuted columns, then we have a feasible solution.

Actually, for TC problems, many times if it looks like you need to try all permutations, there is a good chance that you can solve it with bipartite matching.

TODO: both topcoder.com and arena are down currently, need to verify solution.

p250 and p500 PASSED.
Two bugs in implementation of augment, one is that left is 0..n-1 and right is n..2n-1. and when augment, if from left to right, try all neighbors, if right to left, need to follow the matched vertex on the left.

Currently use BFS. The code looks rather ad hoc.