MovingTokens: Topcoder SRM 705

The program seems to have a pretty high fail rate. However, the idea is quite simple.

Basically, you are given n (<=50) buckets, each of them has one token inside it initially. and a matrix of m (<=50) operations, each of which moves the tokens of each bin to a new destination simultaneously. You are asked for the minimum number of bins after a number of operations (<=10^100).

Solution: The key here is to observe that, an operation never increases the number of bins with tokens. It either merges two or more bins (by moving them into the same bin) or change the distributions of the bins with tokens.

The second observation is that changing the distributions of the bins with tokens do not change the final result. Let’s say that we have a set of operation S, which moves bin i to k. Now consider all the operations. Either 1) all of them moves k to k, thus there will always be at least token in bin k since there is one initially. 2) one of them move the bins in a new place, k1. Now, repeat the procedure and consider the chain of these buckets, k,k1, … . It is clear that these bins either ends at a bin or form a ring, and its length is smaller then MaxN(50).

So for the operation S and bin k, we either have its inverse operation S^-1(the case of ring), or we could just follow the chain and move it to the end of the chain. without affect the final answer.

Hence, we could just use a greedy algorithm: search for all the bin pairs (i,j) that could be merged beforehand. And keep merging all the bin pairs that could be merged. When there are no bins to be merged, the number of bins with tokens should be the final answer.

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据