URAL 1770 - The Party of Ural Champions

A useful observation: The original graph can be obtained from removing some edges from the given distance matrix. Futuermore, if d[i][k]+d[k][j] = d[i][j], then edge (i → j) may be removed.

My solution used Reversed Floyd-Warshall algorithm. The basic idea is like

for k=1 to n
  for i=1 to n
    for j=1 to n
      if d[i][k]+d[k][j]==d[i][j] then d[i][j]=INF

However, the problem do not allow directional edge, so we need to avoid setting d[i][j]=INF but keeping the edge (j → i). To solve this problem, I used the following method:

for k=1 to n
  for i=1 to n
    for j=1 to n
      if d[i][k]+d[k][j]==d[i][j] AND r[j][i] then d[i][j]=d[j][i]=INF
      else if d[i][k]+d[k][j]==d[i][j] then r[i][j]=1

At last, don't forget to see if the input matrix satisfy triangular inequality

Addiction

Problem statement

There are N addictions each has a strength S_i. At each week, you can remove one addiction and restore any number of addictions that you have removed. The only constrain is the change of total strength of addictions you currently have must falls into the range [-D, 0]. Find the maximum number of addictions that you can remove, and minimize the number of weeks to achieve this.

1 ≤ N ≤ 1000
1 ≤ S_i ≤ 10000

Solution
First, there is an interesting property that if an addiction can be removed, any addiction with less strength can be removed also.

Although this seem intuitive but we should prove it anyway. We prove it by induction.

Assume that we can remove some addiction with strength P. Consider an addiction with strength T (T < P). Let the set S be the set of addiction with strength smaller than T and Sum(S) be the sum of strength in S. If T-D <= Sum(S) <= T, then we are done. Else, we have Sum(S) > T. Consider the addiction with smallest strength Q in S, if Q is smaller or equal than D, then we remove it from S directly. Else, there must exist some combinations of addictions with strength smaller than Q with sum of strength in [Q-D,Q]. Then we can remove that addiction with strength Q and replace it with that combination. As a result, Sum(S) decrease not more that D in each step and it will fall into [T-D,T] eventually.

Actually this fact is not necessary for our solution, but it is beautiful :P.
The solution is simple - Dynamic Programming.

Sort the addiction by strength first. Assume F(i) be the minimum number of weeks to remove addiction i. We have

F(i) = F(x₁) + F(x₂) + ... + F(x_m)

where S_x1 + S_x2 + ... + S_xm is in the range [S_i-D, S_i].

And we can do this by a knapsack.
The total time complexity is O(N * max(S))

Bridge hand

搭Airbus回家時, 用iphone玩的一手牌, 只係我覺得打得好開心:D
我是south, 但個 game 設定係只要我方叫到合約, 都係由玩家主打


Dealer: E
Vul: Both

South West North  East
                   P
  P    3H    3S    P
 4S     P     P    P


S 8 6 4
H J 2
D J 3
C A K J 8 5 2


S A K J 9 7 2
H 9 3
D A K 5 2
C T


敵方打兩圈紅心後打出小D, 手裏DA吃住。然後我打出SA看看分佈, 左敵打出S5, 右敵卻墊出C6! 假設旁門無失張, 則只能再輸一磴王牌給左敵的 QT3。為了投入左敵, 先要縮短手中王牌的長度(好似係), 因此我手中打出DK, 然後夢家王吃一張方塊, 兌然CA, 然後手中王吃一張草花。之後再交叉王吃方塊和草花, 形成以下局勢:


         S -
         H -
         D -
         C K J 8
S Q T 3
H -
D -
C -
         S K J 9
         H -
         D -
         C -

然後手中打出S9, 投入左敵, 成功以KJ吃死他的Q3。


全手牌:
            S 8 6 4
            H J 2
            D J 3
            C A K J 8 5 2
S Q T 5 3                   S -
H K 8                       H A Q T 7 6 5 4
D Q 9 8 6                   D T 7 4
C Q 4 3                     C 9 7 6
            S A K J 9 7 2
            H 9 3
            D A K 5 2
            C T


不過如果AI第3圈再出紅心的話應該會很糟糕

Sprague-Grundy Theory

Theorem: If G = g1+g2, then sg(G) = sg(g1)^sg(g2)

Proof:
Base case: If sg(g1) = sg(g2) = 0, then G is a P position, which has sg value 0 = 0^0

Induction: We have to prove
1. If sg(G) = v, then sg(G') != v if G → G'
2. If x < sg(G), then there exists G' where G → G' and sg(G') = x

Part 1
Assume G = g1+g2. WLOG, let G' = g1' + g2, by definition, sg(g1) != sg(g1')
Hence sg(G) = sg(g1)^sg(g2) != sg(g1')^sg(g2) = sg(G')

Part 2
Assume sg(g1) = A, sg(g2) = B, sg(G) = C and A < B
If we write A and B in binary representation, we have

A = an an-1 ... 1 ... a2 a1
B = bn bn-1 ... 0 ... b2 b1

and the bits of A,B before the 1 and 0 are same.

Let x < C. Consider x^sg(g2), we have

  C = cn cn-1 ... 1 ...
  x = cn cn-1 ... 0 ...
x^B = an an-1 ... 0 ...

Hence x^B < A. By definition, there exists g1' where sg(g1') < sg(g1) and sg(g1') = x^B.
Assume G' = g1'+g2, we have sg(G') = sg(g1')^sg(g2) = x^B^B = x.
Therefore G' exists.