The Solution to MSBOP 2015 Warmup

The following includes the solution to the first two problems in MSBoP 2015 Warmup. The third problem seems a maximum flow problem, and I haven’t written a program to validate it, so I don’t include its possible-wrong solution in this post. (I passed Problem III using a Greedy Algorithm which was obviously wrong with some testcases. I think it’s due to the weak testcases)

Problem II, 大神與三位小夥伴

L國是一個有著優美景色且物產豐富的國家,很多人都喜歡來這裡旅遊並且喜歡帶走一些紀念品,大神同學也不例外。距離開L國的時間越來越近了,大神同學正在煩惱給她可愛的小夥伴們帶什麼紀念品好,現在擺在大神同學面前的有三類紀念品A, B, C可以選擇,每類紀念品各有N種。其中種類為A_i, B_i, C_i的紀念品價值均為i, 且分別有N+1-i個剩餘。現在大神同學希望在三類紀念品中各挑選一件然後贈送給她的三名可愛的小夥伴,但是她又不希望恰好挑出來兩件價值相同的紀念品,因為這樣拿到相同價值紀念品的兩位小夥伴就會認為大神同學偏袒另一位小夥伴而不理睬她超過一星期。現在,大神同學希望你買到的三件紀念品能讓三位小夥伴都開心並且不和她鬧彆扭,她想知道一共有多少種不同挑選的方法?

因為方案數可能非常大,大神同學希望知道挑選紀念品的方案數模10^9+7之後的答案。

輸入

第一列包括一個數T,表示資料的組數。
接下來包含T組資料,每組資料一列,包括一個整數N。

輸出

對於每組資料,輸出一列「Case x: 」,其中x表示每組資料的編號(從1開始),後接一個數,表示模10^9+7後的選擇紀念品的方案數。

There are two possible situations:

  • Three gifts are of the same value
  • Three gifts’ values are different from each other.

The first situation is simple to solve by
Q_1 = \sum_{i=1}^{N}i^3 = \left[\frac{1}{2}N(N+1)\right]^2

So the core problem is equal to find the solution of the equation
Q_2 = \sum_{i=1}^{N} \sum_{j=1,j\neq i}^{N} \sum_{k=1, k\neq i, k\neq j}^{N} (N-i+1)(N-j+1)(N-k+1)

Assume that
S_1 = \sum_{i=1}^{N} i = \frac{1}{2}N(N+1)
S_2 = \sum_{i=1}^{N} i^2 = \frac{1}{6}N(N+1)(2N+1)
S_3 = Q_1= S^2_1

Make some mathematic transformations to it (sorry but the \LaTeX in WordPress does not support aligned environment):
Q_2 = \sum_{i=1}^{N} \sum_{j=1,j\neq i}^{N} \sum_{k=1, k\neq i, k\neq j}^{N} ijk
Q_2 = \sum_{i=1}^{N} \sum_{j=1,j\neq i}^{N} \left[ ij \sum_{k=1, k\neq i, k\neq j}^{N} k \right]
Q_2 = \sum_{i=1}^{N} \sum_{j=1,j\neq i}^{N} ij (S_1-i-j)
Q_2 = \sum_{i=1}^{N} \sum_{j=1,j\neq i}^{N} S_1 ij - i^2j - ij^2

Continue to make the similar transformations.
P_1 = \sum_{i=1}^{N} \sum_{j=1,j\neq i}^{N} S_1 ij
P_1 = \sum_{i=1}^{N} S_1 i (S_1-i)
P_2 = \sum_{i=1}^{N} \sum_{j=1,j\neq i}^{N} i^2j
P_2 = \sum_{i=1}^{N} i^2 (S_1-i)
P_3 = \sum_{i=1}^{N} \sum_{j=1,j\neq i}^{N} ij^2
P_3 = \sum_{i=1}^{N} i (S_2 - i^2)

Therefore,
Q_2 = P_1 - P_2 - P_3
Q_2 = \sum_{i=1}^{N} \left[ S_1 i (S_1-i) - i^2 (S_1-i) - i (S_2 - i^2) \right]
Q_2 = \sum_{i=1}^{N} \left[ (S^2_1-S_2) i - 2S_1 i^2 + 2i^3 \right]
Q_2 = \sum_{i=1}^{N} \left[ (S^2_1-S_2) i - 2S_1 i^2 \right] + 2S_3
Q_2 = S^3_1 - 3S_1 S_2 + 2S_3

Finally obtain the solution
Q = Q_1 + Q_2 = S^3_1 - 3S_1 S_2 + 3S_3

It’s a O(1) algorithm.

Problem I, 同構

給定2個樹A和B,保證A的節點個數>=B的節點個數。現在你需要對樹A的邊進行二染色。一個好的染色方案,指不存在一個樹A中的連通塊,同時滿足以下2個條件

1. 其中只有同色的邊
2. 和B同構。兩個樹同構是指,存在一個一一映射(既是單射又是滿射),將樹B的各節點映射到不同的樹A的節點,使得原來在樹B中連續的點,在映射後,仍相鄰。

問是否存在一種好的染色方案。

輸入

第一列一個整數T (1<=T<=10),表示資料組數。
接下來是T組輸入資料,測試資料之間沒有空列。
每組資料格式如下:
第一列一個整數N ,表示樹A的節點總數。
接下來N-1列,每列2個數a, b (1 <= a, b <= N)表示樹A的節點a和b之間有一條邊。
接下來一列,一個整數M(1 <= M <= N),表示樹B的節點總數。
接下來M-1列,每列2個數a, b (1 <= a, b <= M)表示樹B的節點a和b之間有一條邊。

輸出

對每組資料,先輸出「Case x: 」,x表示是第幾組資料,然後接「YES」/「NO」,表示是否存在所求的染色方案。

資料範圍

小資料:1 <= N <= 20
大資料:1 <= N <= 1000000

If the depth of Tree B is greater than 1, we can color the Tree A by cross-coloring. For example,

a --- b ### c --- d
      #
      e --- f
      |
      g

The # means black and the dash means white. In this way, it’s impossible to find a subtree of Tree A whose depth is greater than 1 and colors are unique. Therefore, in this case, we can always print YES.

However, if the depth of Tree B is equal to 1, which means all nodes but the root of B must be connected with the root. When we make a mapping from B to A, the isomorphic tree of B must also have a depth of 1. So the edges in the possible bad connected component in Tree A must be connected with a same node.

Suppose the degree of the root of B is N_b, while the degree of some one node in A is N_a. There must be at least \lceil N_a/2\rceil edges painted the same color connected with that node in A. if N_b \le \lceil N_a/2\rceil, Tree B can be mapped and the answer is NO. Otherwise, if we cannot find such a node in A, the answer is YES.

Leave a Reply

Time limit is exhausted. Please reload CAPTCHA.