# 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個剩餘。現在大神同學希望在三類紀念品中各挑選一件然後贈送給她的三名可愛的小夥伴，但是她又不希望恰好挑出來兩件價值相同的紀念品，因為這樣拿到相同價值紀念品的兩位小夥伴就會認為大神同學偏袒另一位小夥伴而不理睬她超過一星期。現在，大神同學希望你買到的三件紀念品能讓三位小夥伴都開心並且不和她鬧彆扭，她想知道一共有多少種不同挑選的方法？

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, 同構

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

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.