Update 1 Added links to my code.

Update 2 The links to my code seems not work, so I push my codes on github, and you find all of them here: https://github.com/cgy4ever/cf190

Update 3 Fixed my solution of Div1-C (Div2-E). In this problem, we must find centroid of tree instead of center of tree. Thanks RomaWhite for pointing this out and provide test case. And it seems that many solutions can pass the system test will fail on his test case (including my model solution). I feel apologetic for the weak test cases and wrong solution.

Update 4 Reformat the passage, I hope it would looks better.

322A - Ciel and Dancing

Let's define remainNew = # of people haven't danced before. So at beginning remainNew = n+m, and we have:

• During the 1st song, remainNew must decreased by at least 2. (Because the boy and girl must haven't danced before.)
• During the k-th (k>1) song, remainNew must decreased by at least 1. (Because one of the boy or girl must haven't danced before.) So the answer must be no more than n+m-1.

And it's not hard to construct one schedule get this maximal possible answer:

1 1
1 2
...
1 m
2 1
3 1
...
n 1

322B - Ciel and Flowers

If there are no "mixing bouquet" then the answer will be r/3 + g/3 + b/3. One important observation is that: There always exist an optimal solution with less than 3 mixing bouquet.

The proof is here: Once we get 3 mixing bouquet, we can change it to (1 red bouquet + 1 green bouquet + 1 blue bouquet)

So we can try 0, 1, 2 mixing bouquet and make the remain 3 kind of bouquets use above greedy method. Output one with largest outcome.

322C - Ciel and Robot 321A - Ciel and Robot

Note that after Ciel execute string s, it will moves (dx, dy). And for each repeat, it will alway moves (dx, dy). So the total movement will be k * (dx, dy) + (dx[p], dy[p]) which (dx[p], dy[p]) denotes the movement after execute first p characters. We can enumerate p since (0 <= p < |s| <= 100), and check if there are such k exists.

Note that there are some tricks:

• We can divide dx or dy directly because they both can become zero.
• Another trick is that k must be non-negative.

Many people failed on this test case (which no included in the pretest):

-1 -1
UR

322D - Ciel and Duel 321B - Ciel and Duel

We have 3 solutions to this problem:

= 1. greedy =

There are 2 cases: we killed all Jiro's cards, or not.

If we are not killed all of Jiro's cards, then:

1. 1. We never attack his DEF cards, it's meaningless.
2. Suppose we make k attacks, then it must be: use Ciel's k cards with highest strength to attack Jiro's k cards with lowest strength, and we can sort the both k cards by strength to make attack one by one. (If there are an invalid attack, then we can't have k attack)

If we kill all Jiro's card: Then for all DEF cards, we consider it from lower strength to higher: if its strength is L, then we find a card of Ciel with strength more than L (If there are many, we choose one with lowest strength). Then we can know if we can kill all DEF cards. And then we choose |x| cards with highest strength of Ciel, try to kill Jiro's remain card.

Note that if we could kill all ATK cards, the order doesn't matter: the total damage will be (sum of strength of Ciel's remain card) — (sum of strength of Jiro's remain card).

= 2. DP =

Above solution looks complicated, can we solve it with few observation? Yes we can. The only observation is that:

There always exist an optimal solution that: If Ciel's two card X's strength > Y's strength, and X, Y attacks on A and B with the same position, then A's strength > B's strength. We already use this observation in above solution.

Then what can we do? Yes, we can sort all Ciel's card, all ATK card of Jiro, all DEF card of Jiro.

Let's DP[pCiel][pATK][pJiro][killAll] be the state that next unconsidered card of Ciel, Jiro's ATk, Jiro's DEF are pCiel, pATK, pJiro, and killAll=1 if and only if we assume at the end we can kill all Jiro's card.

Then we have 4 choice:

1. Skip, this card don't attack.
2. Attack on the next ATK card.
3. Attack on the next DEF card.
4. Assume Jiro has no cards and make a direct attack.

= 3. MinCostMaxFlow =

Well, what if we want to solve this problem with no observation?

Ok, if you are good at construct flow algorithm, it's an easy thing to solve this by flow.

Please see my solution for details. It just considered the matching relationship.

322E - Ciel the Commander 321C - Ciel the Commander

This is a problem with construction on trees. And for these kind of problems, we usually use two method: up-down or down-up. So we have 1 solution for each method:

= 1. up-down construction =

Suppose we assign an officer with rank A at node x. Then for two distinct subtree rooted by x, says T1 and T2: There can't be any invalid path cross T1 and T2, because it is blocked by node x. (It's clear that we can't make 2 rank A officer.)

So we can solve these subtree independently: the only different is that we can't use rank A anymore.

Then the question is: which node should x be? It could be good if any subtree will has a small size. And if you have the knowledge of "centroid of tree", then you can quickly find that if x be the centroid of this tree, the subtree's size will be no more than half of the original tree. So we only needs about log2(n) nodes and 26 is enough.

= 2. down-up construction =

The above solution involves the concept of "centroid of tree" but you might not heard about that, don't worry, we have another solution can solve this problem without knowing that, and it's easier to implement.

Suppose we choose 1 as the root and consider it as a directed tree, and on some day we have the following problem:

We have some subtree rooted at T1, T2, ..., Tk, and they are already assigned an officer, we need to assign an officer to node x and link them to this node. Well, a normal idea is: we choose one with lowest possible rank.

The rank of x should satisfy:

1. If there are a node with rank t exposes at Ti and a node with t exposes at Tj (i!=j), then rank of x must be higher than t. (Otherwise the path between them will be invalid.)
2. If there are a node with rank t exposes at Ti, then the rank of x can't be t.

So we can use this rule to choose the lowest possible rank. But can it passes? Yes, it can, but the proof is not such easy, I'll introduce the main idea here:

• We assign each node a potential: p(x) = {2^('Z' — w) | w is exposed}. For example, if 'Y' and 'Z' are exposed, then p(x) = 1 + 2 = 3.
• We can proof p(x) <= |# of nodes of the subtree rooted by x| by proof this lemma: When we synthesis x with T1, T2, ..., Tk, p(x) <= 1 + p(T1) + ... + p(Tk). It's not hard to proof, but might have some cases to deal with.

321D - Ciel and Flipboard

For this problem we need a big "observation": what setup of "flips" are valid? What means set up of "flips", well, for example, after the 1st step operation of example 1, we get:

1 1 0
1 1 0
0 0 0

It means the left top 2x2 cells are negatived.

Given a 0-1 matrix of a set up of "flips", how can you determine if we can get it by some N x N (I use N instead of x here, it don't make sense to write something like x x x.) flips.

To solve this problem, we need the following observation:

1. For any i, any j<=x: setUp[i][j]^setUp[i][x]^setUp[i][j+x] will be 0.
2. For any i, any j<=x: setUp[j][i]^setUp[x][i]^setUp[j+x][i] will be 0.

It's quite easy to proof than find that: after each operation, there always be 0 or 2 cells lay in {setUp[i][j], setUp[i][x], setUp[i][j+x]} or {setUp[j][i], setUp[x][i], setUp[j+x][i]}.

So what? Well, then there must be no more than 2^(N*N) solutions, since if we determine the left top N x N cells, we can determine others by above equations.

And then? Magically we can proof if one set up meets all above equations, we can get it. And the proof only needs one line: think the operation as addition of vectors in GF2, then we have N*N independent vector, so there must be 2^(N*N) different setups we can get. (Yes, I admit it need some knowledge, or feeling in linear algebra)

Then the things are easy: we enumerate {setUp[1][N], setUp[2][N], ..., setUp[N][N]}, and determine others by greedy. (More detailed, by columns.)

You can find details in my code.

321E - Ciel and Gondolas

This problem may jog your memory of OI times (if you have been an OIer and now grows up, like me). Maybe some Chinese contestants might think this problem doesn't worth 2500, but DP optimization is an advanced topic in programming contest for many regions. It's quite easy to find an O(N^2 K) DP:

• dp[i][j] = max{ k | dp[i-1][k] + cost(k+1...j)}

(dp[i][j] means the minimal cost if we divide 1...j foxes into i groups)

There are many ways to optimize this kind of dp equation, but a large part of them based one the property of cost function. So we need to find some property independent of cost function.

Let opt[i][j] = the smallest k such that dp[i][j] = dp[i][k] + cost(k+1...j) Then intuitively we have opt[i][1] <= opt[i][2] <= ... <= opt[i][n]. (I admit some people don't think it's intuitively correct, but it can proof by some high school algebra)

Then how to use this stuff?

Let n = 200 and suppose we already get dp[i][j] for i<=3 and now we have to compute dp[4][j]: If we first compute dp[4][100], then we can have opt[4][100] at the same time.

And when we compute dp[4][1] ... dp[4][99], we know that the k must lay in 1...opt[4][100]. When we compute dp[4][101] ... dp[4][200], we know that k must lay in opt[4][100]...n.

Let's formalize this thing: We use compute(d, L, R, optL, optR) to denote we are computing dp[d][L...R], and we know the k must be in range optL...optR.

Then we have:

compute(d, L, R, optL, optR) = 

	1. special case: L==R.

	2. let M = (L+R) / 2, we solve dp[d][M] as well as opt[d][M]. Uses about (optR-optL+1) operations.

	3. compute(d, L, M-1, optL, opt[d][M])

	4. compute(d, M+1, R, opt[d][M], optR)

One can show that this solution will run in O(NlogN * K). Note that we don't need opt[d][M] at the center of interval optL...optR. We can proof at each recursive depth, the total cost by line 2 will be no more than 2n. And there are at most O(log(n)) depths.