codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

322.md (11049B)


      1 Source: https://codeforces.com/blog/entry/8192
      2 
      3 **Update 1** Added links to my code.
      4 
      5 **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>
      6 
      7 **Update 3** Fixed my solution of Div1-C (Div2-E). In this problem, we must find [centroid of tree](http://acm.sgu.ru/problem.php?contest=0&problem=134) instead of [center of tree](http://stackoverflow.com/questions/4020122/finding-center-of-the-tree). Thanks [RomaWhite](/profile/RomaWhite "Master 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.
      8 
      9 **Update 4** Reformat the passage, I hope it would looks better.
     10 
     11 [322A - Ciel and Dancing](/contest/322/problem/A "Codeforces Round 190 (Div. 2)")
     12 
     13 Let's define remainNew = # of people haven't danced before. So at beginning remainNew = n+m, and we have:
     14 
     15 * During the 1st song, remainNew must decreased by at least 2. (Because the boy and girl must haven't danced before.)
     16 * 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.
     17 
     18 And it's not hard to construct one schedule get this maximal possible answer:
     19 
     20 ```
     21 1 1
     22 1 2
     23 ...
     24 1 m
     25 2 1
     26 3 1
     27 ...
     28 n 1
     29 ```
     30 
     31 [322B - Ciel and Flowers](/contest/322/problem/B "Codeforces Round 190 (Div. 2)")
     32 
     33 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.
     34 
     35 The proof is here: Once we get 3 mixing bouquet, we can change it to (1 red bouquet + 1 green bouquet + 1 blue bouquet)
     36 
     37 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.
     38 
     39 [322C - Ciel and Robot](/contest/322/problem/C "Codeforces Round 190 (Div. 2)") [321A - Ciel and Robot](/contest/321/problem/A "Codeforces Round 190 (Div. 1)")
     40 
     41 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.
     42 
     43 Note that there are some tricks:
     44 
     45 * We can divide dx or dy directly because they both can become zero.
     46 * Another trick is that k must be non-negative.
     47 
     48 Many people failed on this test case (which no included in the pretest):
     49 
     50 ```
     51 -1 -1
     52 UR
     53 ```
     54 
     55 [322D - Ciel and Duel](/contest/322/problem/D "Codeforces Round 190 (Div. 2)") [321B - Ciel and Duel](/contest/321/problem/B "Codeforces Round 190 (Div. 1)")
     56 
     57 We have 3 solutions to this problem:
     58 
     59 = 1. greedy =
     60 
     61 There are 2 cases: we killed all Jiro's cards, or not.
     62 
     63 If we are not killed all of Jiro's cards, then:
     64 
     65 1. 1. We never attack his DEF cards, it's meaningless.
     66 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)
     67 
     68 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.
     69 
     70 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).
     71 
     72 = 2. DP =
     73 
     74 Above solution looks complicated, can we solve it with few observation? Yes we can. The only observation is that:
     75 
     76 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.
     77 
     78 Then what can we do? Yes, we can sort all Ciel's card, all ATK card of Jiro, all DEF card of Jiro.
     79 
     80 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.
     81 
     82 Then we have 4 choice:
     83 
     84 1. Skip, this card don't attack.
     85 2. Attack on the next ATK card.
     86 3. Attack on the next DEF card.
     87 4. Assume Jiro has no cards and make a direct attack.
     88 
     89 = 3. MinCostMaxFlow =
     90 
     91 Well, what if we want to solve this problem with no observation?
     92 
     93 Ok, if you are good at construct flow algorithm, it's an easy thing to solve this by flow.
     94 
     95 Please see my solution for details. It just considered the matching relationship.
     96 
     97 [322E - Ciel the Commander](/contest/322/problem/E "Codeforces Round 190 (Div. 2)") [321C - Ciel the Commander](/contest/321/problem/C "Codeforces Round 190 (Div. 1)")
     98 
     99 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:
    100 
    101 = 1. up-down construction =
    102 
    103 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.)
    104 
    105 So we can solve these subtree independently: the only different is that we can't use rank A anymore.
    106 
    107 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.
    108 
    109 = 2. down-up construction =
    110 
    111 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.
    112 
    113 Suppose we choose 1 as the root and consider it as a directed tree, and on some day we have the following problem:
    114 
    115 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.
    116 
    117 The rank of x should satisfy:
    118 
    119 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.)
    120 2. If there are a node with rank t exposes at Ti, then the rank of x can't be t.
    121 
    122 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:
    123 
    124 * 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.
    125 * 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.
    126 
    127 [321D - Ciel and Flipboard](/contest/321/problem/D "Codeforces Round 190 (Div. 1)")
    128 
    129 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:
    130 
    131 ```
    132 1 1 0
    133 1 1 0
    134 0 0 0
    135 ```
    136 
    137 It means the left top 2x2 cells are negatived.
    138 
    139 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.
    140 
    141 To solve this problem, we need the following observation:
    142 
    143 1. For any i, any j<=x: setUp[i][j]^setUp[i][x]^setUp[i][j+x] will be 0.
    144 2. For any i, any j<=x: setUp[j][i]^setUp[x][i]^setUp[j+x][i] will be 0.
    145 
    146 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]}.
    147 
    148 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.
    149 
    150 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)
    151 
    152 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.)
    153 
    154 You can find details in my code.
    155 
    156 [321E - Ciel and Gondolas](/contest/321/problem/E "Codeforces Round 190 (Div. 1)")
    157 
    158 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:
    159 
    160 * dp[i][j] = max{ k | dp[i-1][k] + cost(k+1...j)}
    161 
    162 (dp[i][j] means the minimal cost if we divide 1...j foxes into i groups)
    163 
    164 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.
    165 
    166 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)
    167 
    168 Then how to use this stuff?
    169 
    170 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.
    171 
    172 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.
    173 
    174 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.
    175 
    176 Then we have:
    177 
    178 ```
    179 compute(d, L, R, optL, optR) = 
    180 
    181 	1. special case: L==R.
    182 
    183 	2. let M = (L+R) / 2, we solve dp[d][M] as well as opt[d][M]. Uses about (optR-optL+1) operations.
    184 
    185 	3. compute(d, L, M-1, optL, opt[d][M])
    186 
    187 	4. compute(d, M+1, R, opt[d][M], optR)
    188 ```
    189 
    190 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.