512.md (7183B)
1 Source: https://codeforces.com/blog/entry/16173 2 3 **Update 1** : here are the reference solutions for this contest: 4 5 1. Div2-A: <http://ideone.com/JP1Ksj> 6 2. DIv2-B: <http://ideone.com/udz3bN> 7 3. Div2-C / Div1-A: <http://ideone.com/KVobNb> 8 4. Div2-D / Div1-B: <http://ideone.com/7MQqOm> 9 5. Div2-E / Div1-C: <http://ideone.com/z3FsU2> 10 6. Div1-D: <http://ideone.com/Y7j21a> 11 7. Div1-E: <http://ideone.com/Orbacp> 12 13 Note that for Div2-E / Div1-C, it is for the harder version: we need to handle '1' in the cycle. 14 15 [510A - Fox And Snake](/contest/510/problem/A "Codeforces Round 290 (Div. 2)") 16 17 There are 2 different ways to solve this kind of task: 18 19 First one is to simulate the movement of the snake head, and you draw '#'s on the board. The code will look like: 20 21 ``` 22 head = (1, 1) 23 repeat: 24 repeat m-1 times: head move to right 25 repeat 2 times: head move down 26 repeat 2 times: head move down 27 repeat m-1 times: head move to left 28 repeat 2 times: head move down 29 repeat 2 times: head move down 30 until head is out of the board 31 ``` 32 33 Another way is to do some observation about the result, you can find this pattern: 34 35 ``` 36 (4k+1) / (4k+3) line: "#######" 37 (4k+2) line: ".......#" 38 (4k+0) line: "#......." 39 ``` 40 41 [510B - Fox And Two Dots](/contest/510/problem/B "Codeforces Round 290 (Div. 2)") 42 43 This task is essentially ask if there is a cycle in an undirected graph: treat each cell as a node, and add an edge if two cells are neighborhood and have some color. 44 45 There are lots of ways to do this, for example: 46 47 1. Run dfs / bfs, if an edge lead you to a visited node, then there must be a cycle. 48 2. For each connected component, test if |#*edges*| = |#*nodes*| - 1, if not then there must be a cycle. 49 50 [510C - Fox And Names](/contest/510/problem/C "Codeforces Round 290 (Div. 2)") / [512A - Fox And Names](/contest/512/problem/A "Codeforces Round 290 (Div. 1)") 51 52 Let's first think about what *S* < *T* can tell us: suppose *S* = *abcxyz* and *T* = *abcuv*. Then we know that *S* < *T* if and only if *x* < *u* by the definition. 53 54 So we can transform the conditions *name*1 < *name*2, *name*2 < *name*3 ... into the order of letters. 55 56 Then the question become: do we have a permutation that satisfy those conditions. It is actually the classic topological order question. 57 58 One trick in this task is that, if we have something like *xy* < *x* then there is no solution. This is not covered in pretests. :) 59 60 [510D - Fox And Jumping](/contest/510/problem/D "Codeforces Round 290 (Div. 2)") / [512B - Fox And Jumping](/contest/512/problem/B "Codeforces Round 290 (Div. 1)") 61 62 This task equals to: what is the minimal sum of costs that we can select k cards, so their GCD is 1. 63 64 First observation is that: *GCD*(*x*1, *x*2, ..., *x**k*) = 1 means that for any prime *p*, there exist i such that *x**i* is not dividable by *p*. So we only care about what prime factors a number contain. (So for example, 12 -> {2, 3}, 6 -> {2, 3}, 9 -> {3]}) 65 66 The second observation is: If *x* ≤ 109 then it has at most 9 prime factors. 67 68 So after we select one number, we only care about these 9 or less primes. Then this problem equals to set covering problem (SCP), it can be done by mask DP. It can run in about O(2^9 * n^2). 69 70 [510E - Fox And Dinner](/contest/510/problem/E "Codeforces Round 290 (Div. 2)") / [512C - Fox And Dinner](/contest/512/problem/C "Codeforces Round 290 (Div. 1)") 71 72 First finding is: if *a* + *b* is a prime, then one of them is an odd number, another is an even number. (that's why we set 2 ≤ *x**i*) 73 74 Then we could find: every odd number have exactly 2 even number as neighborhood, and every even number have exactly 2 odd number as neighborhood. And that means we need |#*even*| = |#*odd*| to have a solution. 75 76 So it looks like bipartite graph matching, but every element matched 2 elements. And in fact it can be handled by maxflow: For each odd number, we add a node on the left side and link it from source with capacity equals to 2, and for each even number, we add a node on the right side and link it to sink with capacity equals to 2. And if sum of two numbers is a prime number, we link them with capacity equals to 1. 77 78 Then we solve the max flow, it have solution if and only if *maxflow* = 2 * |#*even*|. 79 80 We can construct the answer(cycles) from the matches. 81 82 Note: Actually this task is still solvable if we allow *a**i* = 1. But you need some clever way to deal with it. We think it is too hard so we removed this case. What do you think about this decision? 83 84 [512D - Fox And Travelling](/contest/512/problem/D "Codeforces Round 290 (Div. 1)") 85 86 We could find that some nodes cannot be visited. And more specific, if one node is in a cycle then it cannot be visited. So what about the structure of nodes that we can visit? 87 88 Let's first find a way to get all nodes that could be visited. We can deal with this by something like biconnected decomposition, but that is not easy to implement. In fact we can use this simple method: each time we pick one node that have at most 1 neighborhood and delete it. Repeat this process until we can't do it anymore. 89 90 We could find these nodes are actually belonging to these 2 kinds: 1. A tree. 2. Rooted tree. (that means, the root is attached to a cycle) 91 92 The rooted tree case is simple: we can solve it by tree DP. The state will be dp[i][j] = the way to remove j nodes in the subtree rooted at i. 93 94 Then how to solve the unrooted tree case? The way to deal with that is to transform it into rooted case. We have 2 solution: 95 96 1. We select one unvisited node as the root by some rules: for example, we select one with minimal index. Then we just need to modify the DP a bit to adjust this additional condition. 97 2. We could find if the tree has n nodes and we visit k nodes in the end, then there will be max(1, n-k) ways to choose the root. That means if we choose every node as the root and sum up them, we will count this case exactly max(1, n-k) times. So we just do the rooted DP for from node n times, and divide max(1, n-k) for ans[k]. 98 99 The overall complicity is *O*(*n*4), and it can be optimize into *O*(*n*3) if you like. 100 101 [512E - Fox And Polygon](/contest/512/problem/E "Codeforces Round 290 (Div. 1)") 102 103 Triangulation of polygon is something hard to think about. So the first key observation is that, we can transform this task into operations on rooted trees! 104 105  106 107 One Triangulation of polygon can be mapping to one rooted tree. And the flip operation can be mapping to the rotation of trees. (It is the operation we used to balance our BST) You can find the mapping from above picture. The red lines indicate the edge that will be flipped and the nodes we rotated. 108 109 Then we should find a standard shape of the tree, and solve this task: how to rotate any tree into this standard shape? 110 111 My solution is to choose the balanced tree as standard shape. The way to do that is this: find the node that the index is the middle number, rotate it to the top(that what we did for splay tree), and do the same thing for each subtree. 112 113 It is easy to see it could work in *O*(*nlogn*) steps.