469.md (10613B)
1 Source: https://codeforces.com/blog/entry/13896 2 3 I'll upload my example solutions and will post links to them as soon as it becomes possible. 4 5 All the problems in Div 1 don't have the unique solution. I list several solutions to each problems. There are also some interesting bonus problems. I can't solve some of them yet :( If you have interesting ideas, feel free to share and discuss your ideas in the comments. :) 6 7 My English is poor, so if there are some mistakes or something you can't understand, you can also discuss it in the comments. 8 9 [469A - I Wanna Be the Guy](/contest/469/problem/A "Codeforces Round 268 (Div. 2)") 10 11 [I Wanna Be the Guy](http://kayin.moe/iwbtg/downloads.php) is an interesting game. I strongly recommend it to you. 12 13 The problem itself is easy. Just check if all the levels could be passed by Little X or Little Y. 14 15 [7894174](/contest/469/submission/7894174 "Submission 7894174 by apia") 16 17 [469B - Chat Online](/contest/469/problem/B "Codeforces Round 268 (Div. 2)") 18 19 This problem is not hard. Just iterator over all possible *t*, and check if the schedule of Little X and Little Z will overlap. 20 21 [7894252](/contest/469/submission/7894252 "Submission 7894252 by apia") 22 23 **Bonus:** 24 25 1. *p*, *q* ≤ 50, *l*, *r* ≤ 109 26 2. *p*, *q*, *l*, *r* ≤ 105 27 28 [468A - 24 Game](/contest/468/problem/A "Codeforces Round 268 (Div. 1)") 29 30 **Solution 1:** 31 32 If *n* ≤ 3, it's easy to find that it's impossible to make 24, because the maximal number they can form is 9. 33 34 If *n* > 5, we can simply add *n* - (*n* - 1) = 1, 24 * 1 = 24 at the end of the solution to the number *n* - 2. 35 36 So we can find the solution of 4, 5 by hand. 1 * 2 * 3 * 4 = 24, (5 - 3) * 4 * (2 + 1) = 24 37 38 [7894267](/contest/468/submission/7894267 "Submission 7894267 by apia") 39 40 **Solution 2:** 41 42 We can find the pattern like that *n* + (*n* + 3) - (*n* + 1) - (*n* + 2) = 0, and find the solution of 4, 5, 6, 7 by hand or brute forces. 43 44 **Solution 3:** 45 46 A knapsack-like solution. 47 48 [7894283](/contest/468/submission/7894283 "Submission 7894283 by apia") 49 50 [468B - Two Sets](/contest/468/problem/B "Codeforces Round 268 (Div. 1)") 51 52 **Solution 1:** 53 54 If we have number *x* and *a* - *x*, they should be in the same set. If , it's obvious that . The contraposition of it is , that means if , *a* - *x* should in the set *B*. Same as the number *x*, *b* - *x*. 55 56 So we can use Disjoint Set Union to merge the number that should be in the same set. 57 58 If *a* - *x* doesn't exist, *x* can not be in the set *A*. If *b* - *x* doesn't exist, *b* can not be in the set *B*. 59 60 Then check if there are any conflicts among numbers which should be in the same set. 61 62 There are many other solutions to solve this problem based on the fact that *x*, *a* - *x*, *b* - *x* should be in the same set, like greedy, BFS and 2-SAT. 63 64 [7894313](/contest/468/submission/7894313 "Submission 7894313 by apia") 65 66 **Solution 2:** 67 68 If *a* = *b*, it's easy to find the solution. 69 70 We regards every number as a node. Every number *x* links to number *a* - *x* and number *b* - *x*. 71 72 The degree of every node is at most 2. So this graph consists of a lot of chains and cycles, and some node may have self loop. 73 74 We only need to check if the lengths of all the chains are even or the chain ends with a self loop. 75 76 [7894323](/contest/468/submission/7894323 "Submission 7894323 by apia") 77 78 **Bonus:** 79 80 Prove there is no cycle in the graph described in the solution 2. 81 82 Divided all the numbers from [0, *n* - 1] into two sets that have parameters *a*, *b*. Can you solved it in *O*(1)? 83 84 [468C - Hack it!](/contest/468/problem/C "Codeforces Round 268 (Div. 1)") 85 86 Define . , so we should find a pair of number *a*, *b* that  87 88 **Solution 1:** 89 90 First we choose *x* randomly. Then we can use binary search to find the minimal *d* that  . 91 92 So  is very small, between 0 and . If , after choosing *x* atmost 9 * *len* + 2 times, we can definitely find a pair that  93 94 [7894341](/contest/468/submission/7894341 "Submission 7894341 by apia") 95 96 **Solution 2:** 97 98 We can use binary search to find the minimal *d* that *g*(*d*) ≥ *a*, *g*(*d*) ≥ 2*a*, ... 99 100 This solution is similar to the first one. 101 102 [7894452](/contest/468/submission/7894452 "Submission 7894452 by apia") 103 104 **Solution 3:** 105 106 We can use binary search to find the minimal *d* that *g*(*d*) ≥ *a*. And we use two pointers to maintain an interval [*l*, *r*] that  until we find . 107 108 I can't prove the correctness of this algorithm, but it performs well in practice. 109 110 [7894356](/contest/468/submission/7894356 "Submission 7894356 by apia") 111 112 **Solution 4:** 113 114 Thanks [ZhouYuChen](/profile/ZhouYuChen "Candidate Master ZhouYuChen") for his talented idea. 115 116 If *x* < 1018, we can get *f*(1018 + *x*) = *f*(*x*) + 1. That means if we shift the interval [*x* + 1, *x* + 1018] by 1, the result will be increase by 1 too. And it also not hard to find that *g*(10*x*) = 45 * *x* * 10*x* - 1. So if , [*a* - *x*, *a* - *x* + 1018 - 1] is the answer. 117 118 It's easy to see that upper bound of the answer is *a*, because of pigeonhole principle (among *g*(0), *g*(1), ..., *g*(*a*) at least two are equal). So big integer is not required in this problem. 119 120 If solution 3 is correct, the upper bound of the answer can be 2 * 1016. 121 122 [7878473](/contest/468/submission/7878473 "Submission 7878473 by ZhouYuChen") 123 124 **Bonus:** 125 126 Prove or disprove that solution 3 is correct. 127 128 [468D - Tree](/contest/468/problem/D "Codeforces Round 268 (Div. 1)") 129 130 I am sorry that this problem coincides with [that one](http://acm.hdu.edu.cn/showproblem.php?pid=4118). 131 132 *d*(*u*, *v*) = *dep**u* + *dep**v* - 2 * *dep**LCA*(*u*, *v*), so the answer is: 133 134  135 136 *dep**i* there means the distance between node *i* and root. 137 138 We choose centroid of tree as root (let's denote it *u*), so we can make every pair (*i*, *p**i*) are in different subtrees, that means *dep**LCA*(*i*, *p**i*) = 0. 139 140 So the answer is . 141 142 The next part of this problem is find the lexicographically smallest solution. 143 144 We regards it as finding the lexicographically smallest matching in a bipartite graph. 145 146 For a subtree, if the amount of nodes in this subtree in the left part > the amount of nodes not in this subtree in the right part, the perfect matching doesn't exist. So the amount of nodes in this subtree in the left part + the amount of nodes in this subtree in the right part should be no more than the amount of nodes unmatched, while the root is an exception. 147 148 We can use a segment tree to maintain it easily. We determined the minimum possible *p**i* from 1 to *n*. If there is a subtree that the amount of nodes in this subtree in the left and right part is equal to the amount of nodes unmatched, we must select a node from it, so *p**i* equal to the node in this subtree with the minimum id. Otherwise, we can choose a node with the minimum id that is not in the same subtree with *i*. 149 150 [7894417](/contest/468/submission/7894417 "Submission 7894417 by apia") 151 152 [468E - Permanent](/contest/468/problem/E "Codeforces Round 268 (Div. 1)") 153 154 The permanent can be obtained as follows: for each (*e*1, *e*2, ..., *e**t*) such that *x*1, *x**e*2..., *x**e**t* are distinct and *y**e*1, *y**e*2, ..., *y**e**t* are distinct, add  to the answer. 155 156 It can be proved by the formula : 157 158 , 159 160 where *s* and *t* are subsets of the same size of {1, 2, ..., *n*} and ,  are their respective complements in that set. 161 162 Construct a undirected graph *G* with 2*n* vertices *v*1, *v*2, ..., *v*2*n*, where the edge weight between vertex *v**i*, *v**n* + *j* is *A**i*, *j* - 1. We only need to know the sum of weight of all matchings that we choose *t* edges. The weight of matching is the product of all edge weights in the matching. 163 164 We only need to know the sum of the weights that we choose *x* edges in the each connected components. 165 166 The number of nodes in a connected component is *s* and the number of edges in this connected component is *t*. 167 168 Algorithm 1: 169 170 Because it's a bipartite graph, so the number of vertices in one part is at most *s* / 2. So we can use state compressed dp to calculate the ways to choose *x* edges in this connected component. The complexity is *O*(2*s* / 2 * *s*2). 171 172 Algorithm 2: 173 174 We can choose a spanning tree. The number of edges in spanning tree of these vertices is *s* - 1, and the number of non-tree edges is *t* - *s* + 1. So we can enumerate all the non-tree edge, use tree dp to calculate the ways. The complexity is *O*(2*t* - *s* * *s*2). 175 176 Combined with these two algorithm, the complexity is *O*(*min*(2*s* / 2, 2*k* - *s*) * *s*2)) = *O*(2*k* / 3 * *k*2).