codeforces-scrape

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

468.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 ![](https://espresso.codeforces.com/74059f117b185798017127422819e60382c5b43b.png), it's obvious that ![](https://espresso.codeforces.com/a3ba5e5d1ef1439737fc628285c04be47091594d.png). The contraposition of it is ![](https://espresso.codeforces.com/69e5b26ae9d80ee0632a870148b0badfb08e5f6c.png), that means if ![](https://espresso.codeforces.com/bff152b5ced9001de776fe156142deb10c0ac7ed.png), *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 ![](https://espresso.codeforces.com/485dd299eee4889ba9bb610b030e672d47930d27.png). ![](https://espresso.codeforces.com/9ce0950449051dacdd892bd89d6d039f7d2a5e83.png), so we should find a pair of number *a*, *b* that ![](https://espresso.codeforces.com/dc5d6d620f31703b166db3fbadd5a4ceeb92e970.png)
     87 
     88 **Solution 1:**
     89 
     90 First we choose *x* randomly. Then we can use binary search to find the minimal *d* that ![](https://espresso.codeforces.com/ef04db5550e30d43a88a54cdd57f3c6dbdac9c28.png) .
     91 
     92 So ![](https://espresso.codeforces.com/3901dfad8ed9de84d53d52f90b3dbfbda7b0377b.png) is very small, between 0 and ![](https://espresso.codeforces.com/ac5840445793a503997255a4a4a00ecb05c4e5ea.png). If ![](https://espresso.codeforces.com/6bdcb6d74968877a7ff91fcc5d26be821e1526da.png), after choosing *x* atmost 9 * *len* + 2 times, we can definitely find a pair that ![](https://espresso.codeforces.com/dc5d6d620f31703b166db3fbadd5a4ceeb92e970.png)
     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 ![](https://espresso.codeforces.com/362653c965909f74b1afa8a7ebafb4a2a2f663d3.png) until we find ![](https://espresso.codeforces.com/b686c86ca117fff32cfa943bd4f0468cc0b59641.png).
    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 ![](https://espresso.codeforces.com/d852c6fcf77dfa33e4bc216a9080b5ff6b7bd96c.png), [*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 ![](https://espresso.codeforces.com/c775174e649ec0507fbfc99b595a3c293c3580c2.png)
    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 ![](https://espresso.codeforces.com/a868bf70ea7259f795a1092fea44786f5e55aa91.png).
    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 ![](https://espresso.codeforces.com/eaa0973b7faac232d98bef1c121eb0df7ca89d9d.png) to the answer.
    155 
    156 It can be proved by the formula :
    157 
    158 ![](https://espresso.codeforces.com/921617faefc12bf5806eeb11bc92e59a4f650361.png),
    159 
    160 where *s* and *t* are subsets of the same size of {1, 2, ..., *n*} and ![](https://espresso.codeforces.com/6ec39de0d908746ce99b9a9e600dcd2c661a473f.png), ![](https://espresso.codeforces.com/ec0fc27161a12b55090dcfd9fad316c69db8652f.png) 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).