1696.md (14760B)
1 Source: https://codeforces.com/blog/entry/103479 2 3 Thanks for participation! 4 5 If your solution to D involves any data structures and is not $O(n)$ -- please read the "solution 1". I believe it is very interesting, but to make the difficulty suitable for D we allowed not $O(n)$ solutions. 6 7 [1696A - NIT orz!](/contest/1696/problem/A "Codeforces Global Round 21") 8 9 **Hint 1** 10 11 How many operations will we perform? 12 13 **Answer** 14 15 At most one. Why? 16 17 **Solution** 18 19 Suppose we can only perform exactly one operation. In this case the answer is $S=\max_{1\le i\le n}(a_i\mathrm{\ or\ }z)$. In fact, we can prove that this is the answer. 20 21 Define $a_i'$ as the value of $a_i$ after some operations. 22 23 It suffices to prove the answer will never exceed $S$. Note that $z$ will always become a submask of itself after any number of operations, so $a_i$ will always be a submask of $(a_i\mathrm{\ or\ }z)$ after any number of operations. This leads to the conclusion that $a_i'\le (a_i\mathrm{\ or\ }z)$ for all $i$. Thus $\max_{1\le i\le n} a_i'\le \max_{1\le i\le n}(a_i\mathrm{\ or\ }z)=S$. 24 25 Time complexity is $O(n)$. 26 27 [1696B - NIT Destroys the Universe](/contest/1696/problem/B "Codeforces Global Round 21") 28 29 **Hint 1** 30 31 How many operations will we perform? 32 33 **Answer** 34 35 At most two. Why? 36 37 **Hint 2** 38 39 How to check if the array can be destroyed in $0$ or $1$ operations? 40 41 **Solution** 42 43 The answer is at most $2$, because doing the operation on $[1,n]$ at most twice will always work. (If the array contains at least one zero, we need $2$ operations. Otherwise we need $1$ operation.) 44 45 If the array consists of zeroes, the answer is $0$. 46 47 If all non-zero elements form a contiguous segment in the array, the answer is $1$. To check this, you can find the leftmost and rightmost occurrence of non-zero elements and check if elements in the middle of them are also non-zero. 48 49 Otherwise the answer is $2$. 50 51 Time complexity is $O(n)$. 52 53 [1696C - Fishingprince Plays With Array](/contest/1696/problem/C "Codeforces Global Round 21") 54 55 **Hint 1** 56 57 The operation is reversible. (The two operations are reverses of each other.) 58 59 **Hint 2** 60 61 Try to find a middle state, such that we can turn both $a$ and $b$ into it. 62 63 **Solution** 64 65 Call the first operation "expand" and the second operation "shrink". 66 67 Keep doing expand on both arrays until we can't do expand anymore, call the resulting arrays $a'$ and $b'$. It suffices to check if $a'=b'$. To implement this, you need to compress contiguous equal numbers. 68 69 Proof of why this is necessary and sufficient: 70 71 * Sufficiency is obvious, since the operations are reversible. We can do something like $a\to a'=b'\to b$. 72 * Necessity: Let $f(a)=a'$. It suffices to prove that an operation on $a$ does not affect $f(a)$. An expand operation obviously doesn't affect $f(a)$. A shrink operation shrinks $a[i,i+m-1]$ into one element. When computing $f(a')$, we will always expand $a'_i$ at some time, so the result is the same as $f(a)$. 73 74 Time complexity is $O((n+k)\log_m V)$, where $V=\max a_i$. 75 76 [1696D - Permutation Graph](/contest/1696/problem/D "Codeforces Global Round 21") 77 78 This problem has two different solutions. The first one is more beautiful, but less straight-forward. 79 80 **Hint 1 for solution 1** 81 82 The solution is $O(n)$. We don't need any data structures. 83 84 **Hint 2 for solution 1** 85 86 Instead of trying to construct the shortest path from $1$ to $n$, find a "transfer vertex" that we must pass through. 87 88 **Answer** 89 90 We will always pass through the position of the maximum element in the array. 91 92 **Hint 3 for solution 1** 93 94 Suppose the maximum element is $a_k$. Solve recursively for $dis(1,k)$ and $dis(k,n)$. 95 96 **Solution 1** 97 98 Denote $dis(x,y)$ as the length of the shortest path between $x$ and $y$. 99 100 Consider a position $i$ that $a_i=n$. Assume $i\ne 1$ and $i\ne n$. For a segment that passes $i$, its maximum element is always $a_i$. Thus, for $x \lt i \lt y$, $x$ and $y$ will never be directly connected by an edge. This means that when going from $1$ to $n$, we have to pass $i$. Let us solve recursively for $dis(1,i)$ and $dis(i,n)$. For example, we solve for $dis(1,i)$. 101 102 We already know that $a_i=n$, so $i$ is the maximum element in $[1,i]$. Consider the minimum element in $[1,i]$, suppose it is $a_j\ (j \lt i)$. From similar arguments, we can solve recursively for $dis(1,j)$ and $dis(j,i)$. However, note that $dis(j,i)$ equals to $1$: since $j$ and $i$ are respectively minimum and maximum in $[1,i]$, they have to be minimum and maximum in $[j,i]$ as well. So $i,j$ must be directly connected. Thus, we only need to solve recursively for $dis(1,j)$. 103 104 The process with $dis(i,n)$ is similar. Note that we will only call $dis(l,r)$ for $l=1$ or $r=n$ (if not, the return value is always 1), so it suffices to pre-compute prefix and suffix minimums and maximums. 105 106 The time complexity is $O(n)$. 107 108 **Hint 1 for solution 2** 109 110 Look at the last sample test case. Think of a simple greedy. 111 112 **Answer** 113 114 Keep going to the rightmost vertex (the vertex with the largest id) works. 115 116 **Hint 2 for solution 2** 117 118 Use data structures to simulate the process. How? 119 120 **Solution 2** 121 122 We can prove that keep going to the vertex with the largest index is a correct strategy. The proof is left as an exercise :) Hint: try to prove that the path we will visit is the same as the path we visited in solution 1. 123 124 Suppose we are at $i$. We want to find the largest $j \gt i$ such that $i$ and $j$ are directly connected. WLOG, assume $a_{i+1} \lt a_i$. Then, it cannot be the case that $a_j \gt a_i$, since none of $a_i,a_j$ will be $mn(i,j)$. Thus $a_j \lt a_i$. It follows that all $i \lt k \lt j$ satisfies $a_k \lt a_i$, otherwise none of $a_i,a_j$ will be $mx(i,j)$. 125 126 Let $r_i$ be the largest $p$, such that for all $t\in [i+1,p]$, $a_t \lt a_i$. From the arguments above we know $j\in [i+1,r_i]$. $r_i$ can be pre-computed with a stack, or binary search + some data structures. 127 128 Let $j_0$ be the position of the minimum element in $[i+1,r_i]$. Obviously $j_0$ is directly connected with $i$. For any $j_0 \lt k\le r_i$, $mn(i,k)$ will be $a_{j_0}$, showing that all such $k$ is not directly connected with $i$. Thus, $j_0$ is the desired $j$. 129 130 If we use data structures for range minimum, we get a $O(n\log n)$ solution, which can easily pass (not sure whether $O(n\log^2 n)$ ones will pass though, the large constraints were intended to cut those). 131 132 However, by building the cartesian tree of the array and doing proper pre-computations, we can optimize this solution to $O(n)$. 133 134 [1696E - Placing Jinas](/contest/1696/problem/E "Codeforces Global Round 21") 135 136 **Hint 1** 137 138 Try to find out the number of operations we do on a specific cell $(i,j)$, call it $f(i,j)$. 139 140 **Hint 2** 141 142 Write the recurrence formula for $f(i,j)$. What is $f(i,j)$? 143 144 **Answer** 145 146 $f(i,j)=\binom{i+j}j$ 147 148 **Hint 3** 149 150 The answer is the sum of $f(i,j)$ over all white cells $(i,j)$. Use some combinatorics formula to speed it up. 151 152 **Solution** 153 154 Let us find out the number of operations we do on a specific cell $(i,j)$, call it $f(i,j)$. 155 156 Every operation done on $(i-1,j)$ will lead to one doll on $(i,j)$, thus consuming one operation on $(i,j)$. Similar observation holds for $(i,j-1)$. 157 158 Thus, $f(i,j)=f(i,j-1)+f(i-1,j)$ (given that $(i,j),(i-1,j),(i,j-1)$ are all white cells). Note that $a$ is non-increasing: this means that if $(i,j)$ is white, $(i-1,j),(i,j-1)$ will both be white. So we can conclude that $f(i,j)=f(i,j-1)+f(i-1,j)$ always holds as long as $(i,j)$ is white. 159 160 Another way to see the formula is $f(i,j)$ is the number of ways to go from $(0,0)$ to $(i,j)$, only going down or right by 1 step. This implies that $f(i,j)=\binom{i+j}j$. 161 162 From this, we know that the answer is $\sum_{i=0}^n\sum_{j=0}^{a_i-1} \binom{i+j}{i}$. With the equation $\sum_{i=0}^k\binom{n+i}n=\binom{n+k+1}{n+1}$, we know that the answer is $\sum_{i=0}^n\binom{i+a_i}{i+1}$. 163 164 The time complexity is $O(n+V)$, where $V=\max a_i$. 165 166 [1696F - Tree Recovery](/contest/1696/problem/F "Codeforces Global Round 21") 167 168 **Hint 1** 169 170 The solution does not contain painful casework and deadly implemention. 171 172 **Hint 2** 173 174 Suppose we aleady know edge $(i,j)$ exists in the tree. What can we know from it? 175 176 **Answer** 177 178 We can immediately recover the whole tree. 179 180 **Solution** 181 182 Read the hints first to understand the solution better. 183 184 Construct a graph with $\binom n2$ vertices $(1,2),(1,3),\dots,(n-1,n)$. 185 186 If $dis(a,b)=dis(b,c)$, link an undirected edge between $(a,b)$ and $(b,c)$. 187 188 Observe that all edges in the tree form a connected component of size exactly $n-1$ in the graph! 189 190 Find all components of size $n-1$ and try if all vertices in it form a tree that satisfy the input. There are at most $\dfrac n2$ such components, so complexity is $O(n^4)$. Proper pre-computation and the usage of bitsets can reduce the complexity to $O(n^4/w)$. 191 192 [1696G - Fishingprince Plays With Array Again](/contest/1696/problem/G "Codeforces Global Round 21") 193 194 **Hint 1** 195 196 What kind of problem is this problem? 197 198 **Answer** 199 200 Linear programming. 201 202 **Hint 2** 203 204 Consider the dual. 205 206 **Hint 3** 207 208 Consider the case when $n=2$. Draw the linear programming on a xOy-coordinate. Try to observe what the answer might be. 209 210 **Solution** 211 212 First we solve the problem with only 1 query on the whole array $A$. 213 214 This is a linear programming problem: 215 216 $ \text{minimize}\sum_{1\le i \lt n} a_i+b_i \\ Xa_1+Yb_1\ge A_1 \\ Xa_i+Yb_i+Ya_{i-1}+Xb_{i-1}\ge A_i\ (2\le i \lt n) \\ Ya_{n-1}+Xb_{n-1}\ge A_n \\ a_i,b_i\ge 0 $ 217 218 Consider its dual: 219 220 $ \text{maximize}\sum_{1\le i\le n}A_ix_i \\ Xx_i+Yx_{i+1}\le 1\ (1\le x \lt n) \\ Yx_i+Xx_{i+1}\le 1\ (1\le x \lt n) \\ x_i\ge 0 $ 221 222 Suppose $X\le Y$. Now we will prove that there exists an optimal solution to the dual problem, in which $x_i$ can only take three values: $1/Y,1/(X+Y),0$. 223 224 The proof is as follows: It is well-known that an optimal solution to a linear programming problem must lie on a vertex of the "multi-dimensional convex polygon" which the restrictions surround. Thus we are only interested in $x_i$ that satisfy several "=" restrictions (and the restrictions should really intersect at one point, meaning that those "=" should uniquely determine $x$). Consider any "sufficient" (that means they uniquely determine ${x}$) subset of them. If one restriction is related to $x_p,x_q$, we link an undirected edge between $p$ and $q$. If one restriction is only related to $x_p$ (i.e. $x_p=0$), we link a self-loop on $p$. "Being sufficient" means that all connected components in the graph has exactly one cycle. However, for an edge $(u,v)$, we know that either $u=v+1$ or $u=v$. This means that all cycles can only be $(i\to i+1\to i)$ or $i\to i$. If a cycle is $(i\to i+1\to i)$, all $x_i$ in the component are $1/(X+Y)$; If a cycle is $i\to i$, all $x_i$ in the component are $1/Y$ or $0$ (not $1/X$, because it exceeds the constraints). 225 226 Thus we can use dp to solve the dual problem. Let $dp(i,0/1/2)$ be the maximum $\sum_{j\le i}A_jx_j$ when $x_i$ is the $0/1/2$-th candidate above. Transitions are straight-forward. 227 228 For multiple queries, the transitions can be written into multiplying matrices, and we can use segment tree to maintain updates. 229 230 About precision issues: actually we can avoid using floating point numbers completely. Note that all numbers in this problem are fractions with denominator $Y(X+Y)$. Also note that the answer does not exceed $(\sum a_i)/Y$. This means that the numerator does not exceed $(\sum a_i)\times (X+Y) \lt 10^{18}$, so we can use long long-s to only store numerators. If you use double in C++, the relative error of one operation is less than $10^{-15}$. $10^{-15}\times n \lt 10^{-9}$, which means that using doubles is also enough. 231 232 Complexity: $O(n+q\log n)$. 233 234 [1696H - Maximum Product?](/contest/1696/problem/H "Codeforces Global Round 21") 235 236 **Hint 1** 237 238 Find a way to calculate the maximum product that can be turned into counting. 239 240 **Hint 2** 241 242 Use monotonicity to reduce the complexity. 243 244 **Solution** 245 246 First, we describe a strategy to find the answer for a single subset. If the whole subset is negative, the answer is the product of the $K$ maximum numbers in it. Otherwise, take $K$ numbers with the maximum absolute value. If there is an even number of negative numbers in those numbers, we're done. Otherwise, find the smallest positive element and change it to the absolute-value-maximum negative element unchosen, or find the largest negative element and change it to the maximum positive element unchosen. We either do the first change or do the second change. 247 248 This gives a direct dp solution. Take all $a_i$ and sort them into two arrays consisting of positive and negative ones (0 goes to arbitary one), $pos$ and $neg$, sorted by absolute values. By calculating $fpos(i,k)$: the sum of the product of the largest $K$ numbers of all subsets of $pos[1\dots i]$ that contain $pos_i$, and $fneg(i,k)$ similarly, and $gneg(i,k)$, the sum of the product of the absolute value smallest $K$ numbers of all subsets of $neg[i\dots |neg|]$ that contain $neg_i$, and enumerating the following, we can solve the original problem in $O(n^5)$: 249 250 * the number of positive elements in the $K$ numbers with the maximum absolute value in our calculating subset, $p$. 251 * the smallest positive element in the $K$ numbers with the maximum absolute value, $pos_i$. 252 * the greatest negative element in the $K$ numbers with the maximum absolute value, $neg_j$. 253 * (if $p$ is odd) the greatest positive element not in the $K$ numbers with the maximum absolute value, $pos_k$. 254 * (if $p$ is odd) the smallest negative element not in the $K$ numbers with the maximum absolute value, $pos_l$. 255 256 The contribution to the answer can be represented as the sum of product of $fpos,fneg$, and powers of two. I left the details as an exercise. 257 258 However, notice that the "enumerating $k,l$" part has nothing to do with $p$, so we can pre-calculate the contribution of $k,l$ for every pair $(i,j)$, giving an $O(n^4)$ algorithm. 259 260 What's more, for fixed $i,j,k$, the $l$-s that we do the first change is a prefix/suffix of all $l$, and $l$-s that we do the second change is a prefix/suffix of all $l$. So with two pointers and prefix sums, we can pre-calculate the contribution of every $(i,j)$ in $O(n^3)$, which is fast enough. 261 262 You might be afraid that $600^3$ is too slow for 1.5 seconds. However, the two $O(n^3)$ parts of the algorithm actually run in $O(n\times cntpos\times cntneg)$ ($cntpos,cntneg$ are the number of positive/negative integers in the array), leading to an at most $1/4$ constant factor. Thus, the algorithm actually runs very fast (less than 0.25 seconds). However for similar constant factor reasons, the $O(n^4)$ solution only takes about 6.5 seconds on Codeforces, so we had to set a seemingly-tight limit.