codeforces-scrape

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

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.