1549.md (19652B)
1 Source: https://codeforces.com/blog/entry/93586 2 3 All the division 2 problems were created by [Agnimandur](/profile/Agnimandur "Master Agnimandur"). [1548E - Gregor and the Two Painters](/contest/1548/problem/E "Codeforces Round 736 (Div. 1)") was created by [Benq](/profile/Benq "Legendary Grandmaster Benq"). I hope that this hint-based editorial helps you, no matter what your rating is! Solution code is provided in both C++, Java, and Kotlin when available. 4 5 ### [Solution Code Repository](https://github.com/Agnimandur/Round736Solutions) 6 7 ## [1549A - Gregor and Cryptography](/contest/1549/problem/A "Codeforces Round 736 (Div. 2)") 8 9 **Hint 1** 10 11 Fix $a$ into a convenient constant. 12 13 **Solution** 14 15 Since $P \ge 5$ and is also a prime number, we know that $P-1$ is an even composite number. A even composite number is guaranteed to have at least 2 unique divisors greater than 1. Let two of these divisors be $a$ and $b$. It is guaranteed that $P\mod{a} = P\mod{b} = 1$, and thus this selection is valid. 16 17 For example, we can simply pick $a=2$ and $b=P-1$, and we will get a correct solution. 18 19 The time complexity is $\mathcal{O}(Q)$. 20 21 ## [1549B - Gregor and the Pawn Game](/contest/1549/problem/B "Codeforces Round 736 (Div. 2)") 22 23 #### Solution 1 24 25 **Hint 1** 26 27 There a very limited number of squares where each of Gregor's pawns could end up. 28 29 **Hint 2** 30 31 Identify a greedy strategy to maximize the answer. 32 33 **Solution** 34 35 The key insight is that due to the fact that there is only one row of enemy pawns, and those pawns never move, there are only $3$ possible columns where one of Gregor's pawns can end up in. 36 37 We can solve this problem greedily, going from column $1$ to column $N$. At the current column $j$, if Gregor has a pawn in this column, then we greedily consider 3 cases. 38 39 * If there is an uncaptured enemy pawn in column $j-1$, mark that pawn as captured and increment the answer. Column $j-1$ will never be looked at again, so this decision is optimal. 40 * If there is no pawn in column $j$, just move Gregor's pawn forward, and increment the answer. 41 * If there is an uncaptured enemy pawn in column $j+1$, mark that pawn as captured and increment the answer. 42 * Otherwise, this pawn will not reach the first row. 43 44 This greedy solution is guaranteed to produce the maximum possible answer. 45 46 The time complexity is $\mathcal{O}(N)$. 47 48 #### Solution 2 49 50 **Hint 1** 51 52 Write the problem as a graph problem. 53 54 **Hint 2** 55 56 Valid captures or valid forward moves represent edges in the graph. 57 58 **Hint 3** 59 60 We have two sets: Gregor's pawns, and destination squares. We also have some edges between these two sets. 61 62 **Hint 4** 63 64 Maximum Matching. 65 66 **Solution** 67 68 Each of Gregor's pawns can end up in one of 3 possible squares. If Gregor has a pawn in column $i$, it can end up in column $i-1$ or $i+1$ if there is an enemy pawn in those columns. Furthermore, it can remain in column $i$ if there is no enemy pawn in that column. 69 70 Let's build a graph $G$, where each edge connects one of Gregor's pawns to a valid destination cell. Since every edge goes from a cell in the bottom row to a cell in the top row, $G$ is clearly bipartite. It's now clear that moving as many pawns to the end is equivalent to finding a maximum matching in $G$. 71 72 The time complexity is $\mathcal{O}(N\sqrt{N})$ using the HKK algorithm for maximum matching. ($G$ has at most $2N$ vertices, and $6N$ edges) 73 74 ## [1549C - Web of Lies](/contest/1549/problem/C "Codeforces Round 736 (Div. 2)") 75 76 **Hint 1** 77 78 For various graphs, try and simulate the process. Determine a rule to figure out whether a noble survives or not. 79 80 **Hint 2** 81 82 When you add or remove a single edge, how much can the answer change by? Try and recalculate the answer in $\mathcal{O}(1)$. 83 84 **Solution** 85 86 Due to the queries, actually simulating the process each time will be too expensive. 87 88 Proof that the Process will End: Assume after round $x$, $x_i$ nobles are killed. If $x_i=0$, then the state of the graph doesn't change, so the process will have ended. If $x_i \gt 0$, then the number of nobles decreases. Thus, the maximum number of rounds the process can last is $N$, so it must end. 89 90 $\textbf{Lemma 1:}$ At the end of the process, no two nobles will still be friends. 91 92 Proof by Contradiction: Assume that nobles $u$ and $v$ (assume WLOG that $u \lt v$) are still friends and the process is over. In order for $u$ to avoid being killed, there must be a noble $w$ weaker than $u$ that is also a friend of $u$. The same logic then applies to $w$, and we have an infinite descent argument. There are only a finite number of nobles weaker than $u$, so there will be a contradiction. 93 94 $\textbf{Lemma 2:}$ If all of a noble's friends are weaker than it, that noble cannot be killed. 95 96 Direct Proof: Since none of the noble's friends are stronger than it, it is impossible for $\textit{all}$ of them to be stronger at any point in the process. 97 98 $\textbf{Final Idea:}$ By combining Lemmas 1 and 2, we can prove that if ALL of a noble's friends are weaker than it, that noble survives, otherwise it will die. This leads to the solution. 99 100 Maintain in an array the number of nobles weaker than noble $i$. Since the updates guarantee that the edge being removed/added does/doesn't exist respectively, we only need to keep track of the number of edges of each noble. Essentially, a noble survives if and only if `weaker[i]==edges[i]`. After linear precomputation, updates and queries take constant time. 101 102 The time complexity is $\mathcal{O}(N+M+Q)$. 103 104 ## [1549D - Integers Have Friends](/contest/1549/problem/D "Codeforces Round 736 (Div. 2)") 105 106 **Hint 1** 107 108 Let's say the subarray $A_i \dots A_j$ is all congruent to $n\mod{m}$. What does that imply about the subarray? 109 110 **Hint 2** 111 112 What does the previous hint imply about the difference array generated by $D[i]=A[i+1]-A[i]$? 113 114 **Hint 3** 115 116 GCD 117 118 **Solution** 119 120 The key observation is to construct the difference array $D$ of size $N-1$, where $D[i]=abs(A[i+1]-A[i])$. If a given subarray is a friend group, then every difference is a multiple of some $m$. Since every element of $A$ is distinct, the case when $D[i]=0$ can be ignored. 121 122 We can now convert this into a GCD (greatest common divisor) problem. It follows that $A[i\dots j]$ is a friend group if and only if $\gcd{(D[i\dots j-1])} \gt 1$. Indeed, the value $m$ that we want is equal to this GCD. 123 124 To solve the problem, we can use a sparse table or a segment tree to find the largest possible subarray beginning at $i$, and then max over all subarray answers to get the final answer. 125 126 The time complexity is $\mathcal{O}(N\log{N}\log{10^{18}})$. The first log is for the sparse table, the second is for computing GCDs. 127 128 Note that the de facto time complexity may be closer to $\mathcal{O}(N\log{N}+N\log{10^{18}})$, due to the [insights from this blog post](https://codeforces.com/blog/entry/63771). 129 130 ## [1549E - The Three Little Pigs](/contest/1549/problem/E "Codeforces Round 736 (Div. 2)") 131 132 #### Solution 1 133 134 **Hint 1** 135 136 Convert the word problem into a combinatorics equation. 137 138 **Hint 2** 139 140 Write the equation for some $x$. Write the equation for $x+1$. How can we easily transition from the first to the second equation? 141 142 **Hint 3** 143 144 For a given $x$, we want to calculate every third term in the sequence $\binom{i}{x}$ for $i \in [1,3N]$. Think about how computing the entire summation $\sum_{i=1}^{3N}{\binom{i}{x}}$ will help. 145 146 **Solution** 147 148 For a given $x$, we want to compute $\sum_{i=1}^{N}{\binom{3i}{x}}$, which can be solved with a combinatorial dynamic programming. 149 150 Define the array `dp[x][m]` (dimensions: $N+1\times 3$), which computes the sum $\sum_{i=0}^{N-1}{\binom{3i+m}{x}}$. Under this definition, $ans[x]=dp[x][0]+\binom{3N}{x}$, where `ans` is what we want to find. 151 152 Under the definition of the dp, we can make the following mathematical observations. 153 154 $dp[x][0]+dp[x][1]+dp[x][2]=\sum_{i=0}^{3N-1}{\binom{i}{x}}$, since term $i$ belongs to the array with $m=i\mod{3}$. This summation can be condensed with the Hockey Stick Identity into $\binom{3N}{x+1}$. 155 156 By repeated uses of Pascal's Identity, we get equations (2) and (3), giving us a system of 3 equations with 3 new unknowns, which can easily be solved. 157 158 1. $\sum_{m=0}^{2}{dp[x][m]}=\binom{3N}{x+1}$. 159 2. $dp[x][1] = dp[x][0]+dp[x-1][0]$ 160 3. $dp[x][2] = dp[x][1]+dp[x-1][1]$ 161 162 The base case is that $dp[0][0]=dp[0][1]=dp[0][2]=N$. Each query can now be answered trivially. 163 164 The time complexity is $\mathcal{O}(N+Q)$ with combinatorial precomputation. 165 166 #### Solution 2 167 168 **Hint 1** 169 170 Convert the word problem into a combinatorics equation. 171 172 **Hint 2** 173 174 How will the Binomial Theorem be helpful? 175 176 **Hint 3** 177 178 Try and construct a polynomial $P(k)$ such as the coefficient $k^x$ in that polynomial represents the number of attack plans if the wolf wants to eat $x$ pigs. 179 180 **Hint 4** 181 182 Notice that $P(k)$ is a geometric series, so FFT is unnecessary. 183 184 **Solution** 185 186 Define the polynomial $P(k)=(1+k)^3+(1+k)^6+\cdot + (1+k)^{3N}$. 187 188 The coefficient of $k^x$ in $P(k)$ is, by the Binomial theorem on each term of the polynomial, equal to $\binom{3}{x}+\binom{6}{x}+\dots + \binom{3N}{x}$. This is equal to `ans[x]` from the previous solution. 189 190 The only thing left to do is quickly calculate $P(k)$. Due to the tight time limit, calculating the polynomial using FFT in $\mathcal{O}{(N\log{N})}$ is probably too slow. 191 192 Instead, we notice that $P(k)$ is a geometric series. Using the geometric series formula, we get that $P(k)=\frac{(1+k)^{3N+3}-(1+k)^3}{(1+k)^3-1}$. 193 194 The numerator and denominator of this fraction can be expanded in linear time. Then all we have to do is a polynomial long division. Once we have $P(k)$, we can answer all the queries trivially. 195 196 The time complexity is $\mathcal{O}(N)$ with combinatorial precomputation. 197 198 ## [1549F1 - Gregor and the Odd Cows (Easy)](/contest/1549/problem/F1 "Codeforces Round 736 (Div. 2)") 199 200 **Hint 1** 201 202 "Enclosed cows" are just interior points. It's clear that Pick's Theorem will be useful. 203 204 **Hint 2** 205 206 Manipulate Pick's Theorem into a modular equation. 207 208 **Hint 3** 209 210 The number of boundary points between $(x_1,y_1)$ and $(x_2,y_2)$ is $\gcd{(x_1-x_2,y_1-y_2)}$. 211 212 **Hint 4** 213 214 Working with relevant formulas, find a simple condition between two points, such that they can be treated as equivalent. 215 216 **Solution** 217 218 Every set of 3 fenceposts forms a lattice triangle We want to find the number of such lattice triangles that have an odd number of interior points. Since all the coordinates are even, the area is automatically even as well. By Pick's Theorem, $area=I+\frac{B}{2}-1$, so $2\cdot area=2I+B-2$. $I$ is the number of interior points, and $B$ is the number of boundary points, for an arbitrary triangle formed by 3 fenceposts. 219 220 Let $A=2\cdot area$, so $A=2I+B-2$. Since $I$ is odd, taking both sides modulo 4 we get that $A \equiv B\mod{4}$. Since the area is an even integer, $A$ is a multiple of 4, so we get that $A\equiv B\equiv 0\mod{4}$. 221 222 Let's define the $\textbf{boundary count}$ of a segment to be the number of lattice points on it, minus 1. It can be proven that the boundary count of the segment connecting $(x_1,y_1)$ and $(x_2,y_2)$ is $\gcd{(|x_2-x_1|,|y_2-y_1|)}$. 223 224 In this problem, we only care about what the boundary count is modulo 4. Since all the coordinates are even, the GCD is guaranteed to be even, so the boundary count is either 0 or 2 mod 4. For the segment connecting $(x_1,y_1)$ and $(x_2,y_2)$ call its boundary count $b$. 225 226 * $b\equiv 0\mod{4}$ IFF $x_1\equiv x_2 \mod{4}$ AND $y_1\equiv y_2 \mod{4}$. 227 * $b\equiv 2\mod{4}$ in all other situations. 228 229 $\textbf{Key Idea:}$ Turn fence post $(x,y)$ into $(x\mod{4},y\mod{4})$. 230 231 Writing the area of a triangle via the shoelace formula, it becomes obvious that the area mod 4 won't change when the coordinates are modded by 4. Additionally, by our work above, $B$ (the sum of the boundary counts for the 3 sides of the triangle) is entirely dependent on the coordinates mod 4. 232 233 Let `cnt[x][y]` be an array counting the number of points that fall into each category based on the key idea above. Since all coordinates are even, only 4 elements in the $cnt$ array will be nonzero. We can fix each point of the triangle into one of the categories, quickly calculuate $A$ and $B$, and solve the problem. Be careful not to overcount triangles. 234 235 The time complexity is $\mathcal{O}(N)$, with a small constant for the counting. 236 237 ## [1549F2 - Gregor and the Odd Cows (Hard)](/contest/1549/problem/F2 "Codeforces Round 736 (Div. 2)") 238 239 **Hint 1** 240 241 Solve the easy version of the problem. 242 243 **Hint 2** 244 245 Taking each coordinate modulo 4 no longer works. This is because if $\Delta{x}$ or $\Delta{y}$ are odd, there's no way to predict whether the boundary count (see editorial of the easy version) is 1 or 3 mod 4. 246 247 **Hint 3** 248 249 By playing with Pick's Theorem, you should find that $B$ (the total number of boundary points) has to be even. Let $b_1$, $b_2$, and $b_3$ be the boundary count of the three sides of a lattice triangle. 250 251 **Hint 4** 252 253 Lets count the answer. Fix a point. Fix the boundary count mod 4 of the two sides adjacent to that point. Fix more things. 254 255 **Hint 5** 256 257 In Hint 4, we fixed a point. It's critical that you fix the boundary count of the side opposite that point to be even. 258 259 **Solution** 260 261 First read (and understand!) the editorial for the easy version of the problem. 262 263 * Definition: The $\textbf{modularity}$ of a point `(x,y)` is `(x%4,y%4)`. 264 * Definition: The $\textbf{boundary count}$ of a segment is the number of lattice points on that segment, minus 1. 265 266 Lets precompute the array `cnt[i][x][y][b]` (dimensions $N\times 4\times 4\times 4$), which equals the number of other points respective to `points[i]` with modularity $(x,y)$ and with a boundary count mod 4 equal to $b$. This precomputation can be done in $\mathcal{O}(N^2 \log{10^7})$ time, by iterating over every pair of points. The boundary count of the segment $(x_1,y_1)$ to $(x_2,y_2)$ is $\gcd{(|x_2-x_1|,|y_2-y_1|)}$. 267 268 Consider the number of boundary points on the three sides of a triangle, and call them $b_1,b_2,b_3$. Clearly, $B=b_1+b_2+b_3$. The key idea is that since $B$ is even, wlog we can assume that $b_3$ is even, and that $b_1 \equiv b_2 \mod{2}$. The other key idea is that it is easy to figure out if the boundary count is congruent to 0 or 2 mod 4 based on the modularities of the coordinates alone, but it's impossible if the boundary count is odd. 269 270 Let's fix a point, and count the number of triangles that involve this point. Let's also iterate over all the relevant modularities of the other two points in the triangle, which range from $(0,0)$ up to $(3,3)$. Let's also make sure that there are an even number of boundary points on the side opposite the fixed point, which we know almost nothing about. It can be shown that $b_3 \equiv 0\mod{4}$ IFF $(x_1,y_1)=(x_2,y_2)$, and that $b_3 \equiv 2\mod{4}$ IFF $x_1,x_2$ have the same parity, and $y_1,y_2$ have the same parity, and the previous case doesn't apply. Finally, make sure that the parity of the boundary count of the two sides next to the fixed point are the same. 271 272 Using the precomputed array $cnt$ and the formula for $b_3$, we can quickly find $B$ in this case. Using the Shoelace Formula, we can quickly find what $A$ is modulo 4. If $A$ is even and equal to $B$, then we know that $I$ must be odd (in the easy version of the problem, we found that $A \equiv B \mod{4}$ IFF $I$ is odd), so all triangles in this class are interesting. Thus, we add to the answer a number roughly equal to $cnt[i][x_1][y_1][b_1]\cdot cnt[i][x_2][y_2][b_2]$ (it could be lower due to the potential overcount, if two points fall into the same bucket of the array). 273 274 Lastly, be sure not to overcount triangles! In my code, I count each of the `EEE` triangles ($b_1,b_2,b_3$ all even) 3 times, and the `OOE` triangles once. 275 276 The time complexity is $\mathcal{O}(N^2 \log{10^7})$ (the main part of the solution is approximately $\mathcal{O}(512N)$). 277 278 Implementation Note: The bottleneck of the algorithm is computing the GCDs. The simplest optimization that is sufficient for AC is to only calculate $\frac{N^2}{2}$ GCDs instead of all $N^2$ (since the GCD is commutative). Java requires additional optimizations, such as precomputing small GCDs. 279 280 ## [1548E - Gregor and the Two Painters](/contest/1548/problem/E "Codeforces Round 736 (Div. 1)") 281 282 **Hint 1** 283 284 Let's give each component a "representative" cell. Then our task is now to count the number of representatives. 285 286 **Hint 2** 287 288 Let the cell with the smallest amount of paint in a component be the representative. How can we find if a given cell $(i,j)$ is a representative or not? 289 290 **Solution** 291 292 This editorial was written by [Benq](/profile/Benq "Legendary Grandmaster Benq"), and inspired by [1392I - Kevin and Grid](/contest/1392/problem/I "Codeforces Global Round 10"). 293 294 For simplicity let's assume that all $a_i$ are distinct (and similarly, all $b_j$). If this is not the case, we may break ties arbitrarily. 295 296 Say that two badly painted cells are directly reachable from each other if they are in the same row or column and all cells in between them are also badly painted. Also, define the value of the cell at $(i,j)$ to be $a_i+b_j$. Call a badly painted cell a $\textbf{representative}$ if no cell directly reachable from it has a smaller value than it. 297 298 $\textbf{Claim:}$ Every connected component of badly painted cells contains exactly one representative. 299 300 $\textbf{Proof:}$ Clearly every connected component contains at least one representative; consider the cell(s) with the minimum value contained within it. To show that every connected component contains \textit{exactly} one representative, suppose that we are given a representative $(i,j)$ that is directly reachable from $(i',j)$ for all $i_l\le i'\le i_r$ and $(i,j')$ for all $j_l\le j'\le j_r$, where $a_i=\min_{i_l\le i'\le i_r}(a_{i'})$ and $b_j=\min_{j_l\le j'\le j_r}(b_{j'})$. Then the connected component containing $(i,j)$ is completely contained within the rectangle $[i_l,i_r]\times [j_l,j_r]$, and $(i,j)$ is the unique cell with the minimum value within that rectangle. This implies that a representative is always the unique cell with the minimum value within its connected component. 301 302 It remains to count the number of representatives. For each $i$, let $lo_i$ be the maximum index less than $hi_i$ such that $a_{lo_i} \lt a_i$ and $hi_i$ be the minimum index greater than $i$ such that $a_{hi_i} \lt a_i$. Then define $na_i$ to be $\min(\max_{i'\in [lo_i,i]}a_{i'},\max_{i'\in [i,hi_i]}a_{i'})$. Any path from a cell in row $i$ to a cell in the same column with lower value must pass through a row with value at least $na_i$. Define $nb_j$ for each $j$ similarly. It can be shown that $(i,j)$ is a representative if and only if the following conditions hold: 303 304 * $a_i+b_j\le X$ 305 * $na_i+b_j \gt X$ 306 * $a_i+nb_j \gt X$ 307 308 Computing $na$ and $nb$ can be done in $\mathcal{O}(N\log N+M\log M)$ with any data structure supporting range min/max queries (e.g. sparse tables), or in $O(N+M)$ with a stack. 309 310 It remains to count the number of pairs $(i,j)$ that satisfy these conditions given $a$, $na$, $b$, and $nb$. First initialize two binary indexed trees $T_a$ and $T_b$. Then sort the pairs $(na_i-a_i,a_i),(nb_j-b_j,b_j)$ in decreasing order. Now for every pair in the order, if it is of the form $(na_i-a_i,a_i)$, then add to the answer the number of elements of $T_b$ that are in the range $(X-na_i,X-a_i]$, and add $a_i$ to $T_a$. The reasoning for the case $(nb_j-b_j,b_j)$ is similar (query $T_a$, update $T_b$). 311 312 The time complexity is $\mathcal{O}(N\log{N}+M\log{M})$ for sorting the pairs and working with the two BITs.