1900.md (11775B)
1 Source: https://codeforces.com/blog/entry/122677 2 3 [1900A - Cover in Water](/contest/1900/problem/A "Codeforces Round 911 (Div. 2)") 4 5 Author: [NemanjaSo2005](/profile/NemanjaSo2005 "Master NemanjaSo2005") 6 7 **Hint 1** 8 9 Assume that cells $i-1$, $i$, and $i+1$ are covered in water. What happens if you remove water from cell $i$? 10 11 **Hint 2** 12 13 The water at position $i$ is replaced as both cells $i-1$ and $i+1$ have water in them. 14 15 **Solution** 16 17 Read the hints. 18 19 If there are 3 consecutive empty cells $i-1$, $i$, $i+1$, we can place water in cells $i-1$ and $i+1$ and then move water from cell $i$ to all other cells. If there are no such cells, we have to place water on every empty cell. 20 21 So if we find substring ''...'' in the array, the answer is $2$, otherwise the answer is the number of empty cells. 22 23 Time and memory complexities are $O(N)$. 24 25 **Bonus** 26 27 Solve the problem if it is required that each cell is filled with water, or next to at least $1$ cell that is filled with water. 28 29 [1900B - Laura and Operations](/contest/1900/problem/B "Codeforces Round 911 (Div. 2)") 30 31 Author: [NemanjaSo2005](/profile/NemanjaSo2005 "Master NemanjaSo2005") 32 33 **Hint 1** 34 35 Check if only digits $1$ can remain. The situation is similar for checking if only digits $2$ or only digits $3$ can remain. 36 37 **Hint 2** 38 39 Try to find something that stays the same after each operation. 40 41 **Hint 3** 42 43 Look at the parity of the numbers. 44 45 **Hint 4** 46 47 The parity of each number changes after an operation. That means that if $2$ numbers have the same parity, they will always have the same parity. If they had different parity, their parities stay different. 48 49 **Solution** 50 51 Read the hints. 52 53 If the parity of $b$ and $c$ is not the same, then it is impossible for only digits $1$ to remain on the board, as it would require $b = c = 0$. Otherwise, the following construction will leave only digits $1$ on the board. 54 55 First remove digits $2$ and $3$ and write digit $1$ while $b \gt 0$ and $c \gt 0$. If $b=c$, then we are done. Otherwise, without loss of generality assume $b \gt c$. That means that after the operations $c=0$ and $b$ is even (Because $b$ and $c$ are the same parity). Now we perform the following $2$ operations $\frac{b}{2}$ times to get only digits $1$ left. Remove digits $1$ and $2$ and add digit $3$. After that remove digits $2$ and $3$ and add digit $1$. An effective change of these $2$ operations is the reduction of $b$ by $2$. 56 57 Time and memory complexities are $O(1)$. 58 59 **Bonus** 60 61 Come up with a problem that uses a similar idea and try to solve it. A lot of beginner problems use a similar idea. 62 63 [1900C - Anji's Binary Tree](/contest/1900/problem/C "Codeforces Round 911 (Div. 2)") 64 65 Author: [Riblji_Keksic](/profile/Riblji_Keksic "Master Riblji_Keksic") 66 67 **Hint 1** 68 69 Solve the problem if all of the characters on vertices are 'U'. 70 71 **Hint 2** 72 73 We can run DFS from the root. Using it we can calculate the number of edges that we have to traverse to get to every edge. Just output the smallest value among all the leaves. 74 75 **Hint 3** 76 77 Modify the DFS such that it takes into account that traversing some edges does not require an operation. 78 79 **Hint 4** 80 81 Add weights to the edges. 82 83 **Solution** 84 85 Read the hints. 86 87 We will make edges from a vertex to its children. The weight of that edge will be $1$ unless one of the following holds: 88 89 * The weight of an edge between a vertex and its left child will be $0$ if the letter written on that vertex is 'L'. 90 * The weight of an edge between a vertex and its right child will be $0$ if the letter written on that vertex is 'R'. 91 92 Now we run a modified DFS to find the distance of each vertex from the root, but with weighted edges. We output the minimal value among all the leaves. 93 94 Time and memory complexities are $O(N)$. 95 96 **Bonus** 97 98 Solve the problem if after reaching a leaf, Keksic can teleport to any other leaf that he chooses and then needs to get back to the root, or report that it is impossible for him to complete such a travel. 99 100 [1900D - Small GCD](/contest/1900/problem/D "Codeforces Round 911 (Div. 2)") 101 102 Author:[NemanjaSo2005](/profile/NemanjaSo2005 "Master NemanjaSo2005") 103 104 **Hint 1** 105 106 Let $m$ be the biggest value in the array. Calculate array $x$ such that $x_i$ ($1 \le i \le m$) is the number of triples which have $\gcd$ of $i$. Then the answer is the sum of $i \cdot x_i$ over all $i$ ($1 \le i \le m$). 107 108 **Hint 2** 109 110 Value of $\lfloor \frac{m}{1} \rfloor + \lfloor \frac{m}{2} \rfloor + \lfloor \frac{m}{3} \rfloor + \ldots + \lfloor \frac{m}{m} \rfloor$ is around $m log m$. 111 112 **Solution part 1** 113 114 We calculate $x_i$ from $x_m$ to $x_1$. For some $i$, we can first calculate the number of triples that have a value of function $f$ that is an integer multiple of $i$, and then from it subtract $x_{2i}, x_{3i}, x_{4i} \ldots$. Because of the previous hint, the subtractions will be quite fast. 115 116 Now the question is how to calculate the number of triples that have a value of function $f$ that is an integer multiple of $i$. 117 118 **Hint 3** 119 120 Numbers up to $100\,000$ can have at most $128$ divisors. 121 122 **The rest of the solution** 123 124 As the order in which numbers are given does not matter, we can sort the array. Now for each number $d$ ($1 \le d \le M$) store indices of all numbers that are divisible by $d$ in an array of vectors. Now we will for each number $d$ ($1 \le d \le m$) count the number of triples. 125 126 To find the number of triples that have a gcd value that is an integer multiple of $d$, we can do the following. We go over the index of the number that will be value $b$ in the function. We can utilize the vectors we calculated in the previous step for that. Say that the current index is $i$. Then for value $c$ we can pick any number with an index larger than $i$ as the array is sorted. For value $a$, we can pick any of the numbers divisible by $d$ with an index less than $i$, the number of which we can get from the vector. By multiplying those $2$ numbers we get the number of triples that have $a_i$ as their middle value. 127 128 As numbers can have up to $128$ divisors, the step above is quite fast. 129 130 Total time complexity is $O(m log m + n log n + 128 \cdot n)$. Total memory complexity is $O(m + 128 \cdot n)$. 131 132 **Bonus** 133 134 Solve the problem if $f(a,b,c) = \gcd (a,c)$. 135 136 [1900E - Transitive Graph](/contest/1900/problem/E "Codeforces Round 911 (Div. 2)") 137 138 Author:[NemanjaSo2005](/profile/NemanjaSo2005 "Master NemanjaSo2005") 139 140 **Hint 1** 141 142 Try to simplify graph $H$. 143 144 **Hint 2** 145 146 Look at strongly connected components of $G$, and what happens with them. 147 148 **Hint 3** 149 150 Use dp to find the answer. 151 152 **Solution** 153 154 The main observation is what $H$ looks like. All the strongly connected components (SCC) in $G$ will become fully connected subgraphs in $H$. Secondly, take any two vertices $a$ and $b$ such that $a$ and $b$ are not in the same SCC. We can let $S_a$ be a set of vertices that are in the same SCC as $a$ ($a$ included). Similarly, $S_b$ is a set of vertices that are in the same SCC as $b$. If there is an edge going from $a$ to $b$, then for any two vertices $x$ and $y$ such that $x$ belongs to $S_a$ and $y$ belongs to $S_b$, there is an edge going from $x$ to $y$. Both of the previously stated facts about the graph can be proven by induction. 155 156 Now, let's say that there is the longest path that goes through at least one vertex of an SCC. Then that path goes through all the vertices in the SCC, due to all vertices in SCC being connected to the same vertices outside the SCC and due to the fact that SCC is a complete subgraph. 157 158 Now we can construct the graph $H'$. Each of the SCCs from $H$ will be a vertex in $H'$. The number on the vertex will be equal to the sum of all numbers on the vertices of the SCC that it was constructed from. Edges between two new vertexes will be added if there is an edge between their original SCCs. The edge will have a weight equal to the size of the SCC that it is going into. An additional vertex will be added at index $0$ and an edge will be made between it and all other vertices with $0$ ingoing edges. Weight will be determined based on the size of the SCC of the vertex that the edge is going into. 159 160 Due to the previous observations, the answer for the $H'$ will be the same as the answer for the $H$. However, notice that $H'$ is a DAG. That means that the answer for it can be computed using DP after topological ordering. 161 162 Total time and memory complexity is $O(n)$. 163 164 **Bonus** 165 166 We will define the value of the path as the biggest value of a vertex on the path. Among the values of all the longest paths, find the median one. It is guaranteed that there are at most $10^{18}$ longest paths starting from each node. (So basically, you can ignore overflow in the number of paths) The rest of the constraints are the same. 167 168 [1900F - Local Deletions](/contest/1900/problem/F "Codeforces Round 911 (Div. 2)") 169 170 Author: [NemanjaSo2005](/profile/NemanjaSo2005 "Master NemanjaSo2005") 171 172 **Hint 1** 173 174 Solve the problem for $q=1$. 175 176 **Hint 2** 177 178 We can just simulate the process. Each operation removes at least half of the elements, meaning that we will perform at most $log n$ operations. 179 180 **Hint 3** 181 182 Solve the problem if each $l_i = 1$. So basically, solve the problem for each prefix. 183 184 **Hint 4** 185 186 Keep values that are in the array after $1$, $2$, $3$, $\cdots$, $log n$ operations. Let's call those array's layers. Layer $0$ is an array after $0$ operations, layer $1$ after $1$ operation, and so on. When we add a value to the end of the layer, only $1$ number that was previously local extreme (local minimum or maximum, depending on layer) might unbecome local extreme if the new value becomes local extreme. So we can just propagate this update to all layers. 187 188 **Hint 5** 189 190 Try to simulate the process of updating described in hint $4$. Also, notice that if the array is longer than $3$, we can handle prefix and suffix updates separately. 191 192 **Solution** 193 194 Read the hints. 195 196 Now we will precompute and store the array after each operation on the entire permutation. We will call those array layers. 197 198 We can now solve queries in $O(log n)$. 199 200 If a query involves a small number of elements, we can just brute force it. Otherwise, we do the following: 201 202 Now let's define our queries a bit differently. We are given some array $x$, which will be a subarray of some layer, and $2$ values, $a$ and $b$. We will get array $y$ by appending $a$ to the start of $x$ and appending $b$ to the end of $x$. We are interested in the value of $f$($y$). It is easy to see that all queries involving $3$ or more elements can be converted into the modified query. 203 204 If $|y|$ is small, we can just brute force it. Otherwise, we can transform it into a query on the next layer in constant time, or in $O(log n)$. 205 206 Now, the first thing to notice is that all elements in $x$ that are neither first nor last will be deleted only if they were deleted when we performed operations on the whole permutation. That means that they will represent some interval on the next layer, let's call it $z$. (That interval can be found either with binary search or in $O(1)$ with precomputation) It holds that $ |z| $ is around half of $|x|$. Now, notice that among $a$ and the first element of $x$, there has to be at least one deletion. The same goes for the last element of $x$ and $b$. 207 208 So now we have transformed the query onto the next level in $O(1)$, or $O(log n)$. As we will do at most $O(log n)$ such transformations, the complexity of a single query is either $O(log n)$ or $O(log^2 n)$ depending on the way we find the next interval, both of which should be fast enough to pass. 209 210 Total time complexity: $O(n + q log n)$ or $O(n + q log^2 n)$. Total memory complexity: $O(n+q)$ 211 212 **Bonus** 213 214 [2103D - Local Construction](/contest/2103/problem/D "Codeforces Round 1019 (Div. 2)")