2257.md (9136B)
1 Source: https://codeforces.com/blog/entry/156058 2 3 Thank you for participating in our round! We hope you enjoyed the problems. 4 5 [2257A - Creating Abbreviations](/contest/2257/problem/A "Codeforces Round 1117 (Div. 2)") Idea: [egorka5opka](/profile/egorka5opka "Master egorka5opka") 6 7 **Solution** 8 9 Note that adding abbreviations to the set $S$ does not create any new possibilities for creating new abbreviations, because a word starting with that letter already exists. Therefore, for each of the 26 letters, we can remember that there is a word that begins with it, and then go through all the abbreviations and check each letter. 10 11 **Code** 12 13 [387467084](/contest/2257/submission/387467084 "Submission 387467084 by pskobx") 14 15 **Rate the problem** 16 17 Amazing 18 19 Good 20 21 Ok 22 23 Bad 24 25 Terrible 26 27 [2257B - Gigantomachy](/contest/2257/problem/B "Codeforces Round 1117 (Div. 2)") Idea: [egorka5opka](/profile/egorka5opka "Master egorka5opka") 28 29 **Solution** 30 31 On each turn, the height at which the giant stands decreases by exactly $1$, except in cases where he changes mountains. 32 33 Thus, the first giant will lose after $((a_1 - a_2) + 1) + ((a_2 - a_3) + 1) + \dots + ((a_{n - 1} - a_n) + 1) + a_n = a_1 + n - 1$ moves. 34 35 Similarly, the second giant will lose after $b_1 + m - 1$ moves. All left is only to compare these two numbers. 36 37 Time complexity: $\mathcal{O}(n)$. 38 39 **Code** 40 41 [387467136](/contest/2257/submission/387467136 "Submission 387467136 by pskobx") 42 43 **Rate the problem** 44 45 Amazing 46 47 Good 48 49 Ok 50 51 Bad 52 53 Terrible 54 55 [2257C - Spying on the Beaver](/contest/2257/problem/C "Codeforces Round 1117 (Div. 2)") Idea: [egorka5opka](/profile/egorka5opka "Master egorka5opka") 56 57 **Solution** 58 59 Suppose we have placed some cameras and remove the corresponding edges from the tree. If all the dams are now in different connected components, we can always uniquely determine where the Beaver went. Conversely, if there is a component containing two dams, we cannot distinguish between them. 60 61 Since the original graph is a tree, it is necessary and sufficient to remove $m-1$ edges. 62 63 If the root contains a dam, we can take the edges leading directly to all the other dams, obtaining a set of size $m-1$. 64 65 If the root does not contain a dam, we take the same edges but skip one of them. It is important that we cannot skip just any edge: we must choose a dam such that there are no other dams on the path from the root to it. We can take the dam with the smallest depth or vertex number. In this case, we do not even need to run a DFS. 66 67 Time complexity: $\mathcal{O}(n+m)$. 68 69 **Code** 70 71 [387467226](/contest/2257/submission/387467226 "Submission 387467226 by pskobx") 72 73 **Rate the problem** 74 75 Amazing 76 77 Good 78 79 Ok 80 81 Bad 82 83 Terrible 84 85 [2257D - Bermuda Rectangle](/contest/2257/problem/D "Codeforces Round 1117 (Div. 2)") Idea: [pskobx](/profile/pskobx "Master pskobx"), [oblememan](/profile/oblememan "Master oblememan"), [egorka5opka](/profile/egorka5opka "Master egorka5opka") 86 87 **Solution** 88 89 Before processing the queries, let us perform some preprocessing. Find all pairs $(a, b)$ such that $a \cdot b = S$. There are $\mathcal{O}(\sqrt{S})$ such pairs, and they can also be found in $\mathcal{O}(\sqrt{S})$ time with standard algorithms. 90 91 These pairs are the top-right corners of all possible Bermuda rectangles. The union of these rectangles forms a staircase-like shape; let us call it $F$. The answer to a query is the area of the intersection of the query rectangle with $F$. 92 93 Sort the points by $x$, and for the point with index $i$, compute the value $P_i$, equal to the area of $F$ between $0$ and this $x_i$. 94 95 This information is enough to answer each query efficiently using binary search. We find the position where the boundary of $F$ crosses the horizontal side of the query rectangle and calculate the answer using the corresponding prefix areas. The exact formulas and case analysis may vary depending on the implementation. 96 97 A couple of remarks that may make implementation easier. If there is a point $(x, y)$, then there is also $(y, x)$, and since, knowing one coordinate, it is easy to compute the other. Therefore, it is enough to store just the sorted list of divisors of $S$ and treat them both as $x$ and as $y$. 98 99 Preprocessing complexity: $\mathcal{O}(\sqrt{S})$, time complexity per query: $\mathcal{O}(\log S)$. 100 101 **Code** 102 103 [387467301](/contest/2257/submission/387467301 "Submission 387467301 by pskobx") 104 105 **Rate the problem** 106 107 Amazing 108 109 Good 110 111 Ok 112 113 Bad 114 115 Terrible 116 117 [2257E - Busy Beaver](/contest/2257/problem/E "Codeforces Round 1117 (Div. 2)") Idea: [pskobx](/profile/pskobx "Master pskobx") 118 119 **Solution** 120 121 The first step is to earn as many carrots as possible to maximize our capital. Divide the floors of each building into the shortest consecutive segments whose total profit is non-negative, and calculate the entry threshold of each such segment. The entry threshold is the minimum amount of capital required to construct all floors of the segment in order. 122 123 For example, consider two floors with $(a_1, a_2) = (10, 0)$ and $(b_1, b_2) = (0, 100)$. Constructing only the first floor is unprofitable, but constructing both floors yields a profit of $90$ carrots. However, an initial capital of at least $10$ carrots is required. 124 125 In an ordered set, we keep the next available segment for each building, sorted by its entry threshold. While the segment with the minimum threshold is affordable, we construct the entire segment, add its profit to our capital, and insert the next segment of the same building into the set. If the segment with the minimum threshold is not affordable, then none of the available segments can be constructed, meaning that we have maximized our capital. 126 127 In the second step, we independently try to continue constructing each building from its current height, floor by floor, for as long as the current capital allows. Among all buildings, we choose the maximum resulting height and, in case of a tie, the smallest index. 128 129 Time complexity: $\mathcal{O}\left(\sum m_i \log n\right)$. 130 131 **Code** 132 133 [387467400](/contest/2257/submission/387467400 "Submission 387467400 by pskobx") 134 135 **Rate the problem** 136 137 Amazing 138 139 Good 140 141 Ok 142 143 Bad 144 145 Terrible 146 147 [2257F1 - Beaver's Jumping Track (Easy Version)](/contest/2257/problem/F1 "Codeforces Round 1117 (Div. 2)") Idea: [pskobx](/profile/pskobx "Master pskobx"), [oblememan](/profile/oblememan "Master oblememan"), [egorka5opka](/profile/egorka5opka "Master egorka5opka") 148 149 **Solution** 150 151 Since $x$ is small, we build a segment tree whose vertices store matrices of size $x \times x$. 152 153 For an interval of platforms, let $c[i][j]$ be the minimum penalty if the Beaver starts $i$ cells after the beginning of the interval and first lands $j$ cells after its end. Invalid starting positions are ignored. 154 155 For a single platform of length $d$ and penalty $s$, 156 157 $ c[i][j]= \left( \left\lceil\frac{d+j-i}{x}\right\rceil-1 \right)s, $ 158 159 where $0\le i \lt \min(d,x)$ and $0\le j \lt x$. The last jump leaves the platform and causes no penalty, while all previous jumps stay inside it. 160 161 To merge two consecutive intervals $A$ and $B$, enumerate the first landing position $k$ in $B$: 162 163 $ c_{A+B}[i][j] = \min_k\left(c_A[i][k]+c_B[k][j]\right). $ 164 165 If $A$ contains fewer than $x$ cells, the Beaver may start directly inside $B$; in this case, we copy the corresponding values from $c_B$. 166 167 For a query $[l,r]$, obtain the matrix for $[l,r-1]$ and enumerate the first landing position $i$ on platform $r$. The answer is 168 169 $ \min_{0\le i \lt \min(x,d_r)} \left( c[0][i] + \left\lceil\frac{d_r-i-1}{x}\right\rceil s_r \right). $ 170 171 The case $l=r$ is calculated directly. 172 173 Each update and query takes $\mathcal{O}(x^3\log n)$ time. Memory complexity is $\mathcal{O}(nx^2)$. Build is $\mathcal{O}(nx^3)$. 174 175 **Code** 176 177 [387467533](/contest/2257/submission/387467533 "Submission 387467533 by pskobx") 178 179 **Rate the problem** 180 181 Amazing 182 183 Good 184 185 Ok 186 187 Bad 188 189 Terrible 190 191 [2257F2 - Beaver's Jumping Track (Hard Version)](/contest/2257/problem/F2 "Codeforces Round 1117 (Div. 2)") 192 193 **Solution** 194 195 Surprisingly, the main problem with the solution from F1 is memory, not time. A segment tree stores $\mathcal{O}(n)$ matrices, each containing $x^2$ values. For $x=10$, this does not fit into the memory limit. 196 197 To reduce memory usage, divide the platforms into blocks of size $B$ (for example, $B=16$). For each block, calculate the matrix of the entire block using the same merging formula as in F1. Then build a segment tree only over these block matrices. 198 199 For a query, at most two blocks are only partially covered by the required range. Process the platforms in these blocks separately, and use the segment tree to combine all blocks that are fully covered. After an update, recalculate the matrix of the affected block and update it in the segment tree. 200 201 For a block size $B$, the memory complexity is $\mathcal{O}\left(n+\frac{n}{B}x^2\right)$. 202 203 Each query takes $\mathcal{O}\left(Bx^2+x^3\log\frac{n}{B}\right)$. 204 205 Аnd each update takes $\mathcal{O}\left(Bx^3+x^3\log\frac{n}{B}\right)$. 206 207 **Code** 208 209 [387467610](/contest/2257/submission/387467610 "Submission 387467610 by pskobx") 210 211 **Rate the problem** 212 213 Amazing 214 215 Good 216 217 Ok 218 219 Bad 220 221 Terrible