279.md (11105B)
1 Source: https://codeforces.com/blog/entry/95148 2 3 [Continuing](https://codeforces.com/blog/entry/83942) with the theme of absent editorials for old rounds, here is an editorial for [Codeforces Round 171 (Div. 2)](/contest/279 "Codeforces Round 171 (Div. 2)"). Even though there is an official editorial, it is only in russian and doesn't have solution for the last problem. 4 5 A 6 7 **Editorial** 8 9 ### [279A - Point on Spiral](/contest/279/problem/A "Codeforces Round 171 (Div. 2)") 10 11 Since constraints are small, you can just simulate the whole process, but I'll explain an $O(1)$ solution. Let's look at the path 12 13  14 15 Now it's easy to see that the plane can be divided into four parts 16 17  18 19 And then we can calculate answer for each part separately, just be careful with borders. For example, for the right part the answer is $4x - 3$. 20 21 **Code** 22 23 ``` 24 #include "bits/stdc++.h" 25 26 using namespace std; 27 28 int main() { 29 int x, y; 30 cin >> x >> y; 31 if (x == 0 && y == 0) { 32 cout << 0 << '\n'; 33 } else if (-x + 1 < y && y <= x) { 34 cout << 1 + (x - 1) * 4 << '\n'; 35 } else if (-y <= x && x < y) { 36 cout << 2 + (y - 1) * 4 << '\n'; 37 } else if (x <= y && y < -x) { 38 cout << 3 + (-x - 1) * 4 << '\n'; 39 } else { 40 cout << 4 + (-y - 1) * 4 << '\n'; 41 } 42 43 return 0; 44 } 45 ``` 46 47 B 48 49 **Editorial** 50 51 ### [279B - Books](/contest/279/problem/B "Codeforces Round 171 (Div. 2)") 52 53 The problem can be written in the following way: for each index $i$ denote $r_i$ as the largest index such that $a_i + \ldots + a_{r_i} \leqslant t$. The problem is to find $max(r_i - i + 1)$. 54 55 One can see that $r_i$ are nondecreasing, so the problem can be solved with two pointers: iterate over $i$ and keep a pointer to corresponding $r_i$. 56 57 **Code** 58 59 ``` 60 #include "bits/stdc++.h" 61 62 using namespace std; 63 64 int main() { 65 int n, t; 66 cin >> n >> t; 67 vector<int> a(n); 68 for (int& k : a) 69 cin >> k; 70 71 int r = 0; 72 int sm = 0; 73 int ans = 0; 74 for (int i = 0; i < n; ++i) { 75 while (r < n && sm + a[r] <= t) { 76 sm += a[r]; 77 ++r; 78 } 79 ans = max(ans, r - i); 80 sm -= a[i]; 81 } 82 83 cout << ans << '\n'; 84 85 return 0; 86 } 87 ``` 88 89 C 90 91 **Editorial** 92 93 ### [279C - Ladder](/contest/279/problem/C "Codeforces Round 171 (Div. 2)") 94 95 Let's calculate two arrays before answering queries. $tol[i]$ is the smallest index such that $[b_{tol[i]},\, \ldots,\, b_{i}]$ is nonincreasing, and $tor[i]$ is the largest index such that $[b_{i},\, \ldots,\, b_{tor[i]}]$ is nondecreasing. Then for each query we can take $tor[l]$ and $tol[r]$ and compare them. The answer is "Yes" iff $tor[l] \geqslant tol[r]$. In other words, we are checking if the largest nondecreasing segment from $l$ and largest nonincreasing segment from $r$ are intersecting. 96 97 To calculate $tol[i]$, go over $i$ from $1$ to $n$ and maintain largest nonincreasing suffix. For $tor$ do the same in reverse. 98 99 **Code** 100 101 ``` 102 #include "bits/stdc++.h" 103 104 using namespace std; 105 106 int main() { 107 int n, m; 108 cin >> n >> m; 109 vector<int> a(n); 110 for (int& k : a) 111 cin >> k; 112 113 vector<int> tor(n), tol(n); 114 iota(tol.begin(), tol.end(), 0); 115 iota(tor.begin(), tor.end(), 0); 116 117 tol[0] = 0; 118 for (int i = 1; i < n; ++i) 119 if (a[i - 1] >= a[i]) 120 tol[i] = tol[i - 1]; 121 122 tor[n - 1] = n - 1; 123 for (int i = n - 2; i >= 0; --i) 124 if (a[i] <= a[i + 1]) 125 tor[i] = tor[i + 1]; 126 127 while (m--) { 128 int l, r; 129 cin >> l >> r; 130 --l; --r; 131 cout << (tol[r] <= tor[l] ? "Yes" : "No") << '\n'; 132 } 133 134 return 0; 135 } 136 ``` 137 138 D 139 140 **Editorial** 141 142 ### [279D - The Minimum Number of Variables](/contest/279/problem/D "Codeforces Round 171 (Div. 2)") 143 144 You can notice that when we want to perform some operation, we are only interested in a subset of current values of variables (including zeros). So let's create $dp[i][mask] = bool$, which is $1$ if we can perform first $i$ operations and end up with the values from $mask$. Here $k$-bit in the mask corresponds to the value $vals[k]$, where array $vals$ stores all numbers in $a$ and a zero, and $k$-th bit is set iff the value of one of the variables is $vals[k]$. 145 146 To make transition from $dp[i][mask]$ to $dp[i + 1][new\_mask]$, let's look at the operation. We have to find two values in the $mask$ such that their sum is $a[i + 1]$. Then to calculate $new\_mask$ we have to set $k$-th bit in the $mask$, where $k$ is such that $vals[k] = a[i + 1]$. Also, while writing new variable we can overwrite any existing variable, so we have an option to disable any bit in the $mask$. 147 148 Now it looks like we have $O(2^nn)$ states and $n$ transitions from each state (disabling each bit). But actually if we only make transition from $dp[i][mask] = 1$, the complexity will be $O(2^nn)$, because for each $i$ there are at most $2^{i+1}$ masks that we can achieve, since there are only $i$ distinct numbers on the current prefix plus an additional zero. And $\sum_{i=1}^n 2^{i+1}\cdot n = O(2^nn)$. 149 150 The only problem left is to check if we can build some number $y$ from $vals$ using numbers from $mask$. This can be precomputed in $O(2^nn)$: let's calculate array $possible[mask] = x$, where $i$-th bit in $x$ is set iff we can get number $vals[i]$ from mask on the next step. To calculate it, first for each $mask$ with at most $2$ bits just calculate all possible $x$ with any straightforward approach, since there are only $O(n^2)$ such masks. For any other mask notice that we can get $y$ iff sum of some two values equals to $y$. So we can iterate over all submasks such that they differ from $mask$ in exactly one bit and update $possible[mask]$ with $possible[submask]$. And since $mask$ has at least $3$ bits, if there is a pair which sums up to $y$, this pair will be included into at least one of the submasks. One can even notice that we only need any $3$ such submasks to cover every pair of bits. 151 152 The answer is minimum number of bits over all masks such that $dp[n][mask] = 1$. 153 154 **Code** 155 156 ``` 157 #include "bits/stdc++.h" 158 159 using namespace std; 160 161 int main() { 162 int n; 163 cin >> n; 164 vector<int> a(n); 165 for (int& k : a) 166 cin >> k; 167 168 auto vals = a; 169 vals.push_back(0); 170 sort(vals.begin(), vals.end()); 171 vals.erase(unique(vals.begin(), vals.end()), vals.end()); 172 173 vector<int> pos(n); 174 for (int i = 0; i < n; ++i) { 175 pos[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); 176 } 177 178 vector<int> possible(1 << vals.size(), 0); 179 for (int i = 1; i < possible.size(); ++i) { 180 int k = 0; 181 for (int j = 0; j < vals.size() && k < 3; ++j) { 182 if ((i >> j) & 1) { 183 possible[i] |= possible[i ^ (1 << j)]; 184 ++k; 185 } 186 } 187 if (__builtin_popcount(i) <= 2) { 188 for (int j = 0; j < vals.size(); ++j) { 189 if (!((i >> j) & 1)) continue; 190 for (int k = 0; k < vals.size(); ++k) { 191 if (!((i >> k) & 1)) continue; 192 int val = vals[j] + vals[k]; 193 int ind = lower_bound(vals.begin(), vals.end(), val) - vals.begin(); 194 if (ind < vals.size() && vals[ind] == val) 195 possible[i] |= (1 << ind); 196 } 197 } 198 } 199 } 200 201 vector<char> dp_cur(1 << vals.size(), 0); 202 dp_cur[1 << pos[0]] = 1; 203 dp_cur[(1 << pos[0]) | (1 << 0)] = 1; 204 205 auto can_sum = [&](int mask, int pos) { 206 return (possible[mask] >> pos) & 1; 207 }; 208 209 vector<char> dp_next; 210 for (int i = 1; i < n; ++i) { 211 dp_next.assign(dp_cur.size(), false); 212 for (int j = 0; j < dp_cur.size(); ++j) { 213 if (dp_cur[j] && can_sum(j, pos[i])) { 214 int mask = j; 215 mask |= (1 << pos[i]); 216 dp_next[mask] = 1; 217 for (int k = 0; k < vals.size(); ++k) 218 if (((mask >> k) & 1) && vals[k] != a[i]) 219 dp_next[mask ^ (1 << k)] = 1; 220 } 221 } 222 swap(dp_cur, dp_next); 223 } 224 225 int ans = -1; 226 for (int i = 0; i < dp_cur.size(); ++i) { 227 if (!dp_cur[i]) continue; 228 int sz = __builtin_popcount(i); 229 if (ans == -1 || ans > sz) 230 ans = sz; 231 } 232 cout << ans << '\n'; 233 234 return 0; 235 } 236 ``` 237 238 E 239 240 **Editorial** 241 242 ### [279E - Beautiful Decomposition](/contest/279/problem/E "Codeforces Round 171 (Div. 2)") 243 244 First of all it's easy to notice that we will use each power of $2$ at most once. 245 246 Let's look at the highest bit in the current number, suppose it's $2^k$. Since the sum of all powers of $2$ below $k$ is less than $2^k$, we will have to add at least one power of two $2^x$ with $x \geqslant k$. One can see that adding $2^{k+2}$ is not optimal, since then we will have to subtract at least $2^{k+1}$ and $2^{k+2} - 2^{k+1}$ can be replaced with $2^{k+1}$. So the only choices are $2^k$ or $2^{k+1}$. If we add $2^k$, we have to solve a problem for remaining number, which is a suffix or our current binary string. Otherwise, $2^{k+1}$ is larger than our current number, so we just need the answer for $m = 2^{k+1} - n$. Let's call such $m$ a complement for a number $n$ (notice that we don't need $k$ in the definition because $k$ is defined as largest bit in $n$) 247 248 Now let's look at $m$. To calculate it, we have to flip all bits in $n$ and add $1$ to the result. Now it's easy to see that if $m$ is a complement for $n$, then for any suffix of $n$ (in binary form), the corresponding suffix of $m$ is a complement for it. Also, $n$ is a complement for $m$. 249 250 So during our calculations we will only deal with $n$, $m$, suffixes of $n$ and suffixes of $m$. And this leads to a following dp solution: let $v[1] = n$, $v[2] = m$. Then $dp[ind][suf]$ is the smallest answer for a binary number represented by a suffix of number $v[ind]$ starting from index $suf$. We can calculate this $dp$ starting from $dp[\ldots][n]$ and the answer will be $dp[1][1]$. 251 252 **Code** 253 254 ``` 255 #include "bits/stdc++.h" 256 257 using namespace std; 258 259 int main() { 260 string n; 261 cin >> n; 262 string m = n; 263 { 264 for (char& c : m) { 265 c ^= '1' ^ '0'; 266 } 267 int ind = m.size() - 1; 268 while (ind >= 0 && m[ind] == '1') { 269 m[ind] = '0'; 270 --ind; 271 } 272 if (ind == -1) { 273 m.insert(m.begin(), '1'); 274 n.insert(n.begin(), '0'); 275 } else { 276 m[ind] = '1'; 277 } 278 } 279 280 int sz = n.size(); 281 282 vector<string> v = {n, m}; 283 vector<array<int, 2>> dp(sz); 284 285 dp[sz - 1][0] = (v[0].back() == '1'); 286 dp[sz - 1][1] = (v[1].back() == '1'); 287 288 for (int i = sz - 2; i >= 0; --i) { 289 for (int b = 0; b < 2; ++b) { 290 if (v[b][i] == '0') { 291 dp[i][b] = dp[i + 1][b]; 292 } else { 293 dp[i][b] = min(dp[i + 1][b] + 1, dp[i + 1][b ^ 1] + 1); 294 } 295 } 296 } 297 298 cout << dp[0][0] << '\n'; 299 300 return 0; 301 } 302 ```