1977.md (15583B)
1 Source: https://codeforces.com/blog/entry/129858 2 3 We hope you enjoyed the problems. 4 5 Problem [1977A - Little Nikita](/contest/1977/problem/A "Codeforces Round 948 (Div. 2)") was created by [Stefan2417](/profile/Stefan2417 "Master Stefan2417") and prepared by [alexchist](/profile/alexchist "Master alexchist"). 6 7 Problem [1977B - Binary Colouring](/contest/1977/problem/B "Codeforces Round 948 (Div. 2)") was created by [alexchist](/profile/alexchist "Master alexchist") and prepared by [Stefan2417](/profile/Stefan2417 "Master Stefan2417"). 8 9 Problem [1977C - Nikita and LCM](/contest/1977/problem/C "Codeforces Round 948 (Div. 2)") was created and prepared by [Stefan2417](/profile/Stefan2417 "Master Stefan2417"). 10 11 Problem [1977D - XORificator](/contest/1977/problem/D "Codeforces Round 948 (Div. 2)") was created and prepared by [alexchist](/profile/alexchist "Master alexchist"). 12 13 Problem [1977E - Tensor](/contest/1977/problem/E "Codeforces Round 948 (Div. 2)") was created and prepared by [Stefan2417](/profile/Stefan2417 "Master Stefan2417"). 14 15 [1977A - Little Nikita](/contest/1977/problem/A "Codeforces Round 948 (Div. 2)") 16 17 **Tutorial** 18 19 Note that one action with the cube changes the parity of the number of cubes in the tower. Therefore, if the parities of $n$ and $m$ do not match, it is impossible to build the tower. Also, if $n \lt m$, the tower cannot be built either. In all other cases, it is possible to build a tower of height $m$ in $m$ operations, and then add and remove a cube until the operations are exhausted. 20 21 **Author's code** 22 23 ``` 24 #include <bits/stdc++.h> 25 using namespace std; 26 27 int main () { 28 ios_base::sync_with_stdio(0); cin.tie(0); 29 int T; 30 cin >> T; 31 while (T--) { 32 int n, m; 33 cin >> n >> m; 34 cout << (n >= m && (n%2) == (m%2) ? "Yes" : "No") << '\n'; 35 } 36 } 37 ``` 38 39 **Feedback** 40 41 * Good problem 42 * Average problem 43 * Bad problem 44 45 [1977B - Binary Colouring](/contest/1977/problem/B "Codeforces Round 948 (Div. 2)") 46 47 **Tutorial** 48 49 We will iterate over the prefix of $i$ bits and construct a correct answer for the number formed by the prefix bits of the number $x$. We are interested in considering only the one bits, as they are the only ones that affect the value of the number $x$. 50 51 If we have already placed a one at position $i$ in the answer, we need to somehow add $2^i$ to the number. To do this, we simply zero out the $i$-th bit in the answer and set it at $i + 1$ — this will add $2 \cdot 2^i = 2^{i+1}$. 52 53 Now, the $i$-th position in the answer holds $0$. 54 55 Let's consider what we placed at position $i-1$ in the answer. If it's $0$, then everything is fine; we just place $1$ at position $i$. If it's $1$, we have a situation of [1 1], which we correct by making it [-1 0 1] — placing $-1$ at $i-1$, leaving $0$ at $i$, and placing $1$ at $i+1$. This will add $2^i$ to the sum because $2^i + 2^{i-1} = 2^{i+1} - 2^{i-1}$. The remaining case is when $i-1$ holds $-1$, but this is impossible because our forward operations only place ones, and $-1$ is placed behind. 56 57 The final time complexity is $O(\log(x))$ per test case. 58 59 **Author's code** 60 61 ``` 62 #include "bits/stdc++.h" 63 64 #define all(a) a.begin(), a.end() 65 #define pb push_back 66 typedef long long ll; 67 using namespace std; 68 mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count()); 69 70 /// Actual code starts here 71 const int N = 100005; 72 73 void solve() { 74 ll x; 75 cin >> x; 76 vector<int> res(31, 0); 77 for (int i = 0; i < 30; i++) { 78 if (1ll & (x >> i)) { 79 if (res[i]) { 80 res[i + 1] = 1; 81 res[i] = 0; 82 } else if (i > 0) { 83 if (res[i - 1] == 1) { 84 res[i + 1] = 1; 85 res[i - 1] = -1; 86 } else { 87 res[i] = 1; 88 } 89 } else if (i == 0) { 90 res[i] = 1; 91 } 92 } 93 } 94 cout << 31 << '\n'; 95 for (int i = 0; i <= 30; i++) { 96 cout << res[i] << ' '; 97 } 98 cout << '\n'; 99 } 100 101 signed main() { 102 ios::sync_with_stdio(false); 103 cin.tie(nullptr); 104 cout.tie(nullptr); 105 int tt = 1; 106 cin >> tt; 107 while (tt--) 108 solve(); 109 } 110 ``` 111 112 **Feedback** 113 114 * Good problem 115 * Average problem 116 * Bad problem 117 118 [1977C - Nikita and LCM](/contest/1977/problem/C "Codeforces Round 948 (Div. 2)") 119 120 **Hint** 121 122 Try to check if the entire array $a$ can be the answer. 123 124 **Tutorial** 125 126 First, let's understand if we can take the entire array $a$ as the special subsequence. 127 128 To do this, find the LCM($a_1, a_2, \dots, a_n$). If it is greater than max($a_1, a_2, \dots, a_n$), then obviously such a number is not in the subsequence, because $LCM \geq max$. 129 130 After this check, it becomes known that each $a_i \ | \ max(a_1, a_2, \dots, a_n)$. 131 132 Then we iterate over the divisors of the maximum and greedily check for the presence of a subsequence with such an LCM. 133 134 If we do this naively, it will be $O(\sqrt{C} + n \cdot d(C) \cdot \log(C))$, but this is already sufficient. 135 136 Note that we can count the occurrence of each number and check only the distinct numbers. Then the complexity will be $O(\sqrt{C} + d(C)^2 \cdot \log(C))$. 137 138 **Author's code** 139 140 ``` 141 #include "bits/stdc++.h" 142 143 #define err(x) cerr << "["#x"] " << (x) << "\n" 144 #define errv(x) {cerr << "["#x"] ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";} 145 #define errvn(x, n) {cerr << "["#x"] ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";} 146 #define all(a) a.begin(), a.end() 147 #define pb push_back 148 typedef long long ll; 149 typedef long double ld; 150 using namespace std; 151 const int MOD = 1000000007; 152 mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count()); 153 154 template<typename T1, typename T2> 155 inline bool relaxmi(T1 &a, const T2 &b) { 156 return a > b ? a = b, true : false; 157 } 158 159 template<typename T1, typename T2> 160 inline bool relaxma(T1 &a, const T2 &b) { 161 return a < b ? a = b, true : false; 162 } 163 164 double GetTime() { return clock() / (double) CLOCKS_PER_SEC; } 165 166 /// Actual code starts here 167 const int N = 100005; 168 169 int calc(vector<pair<int, int>> &t, int d) { 170 int LCM = 0, cnt = 0; 171 for (auto [j, c]: t) { 172 if (d % j == 0) { 173 if (LCM == 0) LCM = j; 174 else LCM = lcm(LCM, j); 175 cnt += c; 176 } 177 } 178 if (LCM != d) cnt = 0; 179 return cnt; 180 } 181 182 void solve() { 183 int n; 184 cin >> n; 185 vector<int> v(n); 186 for (auto &i: v) cin >> i; 187 ll LCM = 1; 188 int mx = *max_element(all(v)); 189 for (auto i: v) { 190 LCM = lcm(LCM, i); 191 if (LCM > mx) { 192 cout << n << '\n'; 193 return; 194 } 195 } 196 map<int, int> cnt; 197 for (auto i: v) cnt[i]++; 198 vector<pair<int, int>> t; 199 for (auto i: cnt) 200 t.push_back(i); 201 int res = 0; 202 for (int i = 1; i * i <= mx; i++) { 203 if (mx % i == 0) { 204 if (!cnt.contains(i)) 205 relaxma(res, calc(t, i)); 206 if (!cnt.contains(mx / i)) 207 relaxma(res, calc(t, mx / i)); 208 } 209 } 210 cout << res << '\n'; 211 } 212 213 signed main() { 214 ios::sync_with_stdio(false); 215 cin.tie(nullptr); 216 cout.tie(nullptr); 217 int tt = 1; 218 cin >> tt; 219 while (tt--) 220 solve(); 221 } 222 ``` 223 224 **Feedback** 225 226 * Good problem 227 * Average problem 228 * Bad problem 229 230 [1977D - XORificator](/contest/1977/problem/D "Codeforces Round 948 (Div. 2)") 231 232 **Hint** 233 234 Try to fix the specialty of column $i$ and the presence of a one in cell $i, j$. 235 236 **Tutorial** 237 238 Let's assume that the value in the $i$-th row and $j$-th column is strictly one and it is the only one in the column. 239 240 Then the entire table is uniquely determined, as well as the XORificator. For each possible state of the XORificator that constructs the required table, 241 242 Let's maintain a counter. Then the state that maximizes the number of columns with exactly one 1 has the maximum counter. 243 244 To efficiently maintain the counter, it is necessary to maintain the hash of the XORificator and quickly recalculate it when moving to the next row. 245 246 The answer can be easily reconstructed by traversing the table again and counting the hash. If the desired hash is obtained, simply output the state of the XORificator. 247 248 The final time complexity is $O(nm \log{(nm)})$ or $O(nm)$ if a hash map is used. 249 250 For hashing, it is convenient to use [Zobrist hashing](https://en.wikipedia.org/wiki/Zobrist_hashing). 251 252 **Author's code** 253 254 ``` 255 #include "bits/stdc++.h" 256 257 using namespace std; 258 259 mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); 260 261 void solve() { 262 int n, m; 263 cin >> n >> m; 264 vector<vector<bool>> table(n, vector<bool>(m)); 265 for (int i = 0; i < n; ++i) { 266 for (int j = 0; j < m; ++j) { 267 char c; 268 cin >> c; 269 table[i][j] = c - '0'; 270 } 271 } 272 vector<long long> rands(n), rands2(n); 273 for (int i = 0; i < n; ++i) { 274 rands[i] = rnd(); 275 rands2[i] = rnd(); 276 } 277 map<pair<long long, long long>, int> ans; 278 int res = 0; 279 pair<int, int> ind_ans = {0, 0}; 280 for (int j = 0; j < m; ++j) { 281 long long summ = 0, summ2 = 0; 282 for (int i = 0; i < n; ++i) { 283 if (table[i][j]) { 284 summ ^= rands[i]; 285 summ2 ^= rands2[i]; 286 } 287 } 288 for (int i = 0; i < n; ++i) { 289 summ ^= rands[i]; 290 summ2 ^= rands2[i]; 291 ans[{summ, summ2}]++; 292 if (res < ans[{summ, summ2}]) { 293 res = ans[{summ, summ2}]; 294 ind_ans = {j, i}; 295 } 296 summ ^= rands[i]; 297 summ2 ^= rands2[i]; 298 } 299 } 300 cout << res << "\n"; 301 string inds(n, '0'); 302 for (int i = 0; i < n; ++i) { 303 if (table[i][ind_ans.first]) { 304 if (i != ind_ans.second) { 305 inds[i] = '1'; 306 } 307 } else if (ind_ans.second == i) { 308 inds[i] = '1'; 309 } 310 } 311 cout << inds << "\n"; 312 } 313 314 signed main() { 315 ios::sync_with_stdio(false); 316 cin.tie(nullptr); 317 int tt = 1; 318 cin >> tt; 319 while (tt--) { 320 solve(); 321 } 322 } 323 ``` 324 325 **Feedback** 326 327 * Good problem 328 * Average problem 329 * Bad problem 330 331 [1977E - Tensor](/contest/1977/problem/E "Codeforces Round 948 (Div. 2)") 332 333 **Tutorial** 334 335 First, let's understand why 2 colors are indeed sufficient. 336 337 Notice that the reachability relation in a graph defines a [Partially Ordered Set](https://en.wikipedia.org/wiki/Partially_ordered_set). 338 339 According to [Dilworth's Theorem](https://en.wikipedia.org/wiki/Dilworth%27s_theorem), the size of the maximum antichain is equal to the minimum number of chains that cover the Partially Ordered Set. 340 341 Note that the condition on the reachability of pairs of vertices within any triplet implies a constraint on the maximum size of the antichain. It is simply no more than 2. Therefore, 2 colors are indeed sufficient. 342 343 The remaining task is to understand how to explicitly construct these 2 chains. 344 345 We will build this inductively. Let's maintain 3 stacks — the last vertices painted in black, white, and red respectively. These will correspond to the chains we are building. 346 347 Suppose we have built chains on $n$ vertices and want to build them on $n + 1$: 348 349 * If the white or black stacks are empty, simply add vertex $n+1$ to the empty stack. 350 * If the red stack is empty: 351 * + Ask about the reachability of the last vertices in the white and black stacks from vertex $n+1$. 352 * + If both vertices are reachable, put vertex $n+1$ in the red stack. 353 * + If only one vertex is reachable, put vertex $n+1$ in the stack whose last vertex is reachable from $n+1$. 354 * + The case where neither vertex is reachable is impossible as it contradicts the condition. 355 * If the red stack is not empty: 356 * + Ask about the reachability of the last vertex in the red stack from vertex $n+1$. 357 * + If it is reachable, put it in the red stack. 358 * + If it is not reachable, ask about the end of the white stack. 359 * + If the vertex at the end of the white stack is not reachable, then the vertex at the end of the black stack must be reachable, otherwise, it contradicts the problem's condition. 360 * + Color vertex $n+1$ black if the black vertex is reachable or white if the white vertex is reachable. 361 * + Recolor all vertices in the red stack to the opposite color relative to vertex $n+1$. We can do this because, by construction, all vertices in the white and black stacks are reachable from all vertices in the red stack. 362 * + Do not forget to clear the red stack. 363 364 Each time a new vertex is added, no more than 2 queries are used. Therefore, we will use no more than $2 \cdot n$ queries in total. 365 366 During the algorithm, all operations are performed in $O(1)$ time, resulting in an overall complexity of $O(n)$. 367 368 As an exercise for the reader, try to prove the lower bound on the number of queries. 369 370 **Author's code** 371 372 ``` 373 #include "bits/stdc++.h" 374 375 #define err(x) cerr << "["#x"] " << (x) << "\n" 376 #define errv(x) {cerr << "["#x"] ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";} 377 #define errvn(x, n) {cerr << "["#x"] ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";} 378 #define all(a) a.begin(), a.end() 379 #define pb push_back 380 typedef long long ll; 381 typedef long double ld; 382 using namespace std; 383 const int MOD = 1000000007; 384 mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count()); 385 386 template<typename T1, typename T2> 387 inline bool relaxmi(T1 &a, const T2 &b) { 388 return a > b ? a = b, true : false; 389 } 390 391 template<typename T1, typename T2> 392 inline bool relaxma(T1 &a, const T2 &b) { 393 return a < b ? a = b, true : false; 394 } 395 396 double GetTime() { return clock() / (double) CLOCKS_PER_SEC; } 397 398 /// Actual code starts here 399 const int N = 100005; 400 401 bool ask(int i, int j) { 402 cout << "? " << j << ' ' << i << endl; 403 string resp; 404 cin >> resp; 405 if (resp == "-1") assert(false); 406 if (resp == "YES") return true; 407 else return false; 408 } 409 410 void solve() { 411 int n; 412 cin >> n; 413 vector<int> st, st2, st3; 414 st = {1}; 415 for (int i = 2; i <= n; i++) { 416 if (st2.empty()) { 417 if (ask(i, st.back())) { 418 st.push_back(i); 419 } else { 420 st2.push_back(i); 421 } 422 } else if (st3.empty()) { 423 int ok1 = ask(i, st.back()), ok2 = ask(i, st2.back()); 424 if (ok1 && ok2) { 425 st3.push_back(i); 426 } else if (ok1) { 427 st.push_back(i); 428 } else if (ok2) { 429 st2.push_back(i); 430 } else { 431 assert(false); 432 } 433 } else { 434 if (ask(i, st3.back())) { 435 st3.push_back(i); 436 } else { 437 if (ask(i, st.back())) { 438 st.push_back(i); 439 for (auto j: st3) 440 st2.push_back(j); 441 st3.clear(); 442 } else { 443 st2.push_back(i); 444 for (auto j: st3) 445 st.push_back(j); 446 st3.clear(); 447 } 448 } 449 } 450 } 451 if (!st3.empty()) { 452 for (auto i: st3) 453 st.push_back(i); 454 st3.clear(); 455 } 456 vector<int> colors(n + 1); 457 for (auto i: st2) 458 colors[i] = 1; 459 cout << "! "; 460 for (int i = 1; i <= n; i++) cout << colors[i] << ' '; 461 cout << endl; 462 } 463 464 signed main() { 465 ios::sync_with_stdio(false); 466 cin.tie(nullptr); 467 cout.tie(nullptr); 468 int tt = 1; 469 cin >> tt; 470 while (tt--) 471 solve(); 472 } 473 ``` 474 475 **Feedback** 476 477 * Good problem 478 * Average problem 479 * Bad problem