662.md (22788B)
1 Source: https://codeforces.com/blog/entry/44408 2 3 ## [664A - Complicated GCD](/contest/664/problem/A "Codeforces Round 347 (Div. 2)") 4 5 Author of the idea — [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP") 6 7 We examine two cases: 8 9 1. *a* = *b* — the segment consists of a single number, hence the answer is *a*. 10 2. *a* < *b* — we have *gcd*(*a*, *a* + 1, *a* + 2, ..., *b*) = *gcd*(*gcd*(*a*, *a* + 1), *a* + 2, ..., *b*) = *gcd*(1, *a* + 2, ..., *b*) = 1. 11 12 **Code** 13 14 ``` 15 #include <bits/stdc++.h> 16 17 using namespace std; 18 19 int main() { 20 string a, b; 21 cin >> a >> b; 22 23 if (a == b) cout << a; 24 else cout << 1; 25 26 return 0; 27 } 28 ``` 29 30 ## [663A - Rebus](/contest/663/problem/A "Codeforces Round 347 (Div. 1)") 31 32 Author of the idea — [gen](/profile/gen "Master gen") 33 34 First we check whether any solution exists at all. For that purpose, we calculate the number of positive (the first one and any other with the + sign) and negative elements (with the - sign) in the sum. Let them be *pos* and *neg*, respectively. Then the minimum value of the sum that can be possibly obtained is equal to *min* = (1 · *pos* - *n* · *neg*), as each positive number can be 1, but all negative can be - *n*. Similarly, the maximum possible value is equal to *max* = (*n* · *pos* - 1 · *neg*). The solution therefore exists if and only if *min* ≤ *n* ≤ *max*. 35 36 Now suppose a solution exists. Let's insert the numbers into the sum one by one from left to right. Suppose that we have determined the numbers for some prefix of the expression with the sum of *S*. Let the sign of the current unknown be *sgn* ( + 1 or - 1) and there are some unknown numbers left to the right, excluding the examined unknown, among them *pos*_*left* positive and *neg*_*left* negative elements. Suppose that the current unknown number takes value *x*. How do we find out whether this leads to a solution? The answer is: in the same way we checked it in the beginning of the solution. Examine the smallest and the largest values of the total sum that we can get. These are equal to *min*_*left* = (*S* + *sgn* · *x* + *pos*_*left* - *n* · *neg*_*left*) and *max*_*left* = (*S* + *sgn* · *x* + *n* · *pos*_*left* - *neg*_*left*), respectively. Then we may set the current number to *x*, if *min*_*left* ≤ *n* ≤ *max*_*left* holds. To find the value of *x*, we can solve a system of inequalities, but it is easier simply to check all possible values from 1 to *n*. 37 38 **BONUS** Let *k* be the number of unknowns in the rebus. Prove that the complexity of the described solution (implementation shown below) is *O*(*k*2 + *n*), not *O*(*k* · *n*). 39 40 **Code** 41 42 ``` 43 #include<bits/stdc++.h> 44 45 using namespace std; 46 47 char s[100]; 48 49 int main() { 50 int k = 0, n, pos = 1, neg = 0; 51 while (true) { 52 char c; 53 scanf(" %c", &c); 54 scanf(" %c", &c); 55 56 if (c == '=') break; 57 if (c == '+') pos++; 58 if (c == '-') neg++; 59 60 s[k++] = c; 61 } 62 63 scanf("%d", &n); 64 65 if (pos - n * neg > n || n * pos - neg < n) { 66 printf("Impossible\\n"); 67 68 return 0; 69 } 70 71 printf("Possible\\n"); 72 73 int S = 0; 74 for (int i = 0; i < k; i++) { 75 int sgn = 1; 76 if (i > 0 && s[i - 1] == '-') sgn = -1; 77 78 if (sgn == 1) pos--; 79 if (sgn == -1) neg--; 80 81 for (int x = 1; x <= n; x++) 82 if (S + x * sgn + pos - n * neg <= n && S + x * sgn + n * pos - neg >= n) { 83 printf("%d %c ", x, s[i]); 84 85 S += x * sgn; 86 87 break; 88 } 89 } 90 91 printf("%d = %d\\n", abs(n - m), n); 92 93 return 0; 94 } 95 ``` 96 97 ## [662D - International Olympiad](/contest/662/problem/D "CROC 2016 - Final Round [Private, For Onsite Finalists Only]") 98 99 Author of the idea — [Alex_2oo8](/profile/Alex_2oo8 "International Grandmaster Alex_2oo8") 100 101 Consider the abbreviations that are given to the first Olympiads. The first 10 Olympiads (from year 1989 to year 1998) receive one-digit abbreviations (*IAO*'9, *IAO*'0, ..., *IAO*'8). The next 100 Olympiads (1999 - 2098) obtain two-digit abbreviations, because all one-digit abbreviations are already taken, but the last two digits of 100 consecutive integers are pairwise different. Similarly, the next 1000 Olympiads get three-digit abbreviations and so on. 102 103 Now examine the inversed problem (extract the year from an abbreviation). Let the abbreviation have *k* digits, then we know that all Olympiads with abbreviations of lengths (*k* - 1), (*k* - 2), ..., 1 have passed before this one. The number of such Olympiads is 10*k* - 1 + 10*k* - 2 + ... + 101 = *F* and the current Olympiad was one of the 10*k* of the following. Therefore this Olympiad was held in years between (1989 + *F*) and (1989 + *F* + 10*k* - 1). As this segment consists of exactly 10*k* consecutive natural numbers, it contains a single number with a *k*-digit suffix that matches the current abbreviation. It is also the corresponding year. 104 105 **Code** 106 107 ``` 108 #include <bits/stdc++.h> 109 110 using namespace std; 111 112 char s[42]; 113 114 int main() { 115 int n; 116 scanf("%d", &n); 117 while (n--) { 118 scanf(" %s", s); 119 120 int k = strlen(s + 4), year = atoi(s + 4), F = 0, tenPow = 10; 121 for (int i = 1; i < k; i++) { 122 F += tenPow; 123 tenPow *= 10; 124 } 125 126 while (year < 1989 + F) year += tenPow; 127 128 printf("%d\\n", year); 129 } 130 131 return 0; 132 } 133 ``` 134 135 ## [662B - Graph Coloring](/contest/662/problem/B "CROC 2016 - Final Round [Private, For Onsite Finalists Only]") 136 137 Author of the problem — [gen](/profile/gen "Master gen") 138 139 Examine the two choices for the final color separately, and pick the best option afterwards. Now suppose we want to color the edges red. 140 141 Each vertex should be recolored at most once, since choosing a vertex two times changes nothing (even if the moves are not consecutive). Thus we need to split the vertices into two sets *S* and *T*, the vertices that are recolored and the vertices that are not affected, respectively. Let *u* and *v* be two vertices connected by a red edge. Then for the color to remain red, both *u* and *v* should belong to the same set (either *S* or *T*). On the other hand, if *u* and *v* are connected by a blue edge, then exactly one of the vertices should be recolored. In that case *u* and *v* should belong to different sets (one to *S* and the other to *T*). 142 143 This problem reduces to 0-1 graph coloring, which can be solved by either *DFS* or *BFS*. As the graph may be disconnected, we need to process the components separately. If any component does not have a 0-1 coloring, there is no solution. Otherwise we need to add the smallest of the two partite sets of the 0-1 coloring of this component to *S*, as we require *S* to be of minimum size. 144 145 **Code** 146 147 ``` 148 #include<bits/stdc++.h> 149 150 using namespace std; 151 152 const int MX = 100000; 153 154 int n, vis[MX]; 155 vector<pair<int, char>> G[MX]; 156 vector<int> part[3]; 157 158 bool dfs(int v, int p, char c) { 159 if (vis[v] != 0) { 160 return vis[v] == p; 161 } 162 163 vis[v] = p; 164 part[p].push_back(v); 165 166 for (auto x : G[v]) { 167 if (dfs(x.first, x.second == c ? p : p ^ 3, c) == false) 168 return false; 169 } 170 171 return true; 172 } 173 174 vector<int> solve(char c) { 175 memset(vis, 0, sizeof vis); 176 177 vector<int> ans; 178 for (int i = 0; i < n; i++) 179 if (vis[i] == 0) { 180 part[1].clear(); 181 part[2].clear(); 182 183 if (dfs(i, 1, c) == false) { 184 for (int j = 0; j < n + 1; j++) ans.push_back(-1); 185 186 return ans; 187 } 188 189 int f = 1; 190 if (part[2].size() < part[1].size()) f = 2; 191 192 ans.insert(ans.end(), part[f].begin(), part[f].end()); 193 } 194 195 return ans; 196 } 197 198 int main() { 199 int m; 200 scanf("%d %d", &n, &m); 201 for (int i = 0; i < m; i++) { 202 int u, v; 203 char c; 204 scanf("%d %d %c", &u, &v, &c); 205 u--; 206 v--; 207 208 G[u].emplace_back(v, c); 209 G[v].emplace_back(u, c); 210 } 211 212 auto f = solve('R'); 213 auto g = solve('B'); 214 215 if (g.size() < f.size()) f = g; 216 217 if (f.size() > n) { 218 printf("-1\\n"); 219 220 return 0; 221 } 222 223 printf("%d\\n", (int)f.size()); 224 for (int x : f) printf("%d ", x + 1); 225 printf("\\n"); 226 227 return 0; 228 } 229 ``` 230 231 ## [662A - Gambling Nim](/contest/662/problem/A "CROC 2016 - Final Round [Private, For Onsite Finalists Only]") 232 233 Author of the idea — [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP") 234 235 It is known that the first player loses if and only if the *xor*-sum of all numbers is 0. Therefore the problem essentially asks to calculate the number of ways to arrange the cards in such a fashion that the *xor*-sum of the numbers on the upper sides of the cards is equal to zero. 236 237 Let  and . Suppose that the cards with indices *j*1, *j*2, ..., *j**k* are faced with numbers of type *b* and all the others with numbers of type *a*. Then the *xor*-sum of this arrangement is equal to , that is, . Hence we want to find the number of subsets *c**i* with *xor*-sum of *S*. 238 239 Note that we can replace *c*1 with , as applying *c*1 is the same as applying . Thus we can freely replace {*c*1, *c*2} with  and *c*2 with . This means that we can apply the following procedure to simplify the set of *c**i*: 240 241 1. Pick *c**f* with the most significant bit set to one 242 2. Replace each *c**i* with the bit in that position set to one to  243 3. Remove *c**f* from the set 244 4. Repeat steps 1-5 with the remaining set 245 5. Add *c**f* back to the set 246 247 After this procedure we get a set that contains *k* zeros and *n* - *k* numbers with the property that the positions of the most significant bit set to one strictly decrease. How do we check now whether it is possible to obtain a subset with *xor*-sum *S*? As we have at most one number with a one in the most significant bit, then it tells us whether we should include that number in the subset or not. Similarly we apply the same argument for all other bits. If we don't obtain a subset with the *xor*-sum equal to *S*, then there is no such subset at all. If we do get a subset with *xor*-sum *S*, then the total number of such subsets is equal to 2*k*, as for each of the *n* - *k* non-zero numbers we already know whether it must be include in such a subset or not, but any subset of *k* zeros doesn't change the *xor*-sum. In this case the probability of the second player winning the game is equal to , so the first player wins with probability . 248 249 **Code** 250 251 ``` 252 #include <bits/stdc++.h> 253 254 using namespace std; 255 256 const int size = 1000 * 1000 + 1; 257 const int ssize = 100; 258 259 int n; 260 long long a[size], b[size]; 261 long long ort[ssize]; 262 long long p[ssize]; 263 264 int main() { 265 long long cur = 0ll; 266 scanf("%d", &n); 267 for (int i = 0; i < n; i++) { 268 scanf("%lld%lld", &a[i], &b[i]); 269 cur ^= a[i]; 270 a[i] ^= b[i]; 271 } 272 a[n] = cur; 273 274 int len = 0; 275 for (int i = 0; i <= n; i++) { 276 for (int j = 0; j < len; j++) { 277 if (a[i] & p[j]) 278 a[i] ^= ort[j]; 279 } 280 if (a[i]) { 281 ort[len++] = a[i]; 282 p[len - 1] = ((a[i] ^ (a[i] - 1)) + 1) >> 1; 283 } 284 } 285 if (a[n]) { 286 printf("1/1\\n"); 287 } else { 288 printf("%lld/%lld\\n", (1ll << len) - 1, (1ll << len)); 289 } 290 291 return 0; 292 } 293 ``` 294 295 ## [662C - Binary Table](/contest/662/problem/C "CROC 2016 - Final Round [Private, For Onsite Finalists Only]") 296 297 Author of the idea — [Alex_2oo8](/profile/Alex_2oo8 "International Grandmaster Alex_2oo8") 298 299 First let's examine a slow solution that works in *O*(2*n* · *m*). Since each row can be either inverted or not, the set of options of how we can invert the rows may be encoded in a bitmask of length *n*, an integer from 0 to (2*n* - 1), where the *i*-th bit is equal to 1 if and only if we invert the *i*-th row. Each column also represents a bitmask of length *n* (the bits correspond to the values of that row in each of the *n* rows). Let the bitmask of the *i*-th column be *col**i*, and the bitmask of the inverted rows be *mask*. After inverting the rows the *i*-th column will become . Suppose that  contains  ones. Then we can obtain either *k* or (*n* - *k*) ones in this column, depending on whether we invert the *i*-th column itself. It follows that for a fixed bitmask *mask* the minimum possible number of ones that can be obtained is equal to . 300 301 Now we want to calculate this sum faster than *O*(*m*). Note that we are not interested in the value of the mask  itself, but only in the number of ones it contains (from 0 to *n*). Therefore we may group the columns by the value of . Let *dp*[*k*][*mask*] be the number of such *i* that , then for a fixed bitmask *mask* we can calculate the sum in *O*(*n*) — . 302 303 What remains is to calculate the value of *dp*[*k*][*mask*] in a quick way. As the name suggests, we can use dynamic programming for this purpose. The value of *dp*[0][*mask*] can be found in *O*(*m*) for all bitmasks *mask*: each column *col**i* increases *dp*[0][*col**i*] by 1. For *k* > 0, *col**i* and *mask* differ in exactly *k* bits. Suppose *mask* and *col**i* differ in position *p*. Then *col**i* and  differ in exactly (*k* - 1) bits. The number of such columns is equal to , except we counted in also the number of columns *col**i* that differ with  in bit *p* (thus, *mask* and *col**i* have the same value in bit *p*). Thus we need to subtract *dp*[*k* - 2][*mask*], but again, except the columns among these that differ with *mask* in bit *p*. Let ; by expanding this inclusion-exclusion type argument, we get that the number of masks we are interested in can be expressed as *dp*[*k* - 1][*next*] - *dp*[*k* - 2][*mask*] + *dp*[*k* - 3][*next*] - *dp*[*k* - 4][*mask*] + *dp*[*k* - 5][*next*] - .... By summing all these expressions for each bit *p* from 0 to *n*, we get *dp*[*k*][*mask*] · *k*, since each column is counted in *k* times (for each of the bits *p* where the column differs from *mask*). 304 305 Therefore, we are now able to count the values of *dp*[*k*][*mask*] in time *O*(2*n* · *n*3) using the following recurrence: 306 307  308 309 This is still a tad slow, but we can speed it up to *O*(2*n* · *n*2), for example, in a following fashion: 310 311   312 313  314 315 **BONUS** Are you able to come up with an even faster solution? 316 317 **Code** 318 319 ``` 320 #include<bits/stdc++.h> 321 322 using namespace std; 323 324 char s[100000]; 325 int col[100000], dp[21][1 << 20]; 326 327 int main() { 328 int n, m; 329 scanf("%d %d", &n, &m); 330 for (int i = 0; i < n; i++) { 331 scanf(" %s", s); 332 333 for (int j = 0; j < m; j++) col[j] |= (s[j] - '0') << i; 334 } 335 336 for (int i = 0; i < m; i++) dp[0][col[i]]++; 337 338 for (int k = 1; k <= n; k++) 339 for (int mask = 0; mask < (1 << n); mask++) { 340 int sum = k > 1 ? (k - 2 - n) * dp[k - 2][mask] : 0; 341 for (int p = 0; p < n; p++) sum += dp[k - 1][mask ^ (1 << p)]; 342 343 dp[k][mask] = sum / k; 344 } 345 346 int ans = n * m; 347 for (int mask = 0; mask < (1 << n); mask++) { 348 int cnt = 0; 349 for (int k = 0; k <= n; k++) cnt += min(k, n - k) * dp[k][mask]; 350 351 ans = min(ans, cnt); 352 } 353 354 printf("%d\\n", ans); 355 356 return 0; 357 } 358 ``` 359 360 ## [662E - To Hack or not to Hack](/contest/662/problem/E "CROC 2016 - Final Round [Private, For Onsite Finalists Only]") 361 362 Author of the idea — [Alex_2oo8](/profile/Alex_2oo8 "International Grandmaster Alex_2oo8") 363 364 Observation number one — as you are the only participant who is able to hack, the total score of any other participant cannot exceed 9000 (3 problems for 3000 points). Hence hacking at least 90 solutions automatically guarantees the first place (the hacks alone increase the score by 9000 points). 365 366 Now we are left with the problem where the number of hacks we make is at most 90. We can try each of the 63 possible score assignments for the problems in the end of the round. As we know the final score for each problem, we can calculate the maximum number of hacks we are allowed to make so the problem gets the assigned score. This is also the exact amount of hacks we will make in that problem. As we know the number of hacks we will make, we can calculate our final total score. Now there are at most 90 participants who we can possibly hack. We are interested only in those who are on top of us. By hacking we want to make their final score less than that of us. This problem can by solved by means of dynamic programming: 367 368 *dp*[*p*][*i*][*j*][*k*] — the maximum number of participants among the top *p*, whom we can push below us by hacking first problem *i* times, second problem *j* times and third problem *k* times. 369 370 The recurrence: we pick a subset of solutions of the current participant that we will hack, and if after these hacks we will push him below us, we update the corresponding dp state. For example, if it is enough to hack the first and the third problems, then *dp*[*p* + 1][*i* + 1][*j*][*k* + 1] = *max*(*dp*[*p* + 1][*i* + 1][*j*][*k* + 1], *dp*[*p*][*i*][*j*][*k*] + 1) 371 372 **BONUS** Can you solve this problem if each hack gives only 10 points, not 100? 373 374 **Code** 375 376 ``` 377 #include<bits/stdc++.h> 378 379 #define time ololo 380 381 using namespace std; 382 383 int time[5000][3], n, solved[3], canHack[3], score[3], willHack[3], bestPlace, dp[2][90][90][90], ci, li; 384 385 int submissionScore(int sc, int tm) { 386 if (tm == 0) return 0; 387 388 return sc * (250 - abs(tm)) / 250; 389 } 390 391 int calcScore(int p) { 392 int sum = 0; 393 for (int i = 0; i < 3; i++) sum += submissionScore(score[i], time[p][i]); 394 395 return sum; 396 } 397 398 int countHacks(int p) { 399 int cnt = 0; 400 for (int i = 0; i < 3; i++) cnt += time[p][i] < 0; 401 402 return cnt; 403 } 404 405 int solve() { 406 memset(dp, 0, sizeof dp); 407 408 int myScore = 0; 409 for (int i = 0; i < 3; i++) myScore += 100 * willHack[i] + submissionScore(score[i], time[0][i]); 410 411 ci = 0; 412 li = 1; 413 for (int p = 1; p < n; p++) 414 if (countHacks(p) > 0 && calcScore(p) > myScore) { 415 ci ^= 1; 416 li ^= 1; 417 418 for (int i = 0; i <= willHack[0]; i++) 419 for (int j = 0; j <= willHack[1]; j++) 420 for (int k = 0; k <= willHack[2]; k++) 421 dp[ci][i][j][k] = dp[li][i][j][k]; 422 423 for (int ii = 0; ii < 2; ii++) 424 for (int jj = 0; jj < 2; jj++) 425 for (int kk = 0; kk < 2; kk++) { 426 if (ii == 1 && time[p][0] >= 0) continue; 427 if (jj == 1 && time[p][1] >= 0) continue; 428 if (kk == 1 && time[p][2] >= 0) continue; 429 430 int s = submissionScore(score[0], time[p][0]) * (ii ^ 1) 431 + submissionScore(score[1], time[p][1]) * (jj ^ 1) 432 + submissionScore(score[2], time[p][2]) * (kk ^ 1); 433 434 if (s > myScore) continue; 435 436 for (int i = ii; i <= willHack[0]; i++) 437 for (int j = jj; j <= willHack[1]; j++) 438 for (int k = kk; k <= willHack[2]; k++) 439 dp[ci][i][j][k] = max(dp[ci][i][j][k], dp[li][i - ii][j - jj][k - kk] + 1); 440 } 441 } 442 443 int res = 1 - dp[ci][willHack[0]][willHack[1]][willHack[2]]; 444 for (int p = 1; p < n; p++) if (calcScore(p) > myScore) res++; 445 446 return res; 447 } 448 449 void brute(int p) { 450 if (p == 3) { 451 int res = solve(); 452 453 bestPlace = min(bestPlace, res); 454 455 return; 456 } 457 458 for (int i = 0; i < 6; i++) { 459 int mn = i == 5 ? 0 : (n >> (i + 1)) + 1; 460 int mx = (n >> i); 461 462 if (solved[p] >= mn && solved[p] - canHack[p] <= mx) { 463 score[p] = 500 * (i + 1); 464 willHack[p] = min(canHack[p], solved[p] - mn); 465 466 brute(p + 1); 467 } 468 } 469 } 470 471 int main() { 472 memset(solved, 0, sizeof solved); 473 memset(canHack, 0, sizeof canHack); 474 475 scanf("%d", &n); 476 for (int i = 0; i < n; i++) 477 for (int j = 0; j < 3; j++) { 478 scanf("%d", &time[i][j]); 479 480 solved[j] += time[i][j] != 0; 481 canHack[j] += time[i][j] < 0; 482 } 483 484 if (canHack[0] + canHack[1] + canHack[2] > 89) { 485 printf("1\\n"); 486 487 return 0; 488 } 489 490 bestPlace = n; 491 brute(0); 492 493 printf("%d\\n", bestPlace); 494 495 return 0; 496 } 497 ```