687.md (21253B)
1 Source: https://codeforces.com/blog/entry/45770 2 3 Hi again! 4 5 If you notice typos or errors, please send a private message. 6 7 ### [688A: Opponents](//codeforces.com/contest/688/problem/A) 8 9 #### Solution 10 11 Let's find out for each row of the given matrix if it is completely consisting of *ones* or not. Make another array *canWin*, and set *canWin**i* equal to one if the *i*-th row consists at least one *zero*. Then the problem is to find the maximum subsegment of *canWin* array, consisting only ones. It can be solved by finding for each element of *canWin*, the closest zero to it from left. The complexity of this solution is *O*(*nd*), but the limits allow you to solve the problem in *O*(*nd*2) by iterating over all possible subsegments and check if each one of them is full of *ones* or not. 12 13 **C++ code** 14 15 ``` 16 // . .. ... .... ..... be name khoda ..... .... ... .. . \\ 17 18 #include <bits/stdc++.h> 19 using namespace std; 20 21 inline int in() { int x; scanf("%d", &x); return x; } 22 const int N = 202; 23 24 int a[N][N]; 25 26 int main() 27 { 28 int n = in(), d = in(); 29 int ans = 0, cur = 0; 30 for(int i = 0; i < d; i++) 31 { 32 string s; 33 cin >> s; 34 bool iff = 0; 35 for(int j = 0; j < n; j++) 36 iff |= (s[j] == '0'); 37 if(iff) 38 cur++; 39 else 40 cur = 0; 41 ans = max(ans, cur); 42 } 43 cout << ans << endl; 44 } 45 ``` 46 47 **Python code** 48 49 ``` 50 n, d = map(int, raw_input().split()) 51 cur = 0 52 ans = 0 53 for i in range(d): 54 s = raw_input() 55 if (s == '1' * n): 56 cur = 0 57 else: 58 cur += 1 59 ans = max(ans, cur) 60 print ans 61 ``` 62 63 ### [688B: Lovely Palindromes](//codeforces.com/contest/688/problem/B) 64 65 #### Hint 66 67 Try to characterize even-length palindrome numbers. 68 69 #### Solution 70 71 For simplifications, in the following solution we define *lovely integer* as an even-length positive palindrome number. 72 73 An even-length positive integer is lovely if and only if the first half of its digits is equal to the reverse of the second half. 74 75 So if *a* and *b* are two different 2*k*-digit lovely numbers, then the first *k* digits of *a* and *b* differ in at least one position. 76 77 So *a* is smaller than *b* if and only if the first half of *a* is smaller than the the first half of *b*. 78 79 Another useful fact: The first half of a a lovely number can be any arbitrary positive integer. 80 81 Using the above facts, it's easy to find the first half of the *n*-th lovely number — it exactly equals to integer *n*. When we know the first half of a lovely number, we can concatenate it with its reverse to restore the lovely integer. To sum up, the answer can be made by concatenating *n* and it's reverse together. 82 83 The complexity of this solution is . 84 85 **C++ code** 86 87 ``` 88 // . .. ... .... ..... be name khoda ..... .... ... .. . \\ 89 90 #include <bits/stdc++.h> 91 using namespace std; 92 93 inline int in() { int x; scanf("%d", &x); return x; } 94 const long long N = 2002; 95 96 int main() 97 { 98 string s; 99 cin >> s; 100 cout << s; 101 reverse(s.begin(), s.end()); 102 cout << s << endl; 103 } 104 ``` 105 106 **Python code** 107 108 ``` 109 s = raw_input() 110 print s + ''.join(reversed(s)) 111 ``` 112 113 #### Challenge 114 115 What if you were asked to find *n*-th positive palindrome number? (1 ≤ *n* ≤ 1018) 116 117 ### [687A: NP-Hard Problem](//codeforces.com/contest/687/problem/A) 118 119 #### Hint 120 121 Try to use all of the vertices. Then look at the two vertex covers together in the graph and see how it looks like. 122 123 #### Solution 124 125 Looking at the two vertex covers in the graph, you see there must be no edge *uv* that *u* and *v* are in the same vertex cover. So the two vertex covers form a bipartition of the graph, so the graph have to be bipartite. And being bipartite is also sufficient, you can use each part as a vertex cover. Bipartition can be found using your favorite graph traversing algorithm(BFS or DFS). [Here](http://stackoverflow.com/questions/30486784/how-to-find-if-a-graph-is-bipartite) is a tutorial for bipartition of undirected graphs. 126 127 The complexity is *O*(*n* + *m*). 128 129 **C++ code** 130 131 ``` 132 // . .. ... .... ..... be name khoda ..... .... ... .. . \\ 133 134 #include <bits/stdc++.h> 135 using namespace std; 136 137 inline int in() { int x; scanf("%d", &x); return x; } 138 const int N = 120021; 139 140 vector <int> vc[2]; 141 vector <int> g[N]; 142 int mark[N]; 143 144 bool dfs(int v, int color = 2) 145 { 146 mark[v] = color; 147 vc[color - 1].push_back(v); 148 for(int u : g[v]) 149 { 150 if(!mark[u] && dfs(u, 3 - color)) 151 return 1; 152 if(mark[u] != 3 - color) 153 return 1; 154 } 155 return 0; 156 } 157 158 int main() 159 { 160 int n, m; 161 cin >> n >> m; 162 for(int i = 0; i < m; i++) 163 { 164 int u = in() - 1; 165 int v = in() - 1; 166 g[u].push_back(v); 167 g[v].push_back(u); 168 } 169 for(int i = 0; i < n; i++) 170 if(!mark[i]) 171 { 172 if(g[i].empty()) 173 continue; 174 if(dfs(i)) 175 { 176 cout << -1 << endl; 177 return 0; 178 } 179 } 180 for(int i = 0; i < 2; i++) 181 { 182 cout << vc[i].size() << endl; 183 for(int v : vc[i]) 184 cout << v + 1 << " "; 185 cout << endl; 186 } 187 } 188 ``` 189 190 #### Challenge 191 192 In the same constraints, what if you were asked to give two disjoint edge covers from the given graph? (The edge covers must be edges-disjoint but they can have common vertex.) 193 194 ### [687B: Remainders Game](//codeforces.com/contest/687/problem/B) 195 196 #### Hint 197 198 Assume the answer of a test is *No*. There must exist a pair of integers *x*1 and *x*2 such that both of them have the same remainders after dividing by any *c**i*, but they differ in remainders after dividing by *k*. Find more facts about *x*1 and *x*2! 199 200 #### Solution 201 202 Consider the *x*1 and *x*2 from the hint part. We have *x*1 - *x*2 ≡ 0 () for each 1 ≤ *i* ≤ *n*. 203 204 So: 205 206  207 208 We also have  (). As a result: 209 210  211 212 We've found a necessary condition. And I have to tell you it's also sufficient! 213 214 Assume , we are going to prove there exists *x*1, *x*2 such that *x*1 - *x*2 ≡ 0 () (for each 1 ≤ *i* ≤ *n*), and  (). 215 216 A possible solution is *x*1 = *lcm*(*c*1, *c*2, ..., *c**n*) and *x*2 = 2 × *lcm*(*c*1, *c*2, ..., *c**n*), so the sufficiency is also proved. 217 218 So you have to check if *lcm*(*c*1, *c*2, ..., *c**n*) is divisible by *k*, which could be done using prime factorization of *k* and *c**i* values. 219 220 For each integer *x* smaller than *MAXC*, find it's greatest prime divisor *gpd**x* using [sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) in . 221 222 Then using *gpd* array, you can write the value of each coin as *p*1*q*1*p*2*q*2...*p**m**q**m* where *p**i* is a prime integer and 1 ≤ *q**i* holds. This could be done in  by moving from *c**i* to  and adding *gpd**c**i* to the answer. And you can factorize *k* by the same way. Now for every prime *p* that , see if there exists any coin *i* that the power of *p* in the factorization of *c**i* is not smaller than the power of *p* in the factorization of *k*. 223 224 Complexity is . 225 226 **C++ code** 227 228 ``` 229 // . .. ... .... ..... be name khoda ..... .... ... .. . \\ 230 231 #include <bits/stdc++.h> 232 using namespace std; 233 234 inline int in() { int x; scanf("%d", &x); return x; } 235 const long long N = 1200021; 236 237 int cntP[N], isP[N]; 238 239 int main() 240 { 241 for(int i = 2; i < N; i++) 242 if(!isP[i]) 243 for(int j = i; j < N; j += i) 244 isP[j] = i; 245 int n = in(), k = in(); 246 for(int i = 0; i < n; i++) 247 { 248 int x = in(); 249 while(x > 1) 250 { 251 int p = isP[x]; 252 int cnt = 0; 253 while(x % p == 0) 254 { 255 cnt++; 256 x /= p; 257 } 258 cntP[p] = max(cntP[p], cnt); 259 } 260 } 261 bool ok = 1; 262 while(k > 1) 263 { 264 ok &= (cntP[isP[k]] > 0); 265 cntP[isP[k]]--; 266 k /= isP[k]; 267 } 268 cout << (ok ? "Yes\n" : "No\n"); 269 } 270 ``` 271 272 And a nice implementation by [Reyna](/profile/Reyna "International Grandmaster Reyna"): [18789803](/contest/687/submission/18789803 "Submission 18789803 by Reyna") 273 274 ### [687C: The values you can make](//codeforces.com/contest/687/problem/C) 275 276 #### Hint 277 278 Use dynamic programming. 279 280 #### Solution 281 282 Let *dp**i*, *j*, *k* be true if and only if there exists a subset of the first *i* coins with sum *j*, that has a subset with sum *k*. There are 3 cases to handle: 283 284 * The *i*-th coin is not used in the subsets. 285 * The *i*-th coin is used in the subset to make *j*, but it's not used in the subset of this subset. 286 * The *i*-th coin is used in both subsets. 287 288 So *dp**i*, *j*, *k* is equal to *dp**i* - 1, *j*, *k* *OR* *dp**i* - 1, *j* - *c**i*, *k* *OR* *dp**i* - 1, *j* - *c**i*, *k* - *c**i*. 289 290 The complexity is *O*(*nk*2). 291 292 **C++ code** 293 294 ``` 295 // - -- --- ---- -----be name khoda----- ---- --- -- - \\ 296 297 #include <bits/stdc++.h> 298 using namespace std; 299 300 inline int in() { int x; scanf("%d", &x); return x; } 301 const int N = 505; 302 303 bool dp[2][N][N]; 304 305 int main() 306 { 307 int n, k; 308 cin >> n >> k; 309 dp[0][0][0] = 1; 310 for(int i = 1; i <= n; i++) 311 { 312 int now = i % 2; 313 int last = 1 - now; 314 int x = in(); 315 for(int j = 0; j <= k; j++) 316 for(int y = 0; y <= j; y++) 317 { 318 dp[now][j][y] = dp[last][j][y]; 319 if(j >= x) 320 { 321 dp[now][j][y] |= dp[last][j - x][y]; 322 if(y >= x) 323 dp[now][j][y] |= dp[last][j - x][y - x]; 324 } 325 } 326 } 327 vector <int> res; 328 for(int i = 0; i <= k; i++) 329 if(dp[n % 2][k][i]) 330 res.push_back(i); 331 cout << res.size() << endl; 332 for(int x : res) 333 cout << x << " "; 334 cout << endl; 335 } 336 ``` 337 338 #### Challenge 339 340 In the same constraints, output the numbers you can never not make! Formally, the values *x* such that for every subset of coins with the sum *k*, there exists a subset of this subset with the sum *x*. 341 342 ### [687D: Dividing Kingdom II](//codeforces.com/contest/687/problem/D) 343 344 Unfortunately, our mistake in setting the constrains for this problem made it possible to get Ac with *O*(*qm*) solution. We hope you accept our apology. 345 346 #### Hint 347 348 Consider the following algorithm to answer a single query: Sort the edges and add them one by one to the graph in decreasing order of their weights. The answer is weight of the first edge, which makes an odd cycle in the graph. Now show that there are only *O*(*n*) effective edges, which removing them may change the answer of the query. Use this idea to optimize your solution. 349 350 #### Solution 351 352 First, let’s solve a single query separately. Sort edges from interval [l, r] in decreasing order of weights. Using *dsu*, we can find longest prefix of these edges, which doesn’t contains odd cycle. (Graph will be bipartite after adding these edges.) The answer will be weight of the next edge. (We call this edge “bottleneck”). 353 354 Why it's correct? Because if the answer is *w*, then the we can divide the graph in a way that none of the edges in the same part have value greater than *w*. So the graph induced by the edges with value greater than *w* must be bipartite. And if this graph is bipartite, then we can divide the graph into two parts as the bipartition, so no edge with value greater than *w* will be in the same part, and the answer is at most *w*. 355 356 Let's have a look at this algorithm in more details. For each vertex, we keep two values in dsu: Its parent and if its part differs from its parent or not. We keep the second value equal to "parity of length of the path in original graph, between this node and its parent". We can divide the graph anytime into two parts, walking from one vertex to its parent and after reaching the root, see if the starting vertex must be in the same part as the root or not. 357 358 In every connected component, there must not exist any edge with endpoints in the same part. 359 360 After sorting the edges, there are 3 possible situations for an edge when we are adding it to the graph: 361 362 1. The endpoints of this edge are between two different components of the current graph. Now we must merge these two components, and update the part of the root of one of the components. 363 2. The endpoints of this edge are in the same component of the current graph, and they are in different parts of this component. There is nothing to do. 364 3. The endpoints of this edge are in the same component of the current graph, and they are also in the same part of this component. This edge is the "bottleneck" and we can't keep our graph bipartite after adding it, so we terminate the algorithm. 365 366 We call the edges of the first and the third type "valuable edges". 367 368 The key observation is: If we run above algorithm on the valuable edges, the answer remains the same. 369 370 Proof idea: The edges of the first type are spanning trees of connected components of the graph, and with a spanning tree of a bipartite graph, we can uniquely determine if two vertices are in the same part or not. 371 372 So if we can ignore all other edges and run our algorithm on these valuable edges, we have *O*(*n*) edges instead of original *O*(*n*2) and the answer is the same. 373 374 We answer the queries using a segment tree on the edges. In each node of this tree, we run the above algorithm and memorize the valuable edges. By implementing carefully (described [here](//codeforces.com/blog/entry/45770?#comment-303336)), making the segment tree could be done in . 375 376 Now for each query [*l*, *r*], you can decompose [*l*, *r*] into  segments in segment tree and each one has *O*(*n*) valuable edges. Running the naive algorithm on these edges lead to an  solution for each query, which fits in time limit. 377 378 **C++ code** 379 380 ``` 381 // . .. ... .... ..... be name khoda ..... .... ... .. . \\ 382 383 #include <bits/stdc++.h> 384 using namespace std; 385 386 inline int in() { int x; scanf("%d", &x); return x; } 387 const int N = 2002, M = (1 << 20), Q = 1001, S = 2 * M; 388 389 #define rank PAP 390 391 struct Edge 392 { 393 int u, v, w; 394 Edge(int u = 0, int v = 0, int w = 0):v(v), u(u), w(w) { } 395 bool operator <(const Edge &e) const { return w < e.w; } 396 }; 397 398 struct Segment 399 { 400 int l, r; 401 Segment(int l = 0, int r = 0): l(l), r(r) { } 402 }; 403 404 typedef vector <Edge> Edges; 405 406 int n, m, q; 407 Edge es[M]; 408 Edges seg[S]; 409 Segment range[S]; 410 int par[N], cost[N], rank[N]; 411 412 Segment merge(Segment l, Segment r) { return Segment(l.l, r.r); } 413 414 void clear(Edges &es) 415 { 416 for(Edge e : es) 417 { 418 par[e.v] = par[e.u] = -1; 419 cost[e.v] = cost[e.u] = 0; 420 rank[e.v] = rank[e.u] = 1; 421 } 422 } 423 424 int root(int v) 425 { 426 if(par[v] == -1) 427 return v; 428 int u = root(par[v]); 429 cost[v] ^= cost[par[v]]; 430 return par[v] = u; 431 } 432 433 int parity(int v) 434 { 435 root(v); 436 return cost[v]; 437 } 438 439 int merge(Edge e) 440 { 441 if(rank[root(e.u)] > rank[root(e.v)]) 442 swap(e.u, e.v); 443 if(root(e.u) == root(e.v)) 444 { 445 if(parity(e.u) == parity(e.v)) 446 return 2; 447 return 0; 448 } 449 int u = root(e.u); 450 int v = root(e.v); 451 cost[u] ^= (parity(e.u) ^ 1 ^ parity(e.v)); 452 par[u] = root(v); 453 rank[v] += rank[u]; 454 return 1; 455 } 456 457 bool hasOddCycle; 458 459 Edges merge(Edges &a, Edges &b) 460 { 461 Edges c; 462 merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c)); 463 clear(c); 464 Edges res; 465 for(int i = c.size() - 1; i >= 0; i--) 466 { 467 int x = merge(c[i]); 468 if(x) 469 res.push_back(c[i]); 470 if(x == 2) 471 { 472 hasOddCycle = 1; 473 break; 474 } 475 } 476 reverse(res.begin(), res.end()); 477 return res; 478 } 479 480 void make() 481 { 482 for(int i = S - 1; i; i--) 483 { 484 if(i >= M) 485 { 486 range[i] = Segment(i - M, i - M + 1); 487 if(i - M < m) 488 seg[i].push_back(es[i - M]); 489 } 490 else 491 { 492 range[i] = merge(range[i * 2], range[i * 2 + 1]); 493 seg[i] = merge(seg[i * 2], seg[i * 2 + 1]); 494 } 495 } 496 } 497 498 int solve(Segment s) 499 { 500 Edges es; 501 hasOddCycle = 0; 502 for(int l = s.l + M, r = s.r + M; l < r; l /= 2, r /= 2) 503 { 504 if(l % 2) 505 es = merge(es, seg[l++]); 506 if(r % 2) 507 es = merge(es, seg[--r]); 508 } 509 if(hasOddCycle) 510 return es[0].w; 511 return -1; 512 } 513 514 int main() 515 { 516 cin >> n >> m >> q; 517 for(int i = 0; i < m; i++) 518 { 519 es[i].u = in() - 1; 520 es[i].v = in() - 1; 521 es[i].w = in(); 522 } 523 make(); 524 while(q--) 525 { 526 int l = in() - 1, r = in(); 527 cout << solve(Segment(l, r)) << "\n"; 528 } 529 } 530 ``` 531 532 ### [687E: TOF](//codeforces.com/contest/687/problem/E) 533 534 #### Hint: What the actual problem is 535 536 Looking at the code in the statement, you can see only the first edge in `neighbors` of each node is important. So for each vertex with at least one outgoing edge, you have to choose one edge and ignore the others. After this the graph becomes in the shape of some cycles with possible branches, and some paths. The number of `dfs` calls equals to 998 × ( sum of sizes of cycles ) + *n* + number of cycles. 537 538 #### Solution 539 540 The goal is to minimize the sum of cycle sizes. Or, to maximize the number of vertices which are not in any cycle. Name them *good vertices*. 541 542 * If there exists a vertex *v* without any outgoing edge, we can make all of the vertices that *v* is reachable from them good. Consider the dfs-tree from *v* in the reverse graph. You can choose the edge  from this tree as the first edge in `neighbors[u]`, in order to make all of these vertices good. 543 * Vertices which are not in the sink strongly connected components could become good too, by choosing the edges from a path starting from them and ending in a sink strongly connected component. 544 * In a sink strongly connected component, there exists a path from every vertex to others. So we can make every vertex good except a single cycle, by choosing the edges in the paths from other nodes to this cycle and the cycle edges. 545 546 So, every vertices could become good except a single cycle in every sink strongly connected component. And the length of those cycles must be minimized, so we can choose the smallest cycle in every sink strongly connected component and make every other vertices good. Finding the smallest cycle in a graph with *n*-vertex and *m* edges could be done in *O*(*n*(*n* + *m*)) with running a *BFS* from every vertex, so finding the smallest cycle in every sink strongly connected component is *O*(*n*(*n* + *m*)) overall. 547 548 **C++ code** 549 550 ``` 551 // . .. ... .... ..... be name khoda ..... .... ... .. . \\ 552 553 #include <bits/stdc++.h> 554 using namespace std; 555 556 inline int in() { int x; scanf("%d", &x); return x; } 557 const int N = 5005; 558 559 int comp[N], bfsDist[N], bfsPar[N]; 560 vector <int> g[N], gR[N]; 561 bool mark[N], inCycle[N]; 562 563 bool dfs(int v, vector <int> *g, vector <int> &nodes) 564 { 565 mark[v] = 1; 566 for(int u : g[v]) 567 if(!mark[u]) 568 dfs(u, g, nodes); 569 nodes.push_back(v); 570 } 571 572 int findSmallestCycle(vector <int> vs) 573 { 574 vector <int> cycle; 575 for(int root : vs) 576 { 577 for(int v : vs) 578 { 579 bfsDist[v] = 1e9; 580 bfsPar[v] = -1; 581 } 582 bfsDist[root] = 0; 583 queue <int> q; 584 q.push(root); 585 bool cycleFound = 0; 586 while(q.size() && !cycleFound) 587 { 588 int v = q.front(); 589 q.pop(); 590 for(int u : g[v]) 591 { 592 if(u == root) 593 { 594 cycleFound = 1; 595 int curLen = bfsDist[v]; 596 if(cycle.empty() || curLen < cycle.size()) 597 { 598 cycle.clear(); 599 for(; v != -1; v = bfsPar[v]) 600 cycle.push_back(v); 601 } 602 break; 603 } 604 if(bfsDist[u] > bfsDist[v] + 1) 605 { 606 bfsDist[u] = bfsDist[v] + 1; 607 bfsPar[u] = v; 608 q.push(u); 609 } 610 } 611 } 612 } 613 return cycle.size(); 614 } 615 616 int main() 617 { 618 int n, m; 619 cin >> n >> m; 620 for(int i = 0; i < m; i++) 621 { 622 int u = in() - 1; 623 int v = in() - 1; 624 g[u].push_back(v); 625 gR[v].push_back(u); 626 } 627 vector <int> order; 628 for(int i = 0; i < n; i++) 629 if(!mark[i]) 630 dfs(i, g, order); 631 632 fill(mark, mark + n, 0); 633 fill(comp, comp + n, -1); 634 int inCycle = 0, nCycle = 0; 635 for(; order.size(); order.pop_back()) 636 { 637 int v = order.back(); 638 if(mark[v]) 639 continue; 640 vector <int> curComp; 641 dfs(v, gR, curComp); 642 bool isSink = true; 643 for(int u : curComp) 644 comp[u] = v; 645 for(int u : curComp) 646 for(int k = 0; k < g[u].size(); k++) 647 if(comp[g[u][k]] != v) 648 isSink = false; 649 if(isSink) 650 { 651 int x = findSmallestCycle(curComp); 652 if(x > 0) 653 { 654 nCycle++; 655 inCycle += x; 656 } 657 } 658 } 659 cout << 999 * inCycle + (n - inCycle) + nCycle << endl; 660 661 } 662 ``` 663 664 #### Challenge 665 666 What if the target function is reversed? It means you have to choose a single outgoing edge from every node with at least one outgoing edge, and maximize the sum of cycle sizes in the chosen graph. 667 668 I thought about this one a lot but can't find any solution. Do you have any idea?