745.md (30553B)
1 Source: https://codeforces.com/blog/entry/49126 2 3 Short solutions: 4 5 * Div2A: How many times do we need to do a cyclic shift to consider all possible ones? Afterwards, what data structure allows us to easily check number of distinct elements? 6 * Div2B: Imagine the process in reverse. What types of identical shapes can I get if I cut a rectangle into two pieces? Remember, pieces cannot be rotated or flipped. 7 * Div2C / Div1A: How do we handle components with special nodes? What do we do with the ones without special nodes? 8 * Div2D / Div1B: We don't get many questions, so is there a way to "parallelize" questions? Another approach, can we split up the condition i != j somehow using bits? 9 * Div2E / Div1C: First, somehow reduce it so r_i,b_i <= n. Now, we can bound the excess tokens by a small number, so we can do bitmask dp from here. 10 * Div1D: The optimal circle must touch a blue point. Now, either consider the inversion, or do a binary search 11 * Div1E: What makes a list good? How fast can we do this check, and how many times do we need to do this check? 12 13 Long solutions: 14 15 ## [Hongcow Learns the Cyclic Shift](//codeforces.com/contest/745/problem/A) 16 17 We only need to consider at most |s| cyclic shifts (since |s| cyclic shifts returns us back to the original string). 18 19 So, we can put these all in a set, and return the size of the set. 20 21 **code** 22 23 ``` 24 print (lambda s: len(set(s[i:] + s[:i] for i in range(len(s)))))(raw_input()) 25 ``` 26 27 ## [Hongcow Solves A Puzzle](//codeforces.com/contest/745/problem/B) 28 29 I really apologize for the ambiguity of this problem. We worked hard to make it concise and accurate, but we left out too many details. 30 31 Basically, the idea is we want to overlay two of these pieces together so that no square has more than 1 X, and the region of X's forms a rectangle. 32 33 Now for the solution: 34 35 First, let's look at it backwards. I have a rectangle, and I cut it in two pieces. These two pieces have the same exact shape. What shapes can I form? 36 37 A necessary and sufficient condition is that the piece itself is a rectangle itself! There are a few ways to check this. One is, find the min/max x/y coordinates, and make sure the number of X's match the bounding box of all the points. 38 39 **code** 40 41 ``` 42 n,m = map(int, raw_input().split()) 43 piece = [raw_input().rstrip() for i in range(n)] 44 45 maxx, minx, maxy, miny = -1, n, -1, m 46 count = 0 47 for i in range(n): 48 for j in range(m): 49 if piece[i][j] == 'X': 50 maxx = max(maxx, i) 51 minx = min(minx, i) 52 maxy = max(maxy, j) 53 miny = min(miny, j) 54 count += 1 55 56 print ((maxx - minx + 1) * (maxy - miny + 1) == count) * "YES" or "NO" 57 ``` 58 59 ## [Hongcow Builds a Nation](//codeforces.com/contest/744/problem/A) 60 61 First, let's make all connected components cliques. This graph is still stable. 62 63 Now, there are some components without special nodes. Where should we connect them? 64 65 If there is a component with size A and a component with size B, we can add A*B edges if we connect these two components. So, it makes sense to choose the largest component. 66 67 **code** 68 69 ``` 70 n,m,k = map(int, raw_input().split()) 71 special = map(int, raw_input().split()) 72 73 root = range(n+1) 74 75 def par(p): 76 if p != root[p]: 77 root[p] = par(root[p]) 78 return root[p] 79 80 def c2(n): 81 return n * (n - 1) / 2 82 83 for __ in xrange(m): 84 u,v = map(par, map(int, raw_input().split())) 85 root[v] = u 86 87 sz = [0 for i in range(n+1)] 88 for i in range(n+1): 89 sz[par(i)] += 1 90 91 leftover = n 92 ans = 0 93 largest = 0 94 for x in special: 95 d = par(x) 96 largest = max(largest, sz[d]) 97 ans += c2(sz[d]) 98 leftover -= sz[d] 99 100 ans -= c2(largest) 101 ans += c2(largest + leftover) 102 ans -= m 103 104 print ans 105 ``` 106 107 ## [Hongcow's Game](//codeforces.com/contest/744/problem/B) 108 109 For the bits solution: We want to create 20 questions where for every i != j, there exists a question 110 111 that contains j and not i, and also a qusetion that contains i and not j. If we can do this, we can find the min for each row. 112 113 Note that i != j implies that there exists a bit index where i and j differ. 114 115 So, let's ask 2 questions for each bit position, one where all indices have a value of 0 in that position, and one where all indices have a value of 1 in that position. This is a total of at most 20 questions, and we can show that this satisfies the condition above, so this solves the problem. 116 117 Parallelization will basically reduce to the above solution, but is another way of looking at the problem. 118 119 First, let's ask {1,2,...,n/2} and {n/2+1,...,n} This handles the case where the min lies on the opposite half. 120 121 ``` 122 [ 123 OOOOXXXX 124 OOOOXXXX 125 OOOOXXXX 126 OOOOXXXX 127 XXXXOOOO 128 XXXXOOOO 129 XXXXOOOO 130 XXXXOOOO 131 ] 132 ``` 133 134 For example, this handles the case where the min lies in the X part of the matrix, and we split it into two identical problems of size n/2 within the O matrix. 135 136 Now, we can ask questions for each submatrix, but we can notice that these two don't interact so we can combine all the questions at this level. 137 138 However, we should ask the questions in parallel, as we don't have that many questions For example, for n=8, we should ask 139 140 ``` 141 First level: 142 [1,2,3,4] 143 [5,6,7,8] 144 145 Second level 146 [1,2],[5,6] (i.e. ask 1,2,5,6 all together, but this is actually two different subproblems, one for the top left, and one for the bottom right). 147 [3,4],[7,8] 148 149 Third level 150 [1],[3],[5],[7] 151 [2],[4],[6],[8] 152 ``` 153 154 As you can see, this reduces to the bit approach above if N is a power of 2. 155 156 **code** 157 158 ``` 159 import java.io.PrintWriter; 160 import java.util.ArrayList; 161 import java.util.Arrays; 162 import java.util.Scanner; 163 164 public class HiddenMatrix { 165 public static void main (String[] args) { 166 Scanner in = new Scanner(System.in); 167 PrintWriter out = new PrintWriter(System.out); 168 int n = in.nextInt(); 169 int[] min = new int[n+1]; 170 Arrays.fill(min, 1 << 30); 171 for (int bit = 0; bit < 10; bit++) { 172 for (int val = 0; val <= 1; val++) { 173 ArrayList<Integer> query = new ArrayList<>(); 174 for (int i = 1; i <= n; i++) { 175 if (((i >> bit) & 1) == val) { 176 query.add(i); 177 } 178 } 179 if (query.size() != n && query.size() != 0) { 180 out.println(query.size()); 181 for (int j = 0; j < query.size(); j++) { 182 if (j != 0) out.print(" "); 183 out.print(query.get(j)); 184 } 185 out.println(); 186 out.flush(); 187 188 for (int i = 1; i <= n; i++) { 189 int d = in.nextInt(); 190 if (((i >> bit) & 1) == 1 - val) { 191 min[i] = Math.min(min[i], d); 192 } 193 } 194 } 195 } 196 } 197 198 out.println(-1); 199 for (int i = 1; i <= n; i++) { 200 if (i != 1) out.print(" "); 201 out.print(min[i]); 202 } 203 out.println(); 204 out.flush(); 205 System.exit(0); 206 } 207 } 208 ``` 209 210 ## [Hongcow Buys a Deck of Cards](//codeforces.com/contest/744/problem/C) 211 212 Also note that if r_i or b_i >= n, we need to collect tokens no matter what since those costs can't be offset. So, we can assume that r_i, b_i <= n. 213 214 Let's only buy tokens when we need them. Note that after buying a card, you will have either 0 red tokens or 0 blue tokens, so our dp state can be described by [mask][which one is zero][how many of the other] The dimensions of this dp table are 2^n * 2 * (n^2) (n^2 because the costs to buy cards is at most n). 215 216 See the code for more details on how to update this dp. 217 218 **code** 219 220 ``` 221 import java.util.Arrays; 222 import java.util.Scanner; 223 224 public class RedAndBlueCards { 225 public static int n; 226 public static char[] color; 227 public static int[] r,b; 228 public static int[] countred, countblue; 229 public static void main (String[] args) { 230 Scanner in = new Scanner(System.in); 231 n = in.nextInt(); 232 color = new char[n]; 233 r = new int[n]; 234 b = new int[n]; 235 int base = 0; 236 int needred = 0, needblue = 0; 237 for (int i = 0; i < n; i++) { 238 color[i] = in.next().charAt(0); 239 r[i] = in.nextInt(); 240 b[i] = in.nextInt(); 241 needred += Math.max(0, r[i] - n); 242 needblue += Math.max(0, b[i] - n); 243 r[i] = Math.min(n, r[i]); 244 b[i] = Math.min(n, b[i]); 245 } 246 base = Math.max(needred, needblue); 247 248 countred = new int[1<<n]; 249 countblue = new int[1<<n]; 250 for (int i = 1; i < 1 << n; i++) { 251 int lowbit = Integer.numberOfTrailingZeros(i & -i); 252 countred[i] = countred[i ^ (1 << lowbit)]; 253 countblue[i] = countblue[i ^ (1 << lowbit)]; 254 if (color[lowbit] == 'R') countred[i]++; 255 else countblue[i]++; 256 } 257 258 dp = new int[2][n*n+1][1<<n]; 259 for (int[][] x : dp) for (int[] y : x) Arrays.fill(y, -1); 260 261 int ans = base + n; 262 if (needred < needblue) { 263 ans += solve(0, 0, needblue - needred); 264 } else { 265 ans += solve(0, 1, needred - needblue); 266 } 267 System.out.println(ans); 268 System.exit(0); 269 } 270 271 public static int[][][] dp; 272 public static int solve(int mask, int redempty, int other) { 273 other = Math.min(other, n*n); 274 if (mask == (1<<n)-1) return 0; 275 if (dp[redempty][other][mask] != -1) return dp[redempty][other][mask]; 276 int ret = 1 << 29; 277 for (int i = 0; i < n; i++) { 278 if (((mask>>i)&1) == 1) continue; 279 int pmask = mask | (1 << i); 280 int havered = redempty == 1 ? 0 : other; 281 int haveblue = redempty == 0 ? 0 : other; 282 int cardred = countred[mask], cardblue = countblue[mask]; 283 284 int nred = Math.max(0, r[i]-(cardred+havered)); 285 int nblue = Math.max(0, b[i]-(cardblue+haveblue)); 286 int needmoves = Math.max(nred, nblue); 287 int nextred = havered + needmoves - Math.max(0, r[i] - cardred); 288 int nextblue = haveblue + needmoves - Math.max(0, b[i] - cardblue); 289 290 if (nextred == 0) { 291 ret = Math.min(ret, needmoves + solve(pmask, 1, nextblue)); 292 } 293 if (nextblue == 0) { 294 ret = Math.min(ret, needmoves + solve(pmask, 0, nextred)); 295 } 296 } 297 return dp[redempty][other][mask] = ret; 298 } 299 } 300 ``` 301 302 ## [Hongcow Draws a Circle](//codeforces.com/contest/744/problem/D) 303 304 First to check if an answer can be arbitrarily large, we can see if there is any red point that is on the convex hull of all our points. So from now on, we can assume the answer is finite. 305 306 We can show that the optimal circle must touch a blue point. To see this, consider any optimal circle that doesn't touch a blue point. We can make it slightly bigger so that it does touch one. 307 308 So, let's binary search for the answer. However, you have to very careful and notice that the binary search isn't monotonic if we only consider circles touching blue points. However, if we consider circles that touch either a red or blue point, then the binary search is monontonic, so everything works out. 309 310 To check if a radius works, we can do a angle sweep around our center point. We have a fixed radius and fixed center, so each other point has at most two angles where it enters and exits the circle as we rotate it about the center point. We can keep track of these events and find an interval where the circle only contains red points. 311 312 **code for binary search** 313 314 ``` 315 import java.io.*; 316 import java.util.ArrayList; 317 import java.util.Arrays; 318 import java.util.Collections; 319 import java.util.StringTokenizer; 320 321 public class RedAndBluePoints { 322 public static double EPS = 1e-9; 323 public static int PENALTY = 1000000; 324 public static int n,m; 325 public static long[] x, y; 326 public static double[][] d; 327 public static void main (String[] args) { 328 InputReader in = new InputReader(System.in); 329 PrintWriter out = new PrintWriter(System.out, true); 330 331 n = in.nextInt(); 332 m = in.nextInt(); 333 x = new long[n+m]; 334 y = new long[n+m]; 335 d = new double[n+m][n+m]; 336 Point[] ps = new Point[n+m]; 337 for (int i = 0; i < n+m; i++) { 338 x[i] = in.nextInt(); 339 y[i] = in.nextInt(); 340 ps[i] = new Point(x[i], y[i]); 341 } 342 ps = convexHull(ps); 343 for (int i = 0; i < n; i++) { 344 for (int j = 0; j < ps.length; j++) { 345 if (onSegment(ps[j], ps[(j+1)%ps.length], new Point(x[i],y[i]))) { 346 out.println(-1); 347 out.close(); 348 System.exit(0); 349 } 350 } 351 } 352 353 for (int i = 0; i < n+m; i++) { 354 for (int j = 0; j < n+m; j++) { 355 d[i][j] = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); 356 } 357 } 358 359 double lower = 0; 360 for (int startpoint = 0; startpoint < n+m; startpoint++) { 361 if (!ok(startpoint, lower)) continue; 362 double add = 20; 363 int iter = 30; 364 while (ok(startpoint, lower+2*add)) { 365 add *= 2; 366 iter++; 367 } 368 double lo = lower; 369 double hi = lower+2*add; 370 while (hi - lo > 1e-8 && iter-->0) { 371 double mid = (lo + hi) / 2.0; 372 if (ok(startpoint, mid)) lo = mid; 373 else hi = mid; 374 } 375 lower = lo; 376 } 377 out.printf("%.10f\n", lower); 378 } 379 380 public static boolean ok(int center, double rad) { 381 ArrayList<State> w = new ArrayList<>(); 382 int cur = center < n ? 1 : 0; 383 for (int j = 0; j < n+m; j++) { 384 if (j == center) continue; 385 double reach = 2 * rad; 386 if (reach * reach < d[center][j] + EPS) continue; 387 388 double[] q = getAngles(center, j, rad); 389 int add = j < n ? 1 : -PENALTY; 390 if (q[1] < q[0]) cur += add; 391 w.add(new State(q[0] - EPS, add)); 392 w.add(new State(q[1] + EPS, -add)); 393 } 394 Collections.sort(w); 395 int res = cur; 396 for (State s : w) { 397 cur += s.inc; 398 res = Math.max(res, cur); 399 } 400 return res >= 1; 401 } 402 403 // returns two angles tangent to point i1 and point i2 with radius. 404 public static double[] getAngles(int i1, int i2, double rad) { 405 double D = d[i1][i2]; 406 double c = D/2.0; 407 double b = Math.sqrt(D*rad*rad-c*c); 408 double nx = (x[i2] - x[i1]) / D, ny = (y[i2] - y[i1]) / D; 409 double bx = -ny * b, by = nx * b; 410 double ax = nx * c, ay = ny * c; 411 412 return new double[] { 413 Math.atan2(ay - by, ax - bx), 414 Math.atan2(ay + by, ax + bx), 415 }; 416 } 417 418 public static class Point { 419 public final long x, y; 420 421 public Point(long x, long y) { 422 this.x = x; 423 this.y = y; 424 } 425 } 426 public static Point[] convexHull(Point[] p) { 427 int n = p.length; 428 if (n <= 1) 429 return p; 430 Arrays.sort(p, (a, b) -> Long.compare(a.x, b.x) != 0 ? Long.compare(a.x, b.x) : Long.compare(a.y, b.y)); 431 Point[] h = new Point[n * 2]; 432 int cnt = 0; 433 for (int i = 0; i < n; h[cnt++] = p[i++]) 434 while (cnt > 1 && cross(h[cnt - 2], h[cnt - 1], p[i]) >= 0) 435 --cnt; 436 for (int i = n - 2, t = cnt; i >= 0; h[cnt++] = p[i--]) 437 while (cnt > t && cross(h[cnt - 2], h[cnt - 1], p[i]) >= 0) 438 --cnt; 439 return Arrays.copyOf(h, cnt - 1 - (h[0].x == h[1].x && h[0].y == h[1].y ? 1 : 0)); 440 } 441 442 static long cross(Point a, Point b, Point c) { 443 return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); 444 } 445 446 public static boolean onSegment(Point a, Point b, Point c) { 447 // does c lie on segment ab 448 return c.x >= Math.min(a.x, b.x) && c.x <= Math.max(a.x, b.x) && 449 c.y >= Math.min(a.y, b.y) && c.y <= Math.max(a.y, b.y) && 450 (c.x - a.x) * (c.y - b.y) == (c.x - b.x) * (c.x - a.y); 451 } 452 453 static class State implements Comparable<State> { 454 public double angle; 455 public int inc; 456 public State (double angle, int inc) { 457 this.angle = angle; 458 this.inc = inc; 459 } 460 461 public int compareTo(State other) { 462 if (angle < other.angle) return -1; 463 if (angle > other.angle) return 1; 464 return 0; 465 } 466 } 467 468 static class InputReader { 469 public BufferedReader reader; 470 public StringTokenizer tokenizer; 471 472 public InputReader(InputStream stream) { 473 reader = new BufferedReader(new InputStreamReader(stream), 32768); 474 tokenizer = null; 475 } 476 477 public String next() { 478 while (tokenizer == null || !tokenizer.hasMoreTokens()) { 479 try { 480 tokenizer = new StringTokenizer(reader.readLine()); 481 } catch (IOException e) { 482 throw new RuntimeException(e); 483 } 484 } 485 return tokenizer.nextToken(); 486 } 487 488 public int nextInt() { 489 return Integer.parseInt(next()); 490 } 491 } 492 } 493 ``` 494 495 For the inversion solution, let's fix the blue point that our circle touches. Then, let's take the inversion around this point (i.e. <https://en.wikipedia.org/wiki/Inversive_geometry)>. Now, circles that pass through our center points become lines, and the interior of those circles are in the halfplane not containing the center point. The radius of the circle is inversely proportional to the distance between our center point to the line after inversion. 496 497 So, we can say we want to solve the following problem after inversion. Find the closest line that contains no blue points in the halfplane facing away from our center point and at least one red point. We can notice that we only need to check lines that contain a blue point on the convex hull after inversion. 498 499 To make implementation easier, you can make the additional observation that the sum of all convex hull sizes will be linear through the process of the algorithm. Some intuition behind this observation is that only adjacent nodes in a delaunay triangluation can appear on the convex hull after inversion, so the sum is bounded by the number of edges in such a triangulation (of course, we do not need to explicitly find the triangulation). 500 501 **code for inversion** 502 503 ``` 504 #pragma comment(linker, "/STACK:1000000000") 505 #include <cstdio> 506 #include <cmath> 507 #include <cstdlib> 508 #include <cassert> 509 #include <ctime> 510 #include <cstring> 511 #include <string> 512 #include <set> 513 #include <map> 514 #include <vector> 515 #include <list> 516 #include <deque> 517 #include <queue> 518 #include <sstream> 519 #include <iostream> 520 #include <algorithm> 521 522 using namespace std; 523 524 #define pb push_back 525 #define mp make_pair 526 #define fs first 527 #define sc second 528 #define double long double 529 530 const double pi = acos(-1.0); 531 const double eps1 = 1e-7; 532 const double eps2 = 1e-14; 533 534 double sqr(double x) { 535 return x * x; 536 } 537 538 struct pt { 539 double x, y; 540 541 pt(double x_ = 0.0, double y_ = 0.0) : x(x_), y(y_) {} 542 }; 543 544 pt operator + (const pt& a, const pt& b) { 545 return pt(a.x + b.x, a.y + b.y); 546 } 547 548 pt operator - (const pt& a, const pt& b) { 549 return pt(a.x - b.x, a.y - b.y); 550 } 551 552 pt operator * (const pt& a, double k) { 553 return pt(a.x * k, a.y * k); 554 } 555 556 struct line { 557 double a, b, c; 558 line(double a_ = 1.0, double b_ = 0.0, double c_ = 0.0): a(a_), b(b_), c(c_) { 559 norm(); 560 } 561 562 line(const pt& p1, const pt& p2) { 563 a = p2.y - p1.y; 564 b = p1.x - p2.x; 565 c = -a * p1.x - b * p1.y; 566 567 norm(); 568 } 569 570 void norm() { 571 double k = sqrt(sqr(a) + sqr(b)); 572 a /= k; 573 b /= k; 574 c /= k; 575 } 576 577 double dist(const pt& p) const { 578 return a * p.x + b * p.y + c; 579 } 580 }; 581 bool cmp (pt a, pt b) { 582 return (a.x < b.x) || (a.x == b.x && a.y < b.y); 583 } 584 585 bool cw (pt a, pt b, pt c) { 586 return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < -eps2; 587 } 588 589 bool ccw (pt a, pt b, pt c) { 590 return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > eps2; 591 } 592 593 void convex_hull (vector<pt> & a) { 594 if (a.size() == 1) return; 595 if (a.size() == 2) return; 596 sort (a.begin(), a.end(), &cmp); 597 pt p1 = a[0], p2 = a.back(); 598 vector<pt> up, down; 599 up.push_back (p1); 600 down.push_back (p1); 601 for (size_t i=1; i<a.size(); ++i) { 602 if (i==a.size()-1 || cw (p1, a[i], p2)) { 603 while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i])) 604 up.pop_back(); 605 up.push_back (a[i]); 606 } 607 if (i==a.size()-1 || ccw (p1, a[i], p2)) { 608 while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i])) 609 down.pop_back(); 610 down.push_back (a[i]); 611 } 612 } 613 a.clear(); 614 for (size_t i=0; i<up.size(); ++i) 615 a.push_back (up[i]); 616 for (size_t i=down.size()-2; i>0; --i) 617 a.push_back (down[i]); 618 } 619 620 int sign(double x) { 621 if (fabs(x) < eps2) 622 return 0; 623 if (x > 0) 624 return 1; 625 return -1; 626 } 627 628 int main() { 629 //freopen("input.txt", "r", stdin); 630 //freopen("output.txt", "w", stdout); 631 632 int n, m; 633 634 cin >> n >> m; 635 636 vector <pt> red(n), blue(m); 637 for (int i = 0; i < n; i++) { 638 cin >> red[i].x >> red[i].y; 639 } 640 641 for (int i = 0; i < m; i++) { 642 cin >> blue[i].x >> blue[i].y; 643 } 644 645 if (m == 1) { 646 cout << -1 << endl; 647 return 0; 648 } 649 vector <pt> cvx_blue = blue; 650 convex_hull(cvx_blue); 651 int k = cvx_blue.size(); 652 653 for (int i = 0; i < n; i++) { 654 bool flag = true; 655 for (int j = 0; j < k; j++) { 656 line hl(cvx_blue[j % k], cvx_blue[(j + 1) % k]); 657 if (hl.dist(red[i]) > eps1) { 658 flag = false; 659 } 660 } 661 662 if (flag) { 663 cout << -1 << endl; 664 665 return 0; 666 } 667 668 } 669 670 double ans = 0.0; 671 672 for (int i = 0; i < m; i++) { 673 vector <pt> new_blue; 674 for (int j = 0; j < i; j++) { 675 new_blue.pb(blue[j] - blue[i]); 676 double d = sqr(new_blue.back().x) + sqr(new_blue.back().y); 677 new_blue.back().x /= d; 678 new_blue.back().y /= d; 679 } 680 681 new_blue.pb(pt(0.0, 0.0)); 682 683 for (int j = i + 1; j < m; j++) { 684 new_blue.pb(blue[j] - blue[i]); 685 double d = sqr(new_blue.back().x) + sqr(new_blue.back().y); 686 new_blue.back().x /= d; 687 new_blue.back().y /= d; 688 } 689 690 vector <pt> new_red; 691 for (int j = 0; j < n; j++) { 692 new_red.pb(red[j] - blue[i]); 693 double d = sqr(new_red.back().x) + sqr(new_red.back().y); 694 new_red.back().x /= d; 695 new_red.back().y /= d; 696 } 697 698 convex_hull(new_blue); 699 700 int k = new_blue.size(); 701 int p = new_red.size(); 702 703 for (int j = 0; j < k; j++) { 704 bool flag = false; 705 line hl(new_blue[j], new_blue[(j + 1) % k]); 706 707 for (int q = 0; q < p; q++) { 708 if (hl.dist(new_red[q]) < eps2) 709 flag = true; 710 } 711 712 if (flag) { 713 if (abs(hl.dist(pt(0.0, 0.0))) < eps2) { 714 cout << -1 << endl; 715 716 return 0; 717 } 718 // cerr << hl.dist(pt(0.0, 0.0)) << endl; 719 /* 720 if (fabs(hl.dist(pt(0.0, 0.0))) < eps) { 721 cout << -1 << endl; 722 return 0; 723 } 724 */ 725 ans = max(ans, 1.0 / abs(hl.dist(pt(0.0, 0.0)))); 726 } 727 } 728 729 for (int q = 0; q < p; q++) { 730 for (int j = 0; j < k; j++) { 731 line hl(new_red[q], new_blue[j]); 732 if (sign(hl.dist(new_blue[(j + 1) % k])) * sign(hl.dist(new_blue[(j + k - 1) % k])) >= 0) { 733 if (abs(hl.dist(pt(0.0, 0.0))) < eps2) { 734 cout << -1 << endl; 735 736 return 0; 737 } 738 739 // cerr << hl.dist(pt(0.0, 0.0)) << endl; 740 ans = max(ans, 1.0 / abs(hl.dist(pt(0.0, 0.0)))); 741 } 742 } 743 } 744 } 745 746 cout.precision(20); 747 cout << ans / 2.0 << endl; 748 749 return 0; 750 } 751 ``` 752 753 ## [Hongcow Masters the Cyclic Shift](//codeforces.com/contest/744/problem/E) 754 755 Let M denote the total number of characters across all strings. 756 757 Consider how long it takes to compute f(L) for a single list. 758 759 Consider a graph where nodes are suffixes of strings. This means we already spelled out the prefix, and still need to spell out the suffix. 760 761 There are at most M nodes in this graph. Now, draw at most N edges connecting suffixes to each other. We can find the edges efficiently by doing suffix arrays or z algorithm or hashes. 762 763 Now, we claim is the list is good if and only if there is no cycle in this graph. You can notice that a cycle exists => we can construct a bad word. Also, if a bad word exists => we can form a cycle. So, we can check if there is a cycle, which takes O(N*M) time. 764 765 Next step is to notice that extending a bad list will never make it good. So we can do two pointers to find all good intervals, which requires O(n) calls to the check function. So, overall this runs in O(N^2*M) time. 766 767 You might be wondering why this problem asks for sublists rather than the entire list. To be honest, it's just to make tests slightly stronger (i.e. I get ~30^2x the number of tests in the same amount of space). 768 769 **code** 770 771 ``` 772 import java.io.*; 773 import java.util.ArrayList; 774 import java.util.Arrays; 775 import java.util.StringTokenizer; 776 777 public class CyclicShiftsAgainAgain { 778 public static int n; 779 public static String[] s; 780 public static int[] len; 781 public static void main (String[] args) { 782 InputReader in = new InputReader(System.in); 783 PrintWriter out = new PrintWriter(System.out, true); 784 n = in.nextInt(); 785 s = new String[n+1]; 786 len = new int[n+1]; 787 s[0] = ""; 788 len[0] = 0; 789 for (int i = 1; i <= n; i++) { 790 s[i] = in.next(); 791 len[i] = len[i-1] + s[i].length(); 792 } 793 794 int ans = 0; 795 int front = 0; 796 for (int i = 1; i <= n; i++) { 797 while (!isGood(front+1, i)) front++; 798 ans += i - front; 799 } 800 801 out.println(ans); 802 out.close(); 803 System.exit(0); 804 } 805 806 public static boolean isGood(int from, int to) { 807 if (from > to) return true; 808 int numnodes = len[to] - len[from - 1]; 809 ArrayList<Integer>[] graph = new ArrayList[numnodes+1]; 810 for (int i = 0; i <= numnodes; i++) graph[i] = new ArrayList<>(); 811 for (int startword = from; startword <= to; startword++) { 812 graph[numnodes].add(len[startword-1] - len[from-1]); 813 StringBuilder sb = new StringBuilder(); 814 sb.append(s[startword]); 815 sb.append("$"); 816 for (int k = from; k <= to; k++) { 817 if (k == startword) continue; 818 sb.append(s[k]); 819 sb.append("#"); 820 } 821 int[] z = zz(sb.toString().toCharArray()); 822 823 int curchar = 0; 824 for (int i = 1; i < s[startword].length(); i++) { 825 if (z[i] + i >= s[startword].length()) { 826 graph[i + len[startword-1] - len[from -1]].add(z[i] + len[startword-1] - len[from-1]); 827 } 828 } 829 int curword = startword == from ? (from+1) : from; 830 for (int i = s[startword].length()+1; i+1 < z.length; i++) { 831 if (sb.charAt(i) == '#') { 832 i++; 833 curword++; 834 if (curword == startword) curword++; 835 curchar = 0; 836 } 837 838 int curnode = curchar + len[curword-1] - len[from-1]; 839 if (z[i] + curchar >= s[curword].length()) { 840 if (z[i] == s[startword].length()) { 841 if (curchar != 0) graph[curnode].add(numnodes); 842 } else { 843 graph[curnode].add(z[i] + len[startword-1] - len[from-1]); 844 } 845 } else if (z[i] == s[startword].length()) { 846 graph[curnode].add(curnode + z[i]); 847 } 848 curchar++; 849 } 850 851 } 852 return isDAG(graph); 853 } 854 855 public static int[] zz(char[] let) { 856 int N = let.length; 857 int[] z = new int[N]; 858 int L = 0, R = 0; 859 for (int i = 1; i < N; i++) { 860 if (i > R) { 861 L = R = i; 862 while (R < N && let[R - L] == let[R]) 863 R++; 864 z[i] = R - L; 865 R--; 866 } else { 867 int k = i - L; 868 if (z[k] < R - i + 1) 869 z[i] = z[k]; 870 else { 871 L = i; 872 while (R < N && let[R - L] == let[R]) 873 R++; 874 z[i] = R - L; 875 R--; 876 } 877 } 878 } 879 z[0] = N; 880 return z; 881 } 882 883 private static boolean isDAG(ArrayList<Integer>[] graph) { 884 int n = graph.length; 885 int[] indeg = new int[n]; 886 for (int i = 0; i < n; i++) for (int x : graph[i]) indeg[x]++; 887 int[] queue = new int[n]; 888 int front = 0, back = 0, idx = 0; 889 890 for (int i = 0; i < indeg.length; i++) 891 if (indeg[i] == 0) 892 queue[back++] = i; 893 894 while (front != back) { 895 int node = queue[front++]; 896 for (int next : graph[node]) { 897 if (--indeg[next] == 0) { 898 queue[back++] = next; 899 } 900 } 901 } 902 903 return front == n; 904 } 905 906 static class InputReader { 907 public BufferedReader reader; 908 public StringTokenizer tokenizer; 909 910 public InputReader(InputStream stream) { 911 reader = new BufferedReader(new InputStreamReader(stream), 32768); 912 tokenizer = null; 913 } 914 915 public String next() { 916 while (tokenizer == null || !tokenizer.hasMoreTokens()) { 917 try { 918 tokenizer = new StringTokenizer(reader.readLine()); 919 } catch (IOException e) { 920 throw new RuntimeException(e); 921 } 922 } 923 return tokenizer.nextToken(); 924 } 925 926 public int nextInt() { 927 return Integer.parseInt(next()); 928 } 929 } 930 } 931 ```