codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

744.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 ```