Codeforces Round #385 Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Short solutions:

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?
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.
Div2C / Div1A: How do we handle components with special nodes? What do we do with the ones without special nodes?
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?
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.
Div1D: The optimal circle must touch a blue point. Now, either consider the inversion, or do a binary search
Div1E: What makes a list good? How fast can we do this check, and how many times do we need to do this check?

Long solutions:

Hongcow Learns the Cyclic Shift

We only need to consider at most |s| cyclic shifts (since |s| cyclic shifts returns us back to the original string).

So, we can put these all in a set, and return the size of the set.

code

print (lambda s: len(set(s[i:] + s[:i] for i in range(len(s)))))(raw_input())

Hongcow Solves A Puzzle

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.

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.

Now for the solution:

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?

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.

code

n,m = map(int, raw_input().split())
piece = [raw_input().rstrip() for i in range(n)]

maxx, minx, maxy, miny = -1, n, -1, m
count = 0
for i in range(n):
	for j in range(m):
		if piece[i][j] == 'X':
			maxx = max(maxx, i)
			minx = min(minx, i)
			maxy = max(maxy, j)
			miny = min(miny, j)
			count += 1


print ((maxx - minx + 1) * (maxy - miny + 1) == count) * "YES" or "NO"

Hongcow Builds a Nation

First, let's make all connected components cliques. This graph is still stable.

Now, there are some components without special nodes. Where should we connect them?

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.

code

n,m,k = map(int, raw_input().split())
special = map(int, raw_input().split())

root = range(n+1)

def par(p):
	if p != root[p]:
		root[p] = par(root[p])
	return root[p]

def c2(n):
	return n * (n - 1) / 2

for __ in xrange(m):
	u,v = map(par, map(int, raw_input().split()))
	root[v] = u

sz = [0 for i in range(n+1)]
for i in range(n+1):
	sz[par(i)] += 1

leftover = n
ans = 0
largest = 0
for x in special:
	d = par(x)
	largest = max(largest, sz[d])
	ans += c2(sz[d])
	leftover -= sz[d]

ans -= c2(largest)
ans += c2(largest + leftover)
ans -= m

print ans

Hongcow's Game

For the bits solution: We want to create 20 questions where for every i != j, there exists a question

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.

Note that i != j implies that there exists a bit index where i and j differ.

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.

Parallelization will basically reduce to the above solution, but is another way of looking at the problem.

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.

[
OOOOXXXX
OOOOXXXX
OOOOXXXX
OOOOXXXX
XXXXOOOO
XXXXOOOO
XXXXOOOO
XXXXOOOO
]

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.

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.

However, we should ask the questions in parallel, as we don't have that many questions For example, for n=8, we should ask

First level:
[1,2,3,4]
[5,6,7,8]

Second level
[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).
[3,4],[7,8]

Third level
[1],[3],[5],[7]
[2],[4],[6],[8]

As you can see, this reduces to the bit approach above if N is a power of 2.

code

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class HiddenMatrix {
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        int[] min = new int[n+1];
        Arrays.fill(min, 1 << 30);
        for (int bit = 0; bit < 10; bit++) {
            for (int val = 0; val <= 1; val++) {
                ArrayList<Integer> query = new ArrayList<>();
                for (int i = 1; i <= n; i++) {
                    if (((i >> bit) & 1) == val) {
                        query.add(i);
                    }
                }
                if (query.size() != n && query.size() != 0) {
                    out.println(query.size());
                    for (int j = 0; j < query.size(); j++) {
                        if (j != 0) out.print(" ");
                        out.print(query.get(j));
                    }
                    out.println();
                    out.flush();

                    for (int i = 1; i <= n; i++) {
                        int d = in.nextInt();
                        if (((i >> bit) & 1) == 1 - val) {
                            min[i] = Math.min(min[i], d);
                        }
                    }
                }
            }
        }

        out.println(-1);
        for (int i = 1; i <= n; i++) {
            if (i != 1) out.print(" ");
            out.print(min[i]);
        }
        out.println();
        out.flush();
        System.exit(0);
    }
}

Hongcow Buys a Deck of Cards

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.

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).

See the code for more details on how to update this dp.

code

import java.util.Arrays;
import java.util.Scanner;

public class RedAndBlueCards {
    public static int n;
    public static char[] color;
    public static int[] r,b;
    public static int[] countred, countblue;
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        color = new char[n];
        r = new int[n];
        b = new int[n];
        int base = 0;
        int needred = 0, needblue = 0;
        for (int i = 0; i < n; i++) {
            color[i] = in.next().charAt(0);
            r[i] = in.nextInt();
            b[i] = in.nextInt();
            needred += Math.max(0, r[i] - n);
            needblue += Math.max(0, b[i] - n);
            r[i] = Math.min(n, r[i]);
            b[i] = Math.min(n, b[i]);
        }
        base = Math.max(needred, needblue);

        countred = new int[1<<n];
        countblue = new int[1<<n];
        for (int i = 1; i < 1 << n; i++) {
            int lowbit = Integer.numberOfTrailingZeros(i & -i);
            countred[i] = countred[i ^ (1 << lowbit)];
            countblue[i] = countblue[i ^ (1 << lowbit)];
            if (color[lowbit] == 'R') countred[i]++;
            else countblue[i]++;
        }

        dp = new int[2][n*n+1][1<<n];
        for (int[][] x : dp) for (int[] y : x) Arrays.fill(y, -1);

        int ans = base + n;
        if (needred < needblue) {
            ans += solve(0, 0, needblue - needred);
        } else {
            ans += solve(0, 1, needred - needblue);
        }
        System.out.println(ans);
        System.exit(0);
    }

    public static int[][][] dp;
    public static int solve(int mask, int redempty, int other) {
        other = Math.min(other, n*n);
        if (mask == (1<<n)-1) return 0;
        if (dp[redempty][other][mask] != -1) return dp[redempty][other][mask];
        int ret = 1 << 29;
        for (int i = 0; i < n; i++) {
            if (((mask>>i)&1) == 1) continue;
            int pmask = mask | (1 << i);
            int havered = redempty == 1 ? 0 : other;
            int haveblue = redempty == 0 ? 0 : other;
            int cardred = countred[mask], cardblue = countblue[mask];

            int nred = Math.max(0, r[i]-(cardred+havered));
            int nblue = Math.max(0, b[i]-(cardblue+haveblue));
            int needmoves = Math.max(nred, nblue);
            int nextred = havered + needmoves - Math.max(0, r[i] - cardred);
            int nextblue = haveblue + needmoves - Math.max(0, b[i] - cardblue);

            if (nextred == 0) {
                ret = Math.min(ret, needmoves + solve(pmask, 1, nextblue));
            }
            if (nextblue == 0) {
                ret = Math.min(ret, needmoves + solve(pmask, 0, nextred));
            }
        }
        return dp[redempty][other][mask] = ret;
    }
}

Hongcow Draws a Circle

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.

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.

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.

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.

code for binary search

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class RedAndBluePoints {
    public static double EPS = 1e-9;
    public static int PENALTY = 1000000;
    public static int n,m;
    public static long[] x, y;
    public static double[][] d;
    public static void main (String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out, true);

        n = in.nextInt();
        m = in.nextInt();
        x = new long[n+m];
        y = new long[n+m];
        d = new double[n+m][n+m];
        Point[] ps = new Point[n+m];
        for (int i = 0; i < n+m; i++) {
            x[i] = in.nextInt();
            y[i] = in.nextInt();
            ps[i] = new Point(x[i], y[i]);
        }
        ps = convexHull(ps);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < ps.length; j++) {
                if (onSegment(ps[j], ps[(j+1)%ps.length], new Point(x[i],y[i]))) {
                    out.println(-1);
                    out.close();
                    System.exit(0);
                }
            }
        }


        for (int i = 0; i < n+m; i++) {
            for (int j = 0; j < n+m; j++) {
                d[i][j] = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
            }
        }

        double lower = 0;
        for (int startpoint = 0; startpoint < n+m; startpoint++) {
            if (!ok(startpoint, lower)) continue;
            double add = 20;
            int iter = 30;
            while (ok(startpoint, lower+2*add)) {
                add *= 2;
                iter++;
            }
            double lo = lower;
            double hi = lower+2*add;
            while (hi - lo > 1e-8 && iter-->0) {
                double mid = (lo + hi) / 2.0;
                if (ok(startpoint, mid)) lo = mid;
                else hi = mid;
            }
            lower = lo;
        }
        out.printf("%.10f\n", lower);
    }

    public static boolean ok(int center, double rad) {
        ArrayList<State> w = new ArrayList<>();
        int cur = center < n ? 1 : 0;
        for (int j = 0; j < n+m; j++) {
            if (j == center) continue;
            double reach = 2 * rad;
            if (reach * reach < d[center][j] + EPS) continue;

            double[] q = getAngles(center, j, rad);
            int add = j < n ? 1 : -PENALTY;
            if (q[1] < q[0]) cur += add;
            w.add(new State(q[0] - EPS, add));
            w.add(new State(q[1] + EPS, -add));
        }
        Collections.sort(w);
        int res = cur;
        for (State s : w) {
            cur += s.inc;
            res = Math.max(res, cur);
        }
        return res >= 1;
    }

    // returns two angles tangent to point i1 and point i2 with radius.
    public static double[] getAngles(int i1, int i2, double rad) {
        double D = d[i1][i2];
        double c = D/2.0;
        double b = Math.sqrt(D*rad*rad-c*c);
        double nx = (x[i2] - x[i1]) / D, ny = (y[i2] - y[i1]) / D;
        double bx = -ny * b, by = nx * b;
        double ax = nx * c, ay = ny * c;

        return new double[] {
                Math.atan2(ay - by, ax - bx),
                Math.atan2(ay + by, ax + bx),
        };
    }

    public static class Point {
        public final long x, y;

        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }
    public static Point[] convexHull(Point[] p) {
        int n = p.length;
        if (n <= 1)
            return p;
        Arrays.sort(p, (a, b) -> Long.compare(a.x, b.x) != 0 ? Long.compare(a.x, b.x) : Long.compare(a.y, b.y));
        Point[] h = new Point[n * 2];
        int cnt = 0;
        for (int i = 0; i < n; h[cnt++] = p[i++])
            while (cnt > 1 && cross(h[cnt - 2], h[cnt - 1], p[i]) >= 0)
                --cnt;
        for (int i = n - 2, t = cnt; i >= 0; h[cnt++] = p[i--])
            while (cnt > t && cross(h[cnt - 2], h[cnt - 1], p[i]) >= 0)
                --cnt;
        return Arrays.copyOf(h, cnt - 1 - (h[0].x == h[1].x && h[0].y == h[1].y ? 1 : 0));
    }

    static long cross(Point a, Point b, Point c) {
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    }

    public static boolean onSegment(Point a, Point b, Point c) {
        // does c lie on segment ab
        return c.x >= Math.min(a.x, b.x) && c.x <= Math.max(a.x, b.x) &&
                c.y >= Math.min(a.y, b.y) && c.y <= Math.max(a.y, b.y) &&
                (c.x - a.x) * (c.y - b.y) == (c.x - b.x) * (c.x - a.y);
    }


    static class State implements Comparable<State> {
        public double angle;
        public int inc;
        public State (double angle, int inc) {
            this.angle = angle;
            this.inc = inc;
        }

        public int compareTo(State other) {
            if (angle < other.angle) return -1;
            if (angle > other.angle) return 1;
            return 0;
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

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.

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.

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).

code for inversion

#pragma comment(linker, "/STACK:1000000000")
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define double long double

const double pi = acos(-1.0);
const double eps1 = 1e-7;
const double eps2 = 1e-14;

double sqr(double x) {
    return x * x; 
}

struct pt {
	double x, y;

    pt(double x_ = 0.0, double y_ = 0.0) : x(x_), y(y_) {}
};

pt operator + (const pt& a, const pt& b) {
	return pt(a.x + b.x, a.y + b.y);
}

pt operator - (const pt& a, const pt& b) {
	return pt(a.x - b.x, a.y - b.y);
}

pt operator * (const pt& a, double k) {
	return pt(a.x * k, a.y * k);
}

struct line {
	double a, b, c;
	line(double a_ = 1.0, double b_ = 0.0, double c_ = 0.0): a(a_), b(b_), c(c_) {
		norm();
    }

	line(const pt& p1, const pt& p2) {
		a = p2.y - p1.y;
		b = p1.x - p2.x;
		c = -a * p1.x - b * p1.y;

		norm();
	}

	void norm() {
		double k = sqrt(sqr(a) + sqr(b));
		a /= k;
		b /= k;
		c /= k;
	}

	double dist(const pt& p) const {
		return a * p.x + b * p.y + c;
	}
};
bool cmp (pt a, pt b) {
	return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}

bool cw (pt a, pt b, pt c) {
	return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < -eps2;
}

bool ccw (pt a, pt b, pt c) {
	return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > eps2;
}

void convex_hull (vector<pt> & a) {
	if (a.size() == 1)  return;
    if (a.size() == 2) return;
	sort (a.begin(), a.end(), &cmp);
	pt p1 = a[0],  p2 = a.back();
	vector<pt> up, down;
	up.push_back (p1);
	down.push_back (p1);
	for (size_t i=1; i<a.size(); ++i) {
		if (i==a.size()-1 || cw (p1, a[i], p2)) {
			while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
				up.pop_back();
			up.push_back (a[i]);
		}
		if (i==a.size()-1 || ccw (p1, a[i], p2)) {
			while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
				down.pop_back();
			down.push_back (a[i]);
		}
	}
	a.clear();
	for (size_t i=0; i<up.size(); ++i)
		a.push_back (up[i]);
	for (size_t i=down.size()-2; i>0; --i)
		a.push_back (down[i]);
}

int sign(double x) {
    if (fabs(x) < eps2)
        return 0;
    if (x > 0)
        return 1;
    return -1;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m;

    cin >> n >> m;

    vector <pt> red(n), blue(m);
    for (int i = 0; i < n; i++) {
        cin >> red[i].x >> red[i].y;
    }

    for (int i = 0; i < m; i++) {
        cin >> blue[i].x >> blue[i].y;
    }

    if (m == 1) {
        cout << -1 << endl;
        return 0;
    }
    vector <pt> cvx_blue = blue;
    convex_hull(cvx_blue);
    int k = cvx_blue.size();
        
    for (int i = 0; i < n; i++) {
        bool flag = true;
        for (int j = 0; j < k; j++) {
            line hl(cvx_blue[j % k], cvx_blue[(j + 1) % k]);
            if (hl.dist(red[i]) > eps1) {
               flag = false;    
            }
        }

        if (flag) { 
            cout << -1 << endl;
    
            return 0;
        }

    }


    double ans = 0.0;

    for (int i = 0; i < m; i++) {
        vector <pt> new_blue;
        for (int j = 0; j < i; j++) {
            new_blue.pb(blue[j] - blue[i]);
            double d = sqr(new_blue.back().x) + sqr(new_blue.back().y);
            new_blue.back().x /= d;
            new_blue.back().y /= d;
        }

        new_blue.pb(pt(0.0, 0.0));

        for (int j = i + 1; j < m; j++) {
            new_blue.pb(blue[j] - blue[i]);
            double d = sqr(new_blue.back().x) + sqr(new_blue.back().y);
            new_blue.back().x /= d;
            new_blue.back().y /= d;
        }

        vector <pt> new_red;
        for (int j = 0; j < n; j++) {
            new_red.pb(red[j] - blue[i]);
            double d = sqr(new_red.back().x) + sqr(new_red.back().y);
            new_red.back().x /= d;
            new_red.back().y /= d;        
        }

        convex_hull(new_blue);

        int k = new_blue.size();
        int p = new_red.size();

        for (int j = 0; j < k; j++) {
            bool flag = false;
            line hl(new_blue[j], new_blue[(j + 1) % k]);
           
            for (int q = 0; q < p; q++) {
                if (hl.dist(new_red[q]) < eps2)
                    flag = true;            
            }            

            if (flag) {
                if (abs(hl.dist(pt(0.0, 0.0))) < eps2) {
                    cout << -1 << endl;
                    
                    return 0;
                }
    //            cerr << hl.dist(pt(0.0, 0.0)) << endl;
                /*
                if (fabs(hl.dist(pt(0.0, 0.0))) < eps) {
                    cout << -1 << endl;
                    return 0;
                }
                */
                ans = max(ans, 1.0 / abs(hl.dist(pt(0.0, 0.0))));
            }
        }

        for (int q = 0; q < p; q++) {
            for (int j = 0; j < k; j++) {
                line hl(new_red[q], new_blue[j]);
                if (sign(hl.dist(new_blue[(j + 1) % k])) * sign(hl.dist(new_blue[(j + k - 1) % k])) >= 0) {
                    if (abs(hl.dist(pt(0.0, 0.0))) < eps2) {
                        cout << -1 << endl;
                
                        return 0;
                    }

  //                  cerr << hl.dist(pt(0.0, 0.0)) << endl;
                    ans = max(ans, 1.0 / abs(hl.dist(pt(0.0, 0.0))));
                }
            }
        }
    }

    cout.precision(20);
    cout << ans / 2.0 << endl; 

    return 0;
}

Hongcow Masters the Cyclic Shift

Let M denote the total number of characters across all strings.

Consider how long it takes to compute f(L) for a single list.

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.

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.

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.

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.

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).

code

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CyclicShiftsAgainAgain {
    public static int n;
    public static String[] s;
    public static int[] len;
    public static void main (String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out, true);
        n = in.nextInt();
        s = new String[n+1];
        len = new int[n+1];
        s[0] = "";
        len[0] = 0;
        for (int i = 1; i <= n; i++) {
            s[i] = in.next();
            len[i] = len[i-1] + s[i].length();
        }

        int ans = 0;
        int front = 0;
        for (int i = 1; i <= n; i++) {
            while (!isGood(front+1, i)) front++;
            ans += i - front;
        }

        out.println(ans);
        out.close();
        System.exit(0);
    }

    public static boolean isGood(int from, int to) {
        if (from > to) return true;
        int numnodes = len[to] - len[from - 1];
        ArrayList<Integer>[] graph = new ArrayList[numnodes+1];
        for (int i = 0; i <= numnodes; i++) graph[i] = new ArrayList<>();
        for (int startword = from; startword <= to; startword++) {
            graph[numnodes].add(len[startword-1] - len[from-1]);
            StringBuilder sb = new StringBuilder();
            sb.append(s[startword]);
            sb.append("$");
            for (int k = from; k <= to; k++) {
                if (k == startword) continue;
                sb.append(s[k]);
                sb.append("#");
            }
            int[] z = zz(sb.toString().toCharArray());

            int curchar = 0;
            for (int i = 1; i < s[startword].length(); i++) {
                if (z[i] + i >= s[startword].length()) {
                    graph[i + len[startword-1] - len[from -1]].add(z[i] + len[startword-1] - len[from-1]);
                }
            }
            int curword = startword == from ? (from+1) : from;
            for (int i = s[startword].length()+1; i+1 < z.length; i++) {
                if (sb.charAt(i) == '#') {
                    i++;
                    curword++;
                    if (curword == startword) curword++;
                    curchar = 0;
                }

                int curnode = curchar + len[curword-1] - len[from-1];
                if (z[i] + curchar >= s[curword].length()) {
                    if (z[i] == s[startword].length()) {
                        if (curchar != 0) graph[curnode].add(numnodes);
                    } else {
                        graph[curnode].add(z[i] + len[startword-1] - len[from-1]);
                    }
                } else if (z[i] == s[startword].length()) {
                    graph[curnode].add(curnode + z[i]);
                }
                curchar++;
            }

        }
        return isDAG(graph);
    }

    public static int[] zz(char[] let) {
        int N = let.length;
        int[] z = new int[N];
        int L = 0, R = 0;
        for (int i = 1; i < N; i++) {
            if (i > R) {
                L = R = i;
                while (R < N && let[R - L] == let[R])
                    R++;
                z[i] = R - L;
                R--;
            } else {
                int k = i - L;
                if (z[k] < R - i + 1)
                    z[i] = z[k];
                else {
                    L = i;
                    while (R < N && let[R - L] == let[R])
                        R++;
                    z[i] = R - L;
                    R--;
                }
            }
        }
        z[0] = N;
        return z;
    }

    private static boolean isDAG(ArrayList<Integer>[] graph) {
        int n = graph.length;
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) for (int x : graph[i]) indeg[x]++;
        int[] queue = new int[n];
        int front = 0, back = 0, idx = 0;

        for (int i = 0; i < indeg.length; i++)
            if (indeg[i] == 0)
                queue[back++] = i;

        while (front != back) {
            int node = queue[front++];
            for (int next : graph[node]) {
                if (--indeg[next] == 0) {
                    queue[back++] = next;
                }
            }
        }

        return front == n;
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Comments (98)

Show archived | Write comment?

MPeti

8 years ago, # |

+10

For Div1C, why is the size of the dimension "how many of the other" n^2?

→ Reply

dramatico

8 years ago, # ^ |

"First, somehow reduce it so r_i,b_i <= n"

shubham1694

That dimension represents how much of the payment is done by cards and not by tokens. Since for ith card at max (i — 1) payment can be done by cards, hence its size is n^2.

I had the same idea but couldn't get it AC in contest.:)

TimonKnigge

You don't need extra dimensions for that, you can directly derive it from the bitmask of which cards you've already visited (at least, I assume that's what the 2ⁿ represents).

← Rev. 2 →

The amount of payment done in cards depends on the order of the cards also, not just the mask. Eg. if there are 3 cards {(2, 0), (1, 0), (1, 0)}, then :

If order is {1, 2, 3}, then payment done in cards = 1 + 1 = 2
If order is {2, 3, 1}, then payment done in cards = 1 + 2 = 3

Payment for getting a card can be done in 2 ways — token or using previous cards. Each card can assist in payment of all subsequent cards. ith card can be used in payment of n-i subsequent cards. This sum is obviously n^2.

Yeah I don't buy that either. For the following input you ended up with > n² tokens of one color as intermediate value:

ania

+15

For the token R 100 0 at some moment you pay max(100-r,0), where r is the current amount of red tokens collected. Note that it will always be 100-r as r<=4 here. You can transform it to 96+max(4-r,0) which means you buy 96 red tokens at some other moment and change the token description to R 4 0. By doing this kind of transformation to all of the tokens (in any case, not just this example) you can end up with every token price <=n and some additional price to pay separately.

G.E.M.orz

If i transform it to 96+max(4-r,0),i should buy 96 red cards at some other moment,but when i buy 96 red cards,i also have another 96 blue cards.These bule cards can also contribute to the answer,so i doubt how to handle with these 96 blue cards?

My idea is that you can shift the payments to any moment in time (you may be in debt at some point but have to pay it at the end). I would shift all the additions (e.g. this 96 red) to the end and have a total of R and B to add after the dp is done. This seems complicated though, I wonder if the author had something simpler in mind.

haleyk100198

I am not quite convinced on the point you can shift the payment if you can buy it earlier, wouldn't it contributes to the discount caused by owning that card incorrectly?

Edit: I think I've got it

Nezzar

-11

For Div1D, if any nice circle of radius r does not touch any blue point, I assumed there exist a circle of radius r which has center on one of the red point, is it wrong? since I'm getting wa for this idea :(

adityagupta1089

-24

Too bad I solved Div2D but I did not count properly the number of indexes which I was asking as a question.

Whistle

-6

wow, this Editorial is even faster than my Internet speed

slow.coder

the description of Div2 B may be hard to many contestants.

dummkopf

+47

MinakoKojima

How to use Binary Search to solve D? Anyone could explain it in more detail?

Lewin

First, the circle has to touch some point red or blue.

Try each of these points, and call this the center point.

Now, we can rotate the circle about the center point. Notice that every other point forms an interval on the angles, so this reduces to a pretty standard problem. Note you count the center point as part of the condition (i.e. when we rotate around a red point, we don't necessarily have to include a different red point).

Sangar

← Rev. 4 →

-10

For Div2 Problem B Hangcow And Puzzle This is also a valid test case

5 5

X X X X X

. . . . .

because final rectangle made just by shifting second rectangle one unit down and five units left both will fit together (without rotating or overlap or picking up some part)

_index

+11

It is guaranteed that the puzzle pieces are one 4-connected piece.

So sir you mean such a test case is not possible ????????

BaturaDima

I had a problem with understanding it too.

After reading editorial I've concluded that need binary search by angle too :)

MagicWand

← Rev. 3 →

in Div2B i can't understand why this is wrong ! as it's mentioned in the problem statement that i'm allowed to move any piece so if i moved the bottom left piece 3 times

i can get this

.X and then i can make a rectangle ,, what is the thing that i misunderstood ?

Ashishgup

I made the same mistake because of the ambiguity of the question. The pieces (or the Xs) are all connected together (in one 4-connected piece). So you either move them together as a whole, or don't move any of them.

barun511

The whole thing is a piece, you cannot move individual parts of the piece.

ista2000

Editorial posted 13 hours ago? :/

__stdcall

I am also curious about this.

RedNextCentury

+12

It was saved as a draft 13 hours ago

justadlet

+13

This contest is excellent! Thank you authors(Lewin) and MikeMirzayanov!!!

My friends and I have a better solution which is easier understood for Div2E/Div1C. We can make the problem reversed. The solution is also bitmask dp. We can start from the state (0,0), which means we cost no red tokens and blue tokens at first. And then we can buy one cards each time, whose cost is ( max( red_cost[i]-red_left, 0 ), max( blue_cost[i]-blue_left, 0 ) ), while i is the card we are ready to buy and red_left means how many red cards we haven't bought except i. We say a state (a,b) is better than another state (a2,b2) when max(a,b) < max(a2,b2). But my program has a little bug and I could not find it until 2 minutes after the contest. QAQ.

sam29

In DIV2B why the answer for the below test case would be NO.

2 5

.XXX.

.X.X.

We can move the X at (2,2) to (1,1) and the X at (2,4) to (1,5). So in this way we can form a rectangle. But the answer for the above test case is NO. Why ???

i have the same problem ! i can't get what in the statement that make the answer for this testcase is no !

Seif

You can only move all Xs (all the component) to any direction.

AGHORii

I think the whole structure can be moved not a single part
XXX
X.X
We can move this whole structure not a single X.
I am not sure though. But I hacked a solution using the similar test case.
UPD : My solution for B failed system test. So, at this moment I have no clue what the fuck is the problem with problem B :(

LawlietYagami

I came up with exact same thing and passed pretest. Few mins later.. Unfortunately your solution for B is Hacked :'(

-osdajigu-

The idea of the problem is to check if you can make a rectangle with 2 exactly pieces as given in the input. You are allowed to move the whole piece, not part of the piece. So if there are any way to make a rectangle with the 2 exactly pieces, then you have print "YES", otherwise "NO".

Mirlan

Can someone help me about problem D. My ten solutions dont work on pretest 1, but i have been using any flushes and endl's. Plz explain me my fault :http://mirror.codeforces.com/contest/745/submission/23071323.

Lucas97

Maybe it is because you only need to write fflush(stdout) after you write a complete line instead of writing it after every number on your list.

i had written every variant... Idk.

sparks

Div2 D is such a fun problem :D

geniucos

In div1E, I've tried to do almost the same thing. But I don't know how to "check the match of the suffix with the end." So we start from a suffix adding words and going into new suffixes and achieve different suffixes. But we are not looking for a cycle in this graph, we are looking for an achievable suffix that, after adding at its end the prefix of the initial state, could get to a string that can be partitioned into more strings. So how do we do that? Wouldn't it be M^2*N?(fixing an initial state and then moving through the edges and checking whether we could have achieved to certain nodes that could be combined with the prefix of this initial state)

I'll add more description above, but as a quick reply.

The part you're quoting is more for creating the edges rather than checking the condition of the problem.

What you're saying is correct, but you have to notice that "need to spell out suffix starting at position i" and "already spelled out letters up to position i" are the same state, so it is sufficient to check if we have a cycle in our graph.

Ohh... Yeah, I think I got it now. So close:))Anyway, very nice problemset:)Congrats!

orange4glace

Could anyone explain Div2.D more detail please?

rachitiitr

For row i, you need to cover all all j!=i. This means for some j!=i, there is a question where we did not take i but j was present. So write i and j in their binary expression(<=10 bits are needed), there will exist a bit where they differ. Acc to editorial solution, you would have asked a question where either i was present or either j. This is exactly what we needed.

hongyan

When the problem can be submit at the problem set? I want to try my solution for Div2D. :)

spk

problem statement of div2B was really bad,many people misunderstood the question and got hacked.

sukhad.anand

In Div 2 b

if the input is X.X.X

then it should print yes as moving one piece to one step right would make a rectangle. But according to editorial as count =3 the output should be no. can anyone explain where am i wrong?

I_Love_Panaetisme

Has anybody solved D2D/D1B using the "parallelization solution"?

snacache

I don't know if my solution was the expected "parallelization" solution.

My solution is:

First, work with a matrix of dimension 2^M where 2^M is the smallest power of two that is bigger or equal than N.

Now, in order to guess the matrix, I make questions over the upper triangular and lower triangular matrix.

For example, given n = 8

$\text{[math]}$

Every entry of this matrix represent a question. Every entry that has the same value is asked in the same question (except the diagonal). The same is done with the lower triangular

Now, using this method only log₂(n) questions are needed for every triangular. If n = 1000, then 20 questions will be made!

Yes, this is the intended way of parallelization that I was thinking of.

_mactep

I used almost the same approach, and came up with asking questions like:

1, 3, 5, 7, 9...
2, 4, 6, 8, 10...
1, 2, 5, 6, 9...
3, 4, 7, 8, 11...
1, 2, 3, 4, 9...
5, 6, 7, 8, 13...

But its failing on test 7 don't know why :(

DysKode

i made the same thing and it worked

bhishma

How are you bounding the number of questions by 2 * log₂(n)

APIV

I think something is wrong here one code with 2 different verdict

23067626 hack

23072618 accept

EDIT : PS for more detail see my blog

ITDOI

My solution on div 1 c Number of final pairs isnt exceed 16^4 Also for every a1<a2 and b1<b2 we can throw out this pair So number of final pair isn't exceed 16^2 so for every subset of cards save pairs we can get from these cards :)

adamant

We can notice that we only need to check lines on the convex hull of all blue points.

How to check them? And why we shouldn't check tangents from red points to this polygon?

To check that if a line has a red point on the opposite side, you can find the convex hull of all points, and only blue-blue edges that aren't on the entire convex hull will be covered by a red point, so you only need to check those. Checking a line is checking the distance from the line to our center point (the radius of the circle is equal to the reciprocal of the distance from the center point to the line).

Also, an easier way to implement, but harder to notice is to see that the sizes of all the convex hulls across all inversions will be linear (the intuition is that the points on the convex hull after inversion are the ones that are closest to the center point). So, you can also just do this by brute force also.

Also, an easier way to implement, but harder to notice is to see that the sizes of all the convex hulls across all inversions will be linear (the intuition is that the points on the convex hull after inversion are the ones that are closest to the center point)

Wow, can you elaborate on this?

I realize I misspoke in an earlier post, you do need to check those tangents, but what I said to solve the original problem is still relevant (i.e. you can either find the convex hull of all points or you make this observation and do it by brute force).

I don't have a formal proof for this, but some intuition is to look at the delaunay triangulation. After inverting about a point P, only points that are connected to P in the delaunay triangulation will lie on the convex hull, so this shows that the sum of all convex hull sizes will be linear.

Mindstorm

← Rev. 5 →

I think that following solution to Div2B is really simple and easy to code. All we have to do is check every "square" (four fields). For every (1 ≤ i < n, 1 ≤ j < m) we count how many letters 'X' are in the square formed by a[i][j], a[i][j + 1], a[i + 1][j], a[i + 1][j + 1]. If there is at least one "square" with number of 'X's equal to 3 then the answer is NO, if not the answer is YES.

Gnay_Oahnauhz

For the div1C/div2E solution of setter, there is int ans = base + n; Why should we add an n there? I think base should be enough (which is incorrect).

gongy

It takes a day to buy something. So if you buy n things there are n extra days.

I see, I was confused by the number of tokens and failed to consider the number turns. Thanks.

future_loops

For div2 C / div1 A I cant see the testcases and i failed at test 15, can someone tell whats wrong in this code .

here is my code https://codeshare.io/21j0z5

maybe problem in size of array as n or n+1 0 indexed or 1 indexed

No, I found the problem, thanks anyway.

grevyarlesz

had the same problem. thanks :)

Arpa

Hi !

The simplest solution for 744C - Hongcow Buys a Deck of Cards is here : 23076523. Because the number of dp states are O(2ⁿ·n²), this code workes in $\text{[math]}$ ( $\text{[math]}$ because of map).

rawr

Div 2C, what should be the output for this test case?

I saw an ac code produced 8 as output, while another ac code produced 7 as output.

Which is the correct one? Is the test case valid? I tried to solve it manually and got 7 as output.

Saat

It should be 8. You can put edges 1,2,3,4,5-10 and edges 7-8, 8-9, 7-9

Oh I see. I forgot to consider completing the other government components. Thanks!

gerw

In Div1E, This means we already spelled out the prefix, and still need to spell out the suffix. What does this sentence mean? And what's the condition of connecting two nodes to each other?

wucebrayne

I am having problem understanding Div 2D. Could someone please suggest more problems like it? What is the topic that it falls under?

harshilgoel

I tried to solve Div2-D by first asking the first half of the elements, and then the second half. This would leave us with two smaller recursive problems which could be solved together as they don't intersect. Hence o(n) = 2 + o(n/2).

Here is an ac using this solution http://mirror.codeforces.com/contest/744/submission/23080098

YuukaKazami

I think your binary search for Div1D runs in time O(n^2 log n log W)? Probably there can be some hard cases to make it TLE....

During the contest I basically implemented the same algorithm, but with a random_shuffle among blue points and red points... That can bring the complexity down to something like O(n^2 log n + n log n log W)...

Philipsweng

But if you do binary search individually for each point,the answer may not be right since it's no longer monotonic,did I just miss something?

The very key thing of this to work is that you should also include the red points and calculate their individual answers first...

After that, suppose the best radius for touching those red points is R, you can somehow prove that for the remaining blue points, either its individual answer is smaller than R, or it is monotonic after R...

M.A.H.M.O.O.D

I'm sorry but the solution for Div 1 C/ Div 2 E has stumped me...Could someone please elaborate I've tried reading a a few codes but it was to no avail...

UPD: I got it now if someone wants to know how to solve it my submission might help (I've filled it with comments to help make things easier)

C++ code:23346668.

WZJRJ28

Div.1 C could be solved by Simulated Annealing....

punetharomil

If anyone has tried DIV2- C Build a Nation using Union-Find algo, please comment. Im stuck with the understanding using this implementation.

SirNickolas

I did. Here's the code: 23060103.

While building the DSU, we need to update components' sizes and count of edges in them. Then, turn each component into a clique. Find the largest component that contains a capital. Finally, merge it with components that do not contain a capital. Be sure to perform the final step only once for each component.

Thanks. Pretty neat coding style. I messed up the entire DSU code for computing size and got lost. Im still not sure where my code is failing though.

itu

For Div1 E, I don't quite understand. It seems you're connecting suffix u of word a and suffix v of word b whenever there's a word c such that c completes word a and goes through a prefix of word b up to suffix v. Is this right? If so, why are there "at most N edges" for each suffix? I would think that a word can lead a suffix to different ones.

Consider for example words:

aaaaa aaaa aaa

and a suffix aaa of aaaaa. Then, word aaaa takes you to prefix aa, which is a prefix of every word and so is represented by three different suffix nodes. What to do with this?

EDIT: It seems AC solutions have assumed that being at a suffix of word A and then using word B necessarily takes you to a suffix of word B. Why is this?

EDIT2: I understand now. The edge isn't using a complete word to jump, it's deciding to put that word after the current one, and using the current suffix as a prefix to it.

When will the test cases be made public... Or is it just me who can't view the test cases?

suraj021

How do we count the number of edges in a graph component? Is there any optimal way ?

pjag

If you know the vertices that belong to the component, it is enough to take the number of neighbors for each vertex, add them up, and halve the result (every edge was counted twice, once for every endpoint).

Then I will have to use extra memory to store vertices of each component, and then sum the indegrees. Will it not be too costly?

No extra memory is needed, you can compute the sum during the traversal, something similar to this:

sum = 0
dfs(v):
  sum = sum + degree(v)
  [dfs stuff]

And even if you did have to store vertices separately, it is not that big of a cost.

Did I get it right?

Suppose there are 3 cc's of a graph. Each time I run dfs on each component, sum is initialized to zero.

for( int i= 0; i< V; ++i ){
   if( !visited[i] ){
      sum= 0;
      dfs( i );
      // num sum/2 is the number of edges in the this graph component
   }
}

Looks all right.

hiddentesla

can somebody please explain easily why asking 2 questions for each position works in Div2D? i tried it by hand and it works, but i want to understand it...

As each position must have different bitmask representation, by asking 2 questions for each position, every two integers are guaranteed not to be grouped into the same question for at least once, therefore avoiding the query being diluted by the [0] at position i on each row.

ManiSadati

Can anyone help me find why 23268578 got WA for Div1 C ?

yolob2112

Regarding div2c,

stuck on testcase 15 23256857,any ideas?

also is there a difference between a clique and completely connected component for a given graph?

dam_sehgal

Got It Your solution is failing for this test case. It's answer is 18
10 6 2
2 7
1 2
2 3
5 6
7 8
8 9
9 10

YashPratapSingh

Can anyone please give the code for DIV 2 Problem C (Hongcow builds a nation) in C++?

You can see all solutions here
Here is my C++ AC solution 23417630

I_love_Captain_America

In div2 E Hongcow buys a deck of cards, is it possible to use a map instead of static array, then we can solve without the first optimization. Has anyone done that?