652A - Габриел и гусеница

The problem was suggested by unprost.

Let's consider three cases.

1. h₁ + 8a ≥ h₂ — in this case the caterpillar will get the apple on the same day, so the answer is 0.

2. The first condition is false and a > b — in this case the caterpillar will never get the apple, because it can't do that on the first day and after each night it will be lower than one day before.

3. If the first two conditions are false easy to see that the answer equals to .

int h1, h2;
int a, b;

bool read() {
	return !!(cin >> h1 >> h2 >> a >> b);
}

void solve() {
	if (h1 + 8 * a >= h2)
		puts("0");
	else if (a > b) {
		int num = h2 - h1 - 8 * a, den = 12 * (a - b);
		cout << (num + den - 1) / den << endl;
	} else
		puts("-1");
}

Also this problem can be solved by simple modelling, because the heights and speeds are small.

Complexity: O(1).

652B - z-сортировка

The problem was suggested by Smaug.

Easy to see that we can z-sort any array a. Let be the number of even positions in a. We can assign to those positions k maximal elements and distribute other n - k elements to odd positions. Obviously the resulting array is z-sorted.

const int N = 1010;

int n, a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	return true;
}

int ans[N];

void solve() {
	sort(a, a + n);

	int p = 0, q = n - 1;
	forn(i, n)
		if (i & 1) ans[i] = a[q--];
		else ans[i] = a[p++];
	assert(q + 1 == p);

	forn(i, n) {
		if (i) putchar(' ');
		printf("%d", ans[i]);
	}
	puts("");
}

Complexity: O(nlogn).

652C - Враждебные пары

This is one of the problems suggested by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.

Let's precompute for each value x its position in permutation pos_x. It's easy to do in linear time. Consider some foe pair (a, b) (we may assume pos_a < pos_b). Let's store for each value a the leftmost position pos_b such that (a, b) is a foe pair. Denote that value as z_a. Now let's iterate over the array a from right to left and maintain the position rg of the maximal correct interval with the left end in the current position lf. To maintain the value rg we should simply take the minimum with the value z[lf]: rg = min(rg, z[lf]). And finally we should increment the answer by the value rg - lf + 1.

const int N = 300300;

int n, m;
int p[N];
pt b[N];

bool read() {
	if (!(cin >> n >> m)) return false;
	forn(i, n) {
		assert(scanf("%d", &p[i]) == 1);
		p[i]--;
	}
	forn(i, m) {
		int x, y;
		assert(scanf("%d%d", &x, &y) == 2);
		x--, y--;
		b[i] = pt(x, y);
	}
	return true;
}

int pos[N];
vector<int> z[N];

void solve() {
	forn(i, n) pos[p[i]] = i;
	forn(i, n) z[i].clear();
	forn(i, m) {
		int x = pos[b[i].x], y = pos[b[i].y];
		if (x > y) swap(x, y);
		z[x].pb(y);
	}

	li ans = 0;
	int rg = n;
	nfor(i, n) {
		forn(j, sz(z[i])) rg = min(rg, z[i][j]);
		ans += rg - i;
	}
	cout << ans << endl;
}

Complexity: O(n).

652D - Вложенные отрезки

The problem was suggested by Alexey Dergunov dalex.

This problem is a standard two-dimensional problem that can be solved with one-dimensional data structure. In the same way a lot of other problems can be solved (for example the of finding the maximal weighted chain of points so that both coordinates of each point are greater than the coordinates of the predecessing point). Rewrite the problem formally: for each i we should count the number of indices j so that the following conditions are hold: a_i < a_j and b_j < a_j. Let's sort all segments by the left ends from right to left and maintain some data structure (Fenwick tree will be the best choice) with the right ends of the processed segments. To calculate the answer for the current segment we should simple take the prefix sum for the right end of the current segment.

So the condition a_i < a_j is hold by sorting and iterating over the segments from the right to the left (the first dimension of the problem). The condition b_j < b_j is hold by taking the prefix sum in data structure (the second dimension).

const int N = 1200300;

int n;
pair<pti, int> a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(scanf("%d%d", &a[i].x.x, &a[i].x.y) == 2), a[i].y = i;
	return true;
}

int t[N];
vector<int> ys;

inline void inc(int i, int val) {
	for ( ; i < sz(ys); i |= i + 1)
		t[i] += val;
}

inline int sum(int i) {
	int ans = 0;
	for ( ; i >= 0; i = (i & (i + 1)) - 1)
		ans += t[i];
	return ans;
}

int ans[N];

void solve() {
	ys.clear();
	forn(i, n) ys.pb(a[i].x.y);
	sort(all(ys));
	ys.erase(unique(all(ys)), ys.end());
	forn(i, sz(ys)) t[i] = 0;

	sort(a, a + n);
	nfor(i, n) {
		int idx = int(lower_bound(all(ys), a[i].x.y) - ys.begin());
		ans[a[i].y] = sum(idx);
		inc(idx, +1);
	}

	forn(i, n) printf("%dn", ans[i]);
}

Complexity: O(nlogn).

652E - В погоне за артефактами

The problem was suggested by Alexey Dergunov dalex.

Edge biconnected component in an undirected graph is a maximal by inclusion set of vertices so that there are two edge disjoint paths between any pair of vertices. Consider the graph with biconnected components as vertices. Easy to see that it's a tree (if it contains some cycle then the whole cycle is a biconnected component). All edges are destroying when we passing over them so we can't returnto the same vertex (in the tree) after leaving it by some edge.

Consider the biconncted components that contains the vertices a and b. Let's denote them A and B. Statement: the answer is YES if and only if on the path in the tree from the vertex A to the vertex B there are an edge with an artifact or there are a biconnected component that contains some edge with an artifact. Easy to see that the statement is true: if there are such edge then we can pass over it in the tree on the path from A to B or we can pass over it in biconnected component. The converse also easy to check.

Here is one of the ways to find edge biconnected components:

1. Let's orient all edges to direction that depth first search passed it for the first time.

2. Let's find in new directed graph strongly connected components.

Statement: the strongly connected components in the new graph coincide with the biconnected components in old undirected graph.

Also you can notice that the edges in tree is the bridges of the graph (bridges in terms of graph theory). So you can simply find the edges in the graph.

forn(i, sz(g2[v])) {
    int to = g2[v][i];
    if (to == p) continue;
    if (dfs3(to, v, t, ans)) {
       ans |= good[v];
       ans |= w2[v][i];
       return true;
    }
}
return false;

u++, c = 0;
forn(i, sz) if (used[perm[i]] != u) dfs2(perm[i]), c++;

forn(i, c) good[i] = false;

forn(i, c) {
    g2[i].clear();
    w2[i].clear();
}
forn(i, n)
    forn(j, sz(g1[i])) {
       int x = comp[i], y = comp[g1[i][j]];
       if (x != y) {
         g2[x].pb(y);
         w2[x].pb(w[i][j]);
       } else if (w[i][j]) good[x] = true;
    }

n = c;
a = comp[a], b = comp[b];

bool ans = good[a];
assert(dfs3(a, -1, b, ans));
puts(ans ? "YES" : "NO");

Complexity: O(n + m).