A-F are pretty cool, how to solve G?

For E, I already used union-find and summing up the minimum cost for each component. Still WA.

Quite cool of the author allowing sqrt-decomp to pass F

In problem E i stored the graph as undirected one and broke the cycles into 2 cases ,the vertices which belong purely to a cycle and the others which have a cycle and a chain (for these i rand dfs from vertices whose adjoint size was 1 until i found a vertice with adjoint size 3) . But it gave WA. Could somebody point out why the approach is wrong.

code

On the way from reading C to understanding C I somewhere lost meaning of h[],w[], to be maximum posible value of row/col, instead of exact value. Then its hard to solve.

normalize discussing ABCD's of abc contest (_/_)

I use segment tree + lazy propagation for arithmetic progression for problem F. But I got wrong answer, can someone point out where I might be making the mistake?

My submission

Thank you for providing such a cool contest.

Problem D involves a wonderful trick. By implementing a[L]++ and a[R]--, and then calculating the prefix sum, we could find out all the intervals that have been covered.

Problem E is about graph with directed edges, and one should be familiar with topological sorting and also how to find out the cycle.

Problem F needs some mathematics to deduce the expression of Dx, and one should also be very careful of integer-overflow.

As for Problem G, at first, I was scared by the super huge N. After I found out the state transition of dp, then I realized that it could be reduced to logN by using Fast-Exponentiation-Algorithm (matrix version). But my definition of dp state is somehow a little bit complicated and didn't finish codes before contest ends.

The easiest and worst sol for problem C :)

#include <bits/stdc++.h>
using namespace std;

int main() {
	int h1, h2, h3, w1, w2, w3, ans = 0;
	cin >> h1 >> h2 >> h3 >> w1 >> w2 >> w3;
	vector<vector<int> > a(3, vector<int>(3));
	for (a[0][0] = 1; a[0][0] <= 30; a[0][0]++)
	for (a[0][2] = 1; a[0][2] <= 30; a[0][2]++)
	for (a[2][0] = 1; a[2][0] <= 30; a[2][0]++)
	for (a[2][2] = 1; a[2][2] <= 30; a[2][2]++) {
		a[0][1] = h1 - a[0][0] - a[0][2];
		a[1][0] = w1 - a[0][0] - a[2][0];
		a[1][2] = w3 - a[0][2] - a[2][2];
		a[1][1] = h2 - a[1][0] - a[1][2];
		a[2][1] = h3 - a[2][0] - a[2][2];
		if (a[0][0] + a[0][1] + a[0][2] == h1)
		if (a[1][0] + a[1][1] + a[1][2] == h2)
		if (a[2][0] + a[2][1] + a[2][2] == h3)
		if (a[0][0] + a[1][0] + a[2][0] == w1)
		if (a[0][1] + a[1][1] + a[2][1] == w2)
		if (a[0][2] + a[1][2] + a[2][2] == w3)
		if (a[0][0] > 0 && a[0][1] > 0 && a[0][2] > 0)
		if (a[1][0] > 0 && a[1][1] > 0 && a[1][2] > 0)
		if (a[2][0] > 0 && a[2][1] > 0 && a[2][2] > 0) ans++;
	}
	cout << ans;
	return 0;
}

It got Accept