People with atcoder rating of greater than or equal to 2000 see the "New Editorial" button on ABC's editorial page. Clicking on it opens a page to publish user editorials.

How to solve G?

The problem statement is equivalent to placing $$$min(R,B)$$$ 2x1-Dominoes on $$$A$$$ and adding the covered $$$A_i$$$ s. But that's as far as I could get...

I am so depressed with a C ... It made me feel incompetent :(

For me G was easier than C , as it required a good amount of code and had much less points than C ( Unluckily I missed G as I had value of infinity as 998245353 rather than 10^9+7)

I think my answer is wrong for problem C, but It has been accepted.

Those test cases are giving me : Yes.

3
. # .
# . .
. . .
. . #
# . .
. . .

5
. . . . .
. . . . .
. . # . .
. . # # #
. . # . .
. . . . .
. . . . .
. . . # #
. . . # #
. . . # .

Am I wrong ?

Most of the people in the first page of the standings are getting "Yes" you can check if you want : https://atcoder.jp/contests/abc218/submissions/25773980

check out the editorials

For C, First, if only 90 degree rotation is considered, there may be only 4 patterns s at most. Then consider the translation. It can be found that you only need to see which of the four patterns mentioned above can be translated to completely match t. Specifically, we list the positions of all characters # in S and T in sequence, and then compare them one by one. Let set pattern $$$S$$$ have a amount of $$$c_1$$$ #, the position of the $$$i$$$-th # is $$$(x_{0,i},y_{0,i})$$$; pattern $$$T$$$ have a amount of $$$c_2$$$ #, the position of the $$$i$$$-th # is $$$(x_{1,i},y_{1,i})$$$, and then we just need to find out whether the following conditions are met:

• $$$\forall i\in[2,n],x_{0,i}-x_{1,i}=x_{0,1}-x_{1,1}$$$
• $$$\forall i\in[2,n],y_{0,i}-y_{1,i}=y_{0,1}-y_{1,1}$$$
• $$$c_1=c_2$$$

Just follow this implemention. It may be a bit hard.

namespace Solution {
	const int N = 207;
	int n, cnt1, cnt2; char a[N][N], b[N][N], a1[N][N], a2[N][N], a3[N][N];
	struct dist {int x, y;}dis[N * N];
	struct node {int x, y;}p[2][N * N];
	
	ib solve(char t1[N][N], char t2[N][N]) {
		F(int, i, 1, cnt1) p[0][i] = (node){0, 0};
		F(int, i, 1, cnt2) p[1][i] = (node){0, 0};
		F(int, i, 1, max(cnt1, cnt2)) dis[i] = (dist){0, 0};
		cnt1 = cnt2 = 0;
		F(int, i, 1, n) F(int, j, 1, n) {
			if(t1[i][j] == '#') p[0][++cnt1] = (node){i, j};
			if(t2[i][j] == '#') p[1][++cnt2] = (node){i, j};
		}
		if(cnt1 != cnt2) return 0;
		F(int, i, 1, cnt1) dis[i] = (dist){p[0][i].x - p[1][i].x, p[0][i].y - p[1][i].y};
		F(int, i, 2, cnt1) if(dis[i].x != dis[1].x || dis[i].y != dis[1].y) return 0;
		return 1;
	}
	
	iv Main() {
		read(n);
		F(int, i, 1, n) scanf("%s", a[i] + 1);
		F(int, i, 1, n) scanf("%s", b[i] + 1);
		int precnt1 = 0, precnt2 = 0;
		F(int, i, 1, n) F(int, j, 1, n) {
			if(a[i][j] == '#') precnt1++;
			if(b[i][j] == '#') precnt2++;
		}
		if(precnt1 != precnt2) return No, void();
		F(int, i, 1, n) F(int, j, 1, n) a1[i][j] = a[n - j + 1][i];
		F(int, i, 1, n) F(int, j, 1, n) a2[i][j] = a[j][n - i + 1];
		F(int, i, 1, n) F(int, j, 1, n) a3[i][j] = a1[n - j + 1][i];
//		F(int, i, 1, n) {F(int, j, 1, n) putchar(a3[i][j]); puts("");}
		if(solve(a, b) || solve(a1, b) || solve(a2, b) || solve(a3, b)) return Yes, void();
		return No, void();
	}
}

For D, we only need to enumerate two points, not four. Let the two points we enumerated be $$$i$$$ and $$$j$$$, and then you just need to see whether the two points $$$(x_i, y_j)$$$ and $$$(x_j,y_i)$$$ exist. Be careful not to repeat the enumeration.

namespace Solution {
	int n, ans, in[2007];
	struct node {int x, y;}a[2007];
	map<pii, int> vis;
	map<pair<int, pair<int, pii> > , int> v2;
	
	iv Main() {
		read(n);
		F(int, i, 1, n) read(a[i].x, a[i].y), vis[mp(a[i].x, a[i].y)] = i;
		F(int, i, 1, n) F(int, j, i + 1, n) {
			int id1 = vis[mp(a[i].x, a[i].y)], id2 = vis[mp(a[j].x, a[j].y)], id3 = vis[mp(a[i].x, a[j].y)], id4 = vis[mp(a[j].x, a[i].y)];
			if(id1 && id2 && id3 && id4 && !(!(id1 ^ id2) || !(id1 ^ id3) || !(id1 ^ id4) || !(id2 ^ id3) || !(id2 ^ id4) || !(id3 ^ id4))) {
				int id[5] = {0, id1, id2, id3, id4};
				sort(id + 1, id + 5);
				if(!v2[mp(id[1], mp(id[2], mp(id[3], id[4])))]) ans++, v2[mp(id[1], mp(id[2], mp(id[3], id[4])))] = 1;
			}
		}
		write(ans);
		return;
	}
}

Just find the minimum spanning tree for E(be careful while dealing with loops and multiple edges), your answer will be $$$max(0,total\ cost-cost\ of\ MST)$$$.

I got 4 penalty's because I removed all edges even those which had negative weight. I guess that's your error too. Sort edges in non-decreasing order of weights and form a graph. If the edge forms a cycle and doesn't have weight <= 0, remove it, else add to the graph. Final answer is (Total sum of edge weights — sum of weights of included edges of graph).

Submission

Kinda, you can bruteforce all edges inside the shortest path (at most $$$N-1$$$), for all other edges the answer remains the same.

Yeah, it's kinda brute force.

ngl most of the in-contest solvers who use convexity often rely on proof by AC :P

I saw submissions using priority queue also where they are greedily converting to red which gives maximum profit. Btw can you please elaborate your solution. Thanks

I always thought that it is impossible to make $$$(max, +)$$$ convolution faster than $$$ O(n \sqrt{n} ) $$$. What is the complexity of your solution?

True , I too think I have seen something very similar to this somewhere.

Do you know how to solve the question for your constraints ($$$N, M \le 2 \cdot 10^5$$$)?

Link

I solved this problem few days back. I copied my code to find the edges that will always be in the shortest path.

Well, the constraint in the CodeChef problem is N≤10⁵, which is 50 times as more as in Problem D. (+ input several testcases if you haven't)

Thats because the quantity of tasks has also increased i Guess..

i got No on both TC you mentioned

I think it is because your test cases have spaces in between.

The problem statement gives the inputs without spaces.

If you remove the spaces so it looks like this, your problem should be solved:

3
.#.
#..
...
..#
#..
...

5
.....
.....
..#..
..###
..#..
.....
.....
...##
...##
...#.

I modified your code and here is the submission: https://atcoder.jp/contests/abc218/submissions/25796147

Basically, need to change 2 things: 1. remove Abs() 2. Use diffx and diffy in parallel instead of diff.

Thanks for the info , I was also having the same error but as I was unable to figure out the reason I switched code from Multiset to set of pair.