Official

C - Connect 6 Editorial by en_translator


First of all, the grid contains six or more consecutive squares painted black aligned either vertically, horizontally, or diagonally, if and only if there exist six consecutive squares aligned either vertically, horizontally, or diagonally, such that all of these six squares are painted black.
Next, when can we make the grid contain six or more consecutive squares painted black aligned either vertically, horizontally, or diagonally by painting at most two squares black? It is when there exist six consecutive squares aligned either vertically, horizontally, or diagonally, such that four or more of them are painted black. If there are such six squares, then we can fulfill the condition by painting black the squares that are not yet painted black. Conversely, if there aren’t, then it cannot be achieved no matter which two squares are painted. This is obvious by consider painting white at most two of the squares painted black in the grid satisfying the condition.

Here, how many groups of six consecutive squares in each directions are there? The number of vertical ones is \((N-5)\) for each column for a sum of \(N(N-5)\); the number of horizontal ones is \(N(N-5)\), which can be understood by swapping rows and columns. For diagonal ones, there are \((N-5)^2\) ways to choose \(6\)-by-\(6\) subgrid, each of which contains two diagonals. Therefore, the total number of squares required to inspect is at most about \(6\times\bigl\{ 2N(N-5)+2(N-5)^2 \bigr\}<24N^2\). Since \(N\leq 1000\), brute-forcing against them is still fast enough. Therefore, the problem has been solved.

When implementing, be careful of the range of loops and squares, and the pattern in which \(6\) consecutive squares can be made only by painted outside the grid (like the figure below).

....#.
...#..
..#...
.#....
#.....
......

Sample code in c++:

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)


int main(void) {
	int n, cnt;
	bool ans = false;
	vector<string>a;
	string str;

	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> str;
		a.push_back(str);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if ((i + 5) < n) {
				cnt = 0;
				for (int k = 0; k < 6; k++)if (a[i + k][j] == '#')cnt++;
				if (cnt >= 4)ans = true;
			}
			if ((j + 5) < n) {
				cnt = 0;
				for (int k = 0; k < 6; k++)if (a[i][j + k] == '#')cnt++;
				if (cnt >= 4)ans = true;
			}
			if (((i + 5) < n) && ((j + 5) < n)) {
				cnt = 0;
				for (int k = 0; k < 6; k++)if (a[i + k][j + k] == '#')cnt++;
				if (cnt >= 4)ans = true;
			}
			if ((0 <= (i - 5)) && ((j + 5) < n)) {
				cnt = 0;
				for (int k = 0; k < 6; k++)if (a[i - k][j + k] == '#')cnt++;
				if (cnt >= 4)ans = true;
			}
		}
	}

	if (ans)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

By the way, if \(6\) (the desired number of consecutive squares) is some general \(K\), this solution costs \( O(KN^2)\) time, but we can use cumulative-sum like technique to count the number of # in each direction to solve it in a total of \(O(N^2)\) time independent of \(K\).

posted:
last update: