PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: NaOH_Frog
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
2384
PREREQUISITES:
None
PROBLEM:
Given N, find an N\times N grid containing the integers 0 to (N-1) and a cycle in this grid such that:
- Every row and every column of the grid forms a permutation of \{0, 1, 2, \ldots, N-1\}
- The cycle visits every cell of the grid exactly once; and
- When starting from (0, 0) and making x moves along the cycle, the integer in the resulting cell is (x\bmod N)
EXPLANATION:
When N is odd, no solution exists.
Proof
Let’s forget all the other conditions: when N is odd, we can’t even find a cycle that visits every cell exactly once!
To see why, color the grid black and white in a chessboard pattern (that is, adjacent cells have different colors).
Without loss of generality, let’s say that cell (0, 0) is colored white.
Since adjacent cells have different colors, making a single move changes the color you’re standing on.
This means, when starting from (0, 0):
- After an even number of moves, you’ll be on a white cell.
- After an odd number of moves, you’ll be on a black cell.
After exactly N^2 moves, we want to end up back at (0, 0).
If N is odd, N^2 is also odd, meaning we’re at a black square after N^2 moves; certainly we can’t be at (0, 0) since it’s colored white.
This contradiction shows that no solution exists when N is odd.
Now, we only have to solve for even N.
Notice that the only thing that really matters is the cycle visiting every cell: once this is fixed, the values in each cell are also fixed; and that also determines whether each row/column forms a permutation or not.
So, we can focus on only finding a “good” cycle.
Subtask 1 can be solved by directly working out a solution on paper, because you only need separate solutions for N = 2, 4, 6, 8, 10 (of which N = 2 is solved in the sample already).
Subtask 2 can be solved by the following general construction:
- Start at (0, 0), and move rightwards as much as possible.
That is, (0, 0) \to (0, 1) \to (0, 2) \to\ldots\to (0, N-1) - Then, move downwards as much as possible.
That is, (0, N-1) \to (1, N-1) \to (2, N-1) \to\ldots\to (N-1, N-1) - Next, move one step left, then upwards as much as possible
(N-1, N-1) \to (N-1, N-2) \to (N-2, N-2) \to (N-3, N-2)\ldots\to (1, N-2) - Then, again move one step left, then downwards till you hit (N-1, N-3).
Continually repeat this “snaking” process of moving upwards and downwards, till you reach (1, 0) at which point you’re done.
This can be visualized as follows, for N = 6:
Let’s prove that this does indeed work.
Proof
First, it’s easy to see that the path we constructed does visit all cells exactly once and ends up back at (0, 0), because N is even.
We only need to show that each row and column forms a permutation.
- The first row is obviously a permutation.
- Now, consider some row R, where 0 \lt R \lt N. Let’s look at when we visit this row.
- The first time we visit it is when moving downwards in the last column. This gives row R the integer R-1.
- The second time is when moving upwards in column N-2. These visits are separated by exactly 2\cdot (N-1-R) + 1 moves, so row R receives the integer
(R-1) + 2\cdot (N-1-R) + 1 = R-1-2-2R+1 = -2-R (all modulo N, of course) - Next, we visit it moving downwards, after another 2\cdot (R-1) + 1 moves. This gives us the integer -2-R+2R-2+1 = R-3
- Another 2\cdot (N-1-R) + 1 moves gives us the integer -4-R, and so on.
From here, a pattern emerges:
- When moving downwards, the row receives the values R-1, R-3, R-5, \ldots
- When moving upwards, the row receives the values (-2-R), (-4-R), (-6-R), \ldots
Because N is even, these two sets don’t intersect; and because we move upwards and downwards \frac{N}{2} times each, they cover all the integers \{0, 1, 2, \ldots, N-1\}, as required.
As for the columns:
- The last column obviously receives every integer
- Every other column receives N-1 consecutive integers for sure, via the upward/downward movements. We only need to prove that the one it receives from the first row is distinct from these N-1.
That isn’t very hard to do in similar fashion to the row proof above (for upward columns, look at what the bottommost element is; and for downward columns, look at what the topmost element is), and we’re done!
TIME COMPLEXITY
\mathcal{O}(N^2) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
const int N = 1007;
int n, a[N][N];
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
if(n % 2) return cout << "-1\n", 0;
for(int i = 1; i < n; i++) s += 'R';
for(int i = 1; i < n; i++) s += 'D';
for(int i = 1; i < n; i++){
s += 'L';
for(int j = 2; j < n; j++) s += (i % 2 ? 'U' : 'D');
}
s += 'U';
int x = 0, y = 0;
for(int i = 0; i < s.size(); i++){
a[x][y] = i % n;
if(s[i] == 'L') y--;
if(s[i] == 'R') y++;
if(s[i] == 'U') x--;
if(s[i] == 'D') x++;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) cout << a[i][j] << ' ';
cout << '\n';
}
cout << s << '\n';
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
while (buffer[pos] == '\r');
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int n = in.readInt(2, 1000);
in.readEoln();
in.readEof();
if (n % 2 == 1) {
cout << -1 << " \n";
return 0;
}
vector<vector<int>> a(n, vector<int>(n));
string b;
for (int i = 1; i < n; i++) {
if (i % 2 == 1) {
b += "D";
b += string(n - 2, 'R');
a[i][0] = (a[i - 1][0] + 1) % n;
for (int j = 1; j < n - 1; j++) {
a[i][j] = (a[i][j - 1] + 1) % n;
}
} else {
b += "D";
b += string(n - 2, 'L');
a[i][n - 2] = (a[i - 1][n - 2] + 1) % n;
for (int j = n - 3; j >= 0; j--) {
a[i][j] = (a[i][j + 1] + 1) % n;
}
}
}
b += "R";
b += string(n - 1, 'U');
b += string(n - 1, 'L');
a[n - 1][n - 1] = (a[n - 1][n - 2] + 1) % n;
for (int i = n - 2; i >= 0; i--) {
a[i][n - 1] = (a[i + 1][n - 1] + 1) % n;
}
for (int j = n - 2; j >= 0; j--) {
a[0][j] = (a[0][j + 1] + 1) % n;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j] << " ";
}
cout << '\n';
}
cout << b << " \n";
return 0;
}
Editorialist's code (Python)
n = int(input())
if n%2 == 1:
print(-1)
exit(0)
moves = 'R'*(n-1) + 'D'
for i in range(n):
if i%2 == 0: moves += 'D'*(n-2)
else: moves += 'U'*(n-2)
moves += 'L' if i+1 < n else 'U'
grid = [0]*(n*n)
shift = {'L' : (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
x, y = 0, 0
for c in moves:
dx, dy = shift[c]
grid[(x+dx)*n + (y+dy)] = (grid[x*n + y] + 1)%n
x += dx
y += dy
for i in range(n): print(*grid[i*n:i*n+n])
print(moves)