# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* NaOH_Frog

*tabr*

**Tester:***iceknight1093*

**Editorialist:**# 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)
```