PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Ildar Gainullin
Tester: Alexander Morozov
Editorialist: Alei Reyes
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Shortest Paths
PROBLEM:
You are given a matrix A of non-negative integers with N rows and N columns. Find a matrix B with N+1 rows and N+1 columns such that:
- each element of B is a digit between 0 and 9 (inclusive)
- A_{i,j} = B_{i,j}+B_{i+1,j}+B_{i,j+1}+B_{i+1,j+1} for each valid i,j
QUICK EXPLANATION:
Brute force the first element of the matrix B_{1,1}, then reduce the problem to inequalities of the form L \leq x_i-y_j \leq R. Solve the system of inequalities using Bellman-Ford.
EXPLANATION:
The relationship A_{i,j} = B_{i,j}+B_{i+1,j}+B_{i,j+1}+B_{i+1,j+1} allows to find the value of A_{i,j} as the sum of elements in the submatrix of size 2 with top-left corner at (i,j). That means we can calculate the entry at position (i+1,j+1) if we know all entries (x,y) where x\leq i and y\leq j. Therefore if we are given the first row and column of B, we can reconstruct the full matrix by reversing the equation: B_{i+1,j+1} = A_{i,j}-(B_{i,j}+B_{i+1,j}+B_{i,j+1}).
Let’s denote the first element of the i+1-th row of B by x_i, similarly let the first element oft the j+1-th column be y_j, and let O be the element at position (1,1) like in the following diagram:
The matrix B satisfies an interesting property, it turns out that the value at position (i+1,j+1) can be calculated using x_i, y_j, O and the matrix A, it doesn’t matter the values assigned to the other variables x_k, y_l (k \neq i, l\neq j). Moreover B_{i,j} is a linear combination of x_i and y_j of the form \alpha_{i,j} \cdot x_i + \beta_{i,j} \cdot y_j, where \alpha_{i,j},\beta_{i,j} \in \{-1,1\} . This can be easily spotted by manually computing some of the entries of B. For simplicity let’s consider O=0 and A_{i,j}=0:
For example:
- B_{2,2}+x_1+y_1+O=A_{1,1} therefore B_{2,2}=(A_{1,1}-O)-x_1-y_1. We are interested only in the variables x,y so for the moment let’s neglect the terms A and O.
- B_{4,4}+(x_3 -y_2)+(-x_2+y_3)+(x_2+y_2)=A_{3,3} therefore B_{4,4}=-x_3-y_3. Notice how the terms are simplified.
The sign of x_i alternates from column to column, and the sign of y_i alternates from row to row.
How to find the influence of A and O over each element of the matrix? The operations to complete B given the first row and column are linear, so we can get the additional terms by completing a matrix consisting of zeroes except B_{1,1}=O.
Let’s brute force all possible values of O from 0 through 9, complete the matrix using the recurrence, and for each entry let’s create an inequality: 0 \leq B_{i,j} \leq 9.
The system of inequalities can be solved using Bellman Ford. The intuition is that if L \leq x_i-y_j \leq R holds, then x_i \geq y_j+L (similarly the other inequality with R), meaning that the cost to reach x_i is more than L starting from y_j and can be represented as an edge y_j \rightarrow x_i with cost L.
SOLUTIONS:
Setter's Solution
int cur[10][10][101][101];
int arr[101][101];
const int inf = 1e9;
int main() {
int n;
cin >> n;
vector <vector <int> > a(n, vector <int> (n));
for (int i = 0; i < n; i++) for (int j = 0; j< n; j++) cin >> a[i][j];
for (int x = 0; x < 10; x++) {
for (int y = 0; y < 10; y++) {
for (int i = 0; i <= n; i++) for (int j= 0; j <= n; j++) arr[i][j] = 0;
for (int i= 1; i <= n; i++) arr[0][i] = x, arr[i][0] = y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i + 1][j + 1] = a[i][j] - arr[i][j] - arr[i][j + 1] - arr[i + 1][j];
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
cur[x][y][i][j] = arr[i][j];
/*
if (i == n && j == n) {
cout << x << ' ' << y << ' ' << cur[x][y][i][j] << endl;
}
*/
}
}
}
}
for (int o = 0; o < 10; o++) {
vector <vector <int> > b(n + 1, vector <int> (n + 1));
b[0][0] = o;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
b[i + 1][j + 1] = a[i][j] - b[i][j] - b[i][j + 1] - b[i + 1][j];
}
}
int verts = n + n + 1;
vector <vector <pair <int, int> > > g(verts);
auto add_ineq = [&] (int a, int b, int c, int d) {
g[a].push_back({b, d});
g[b].push_back({a, -c});
};
int zero = 0;
for (int i = 1; i <= n; i++) {
if (i % 2 == 0) {
add_ineq(i, 0, 0, 9);
add_ineq(n + i, 0, -9, 0);
} else {
add_ineq(i, 0, -9, 0);
add_ineq(n + i, 0, 0, 9);
}
}
bool bad = false;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
vector <int> rofl;
for (int x = 0; x < 10; x++) {
for (int y = 0; y < 10; y++) {
int val = b[i][j] + cur[x][y][i][j] - cur[0][0][i][j];
if (0 <= val && val < 10) {
int ok = (j % 2 == 0 ? x : -x) - (i % 2 == 1 ? y : -y);
rofl.push_back(ok);
}
}
}
if (rofl.empty()) {
bad = true;
continue;
}
int vl = *min_element(rofl.begin(), rofl.end());
int vr = *max_element(rofl.begin(), rofl.end());
/*
for (int x = 0; x < 10; x++) {
for (int y = 0; y < 10; y++) {
int val = b[i][j] + cur[x][y][i][j];
int ok = (i % 2 == 0 ? x : -x) - (j % 2 == 1 ? y : -y);
assert((0 <= val && val < 10) == (vl <= ok && ok <= vr));
}
}
*/
add_ineq(j, n + i, vl, vr);
}
}
if (bad) continue;
vector <int> dist(verts, -inf);
dist[0] = 0;
bool ch = true;
while (ch) {
if (dist[0] != 0) {
bad = true;
break;
}
ch = false;
for (int i = 0; i < verts; i++) {
for (auto c : g[i]) {
int j = c.first, r = c.second;
if (dist[j] < dist[i] - r) {
ch = true;
dist[j] = dist[i] - r;
}
}
}
}
if (!bad) {
vector <vector <int> > ans(n + 1, vector <int> (n + 1));
ans[0][0] = o;
for (int i = 1; i <= n; i++) {
if (i % 2 == 0) {
ans[0][i] = dist[i];
} else {
ans[0][i] = -dist[i];
}
}
for (int i = 1; i <= n; i++) {
if (i % 2 == 1) {
ans[i][0] = dist[n + i];
} else {
ans[i][0] = -dist[n + i];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ans[i + 1][j + 1] = a[i][j] - ans[i][j] - ans[i][j + 1] - ans[i + 1][j];
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
cout << ans[i][j];
}
cout << '\n';
}
return 0;
}
}
}
