DGMATRIX - Editorial

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:

B= \begin{bmatrix} O & y_1 & y_2 & ... & y_N \\ x_1 & . & . & ... & . \\ x_2 & . & . & ... & . \\ ... & . & . & ... & . \\ x_N & . & . & ... & . \\ \end{bmatrix} \quad

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:

B= \begin{bmatrix} O & y_1 & y_2 & y_3 & ...&y_N \\ x_1 & -x_1-y_1 & x_1-y_2 & -x_1-y_3 & ...&. \\ x_2 & -x_2+y_1 & x_2+y_2 & -x_2+y_3 & ...&. \\ x_3 & -x_3-y_1 & x_3-y_2 & -x_3-y_3 & ...&.& \\ ... & . & . & ... & . &.\\ x_N & . & . & ... & . &.\\ \end{bmatrix} \quad

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;
    }
  }
}
7 Likes

Thanks For the solution, I was searching for it desperately :slight_smile: