ZZZ's Site

狗蛋儿

9 August 2020

[Codeforces 1393D] Rarity and New Dress

by zzz

Problem Description

Problem Link

Counting how many rhombuses with the same color in a matrix.

Solution #1: dp[i][j] = min(left[i][j], up[i][j], dp[i][j-2] + 1, dp[i][j-1] + 1)

dp[i][j] is the number of rhombuses with the right-end as (i,j). It needs to be limited by the right, up, dp[i][j-2] and dp[i][j-1].

  for (int k = 0; k < n + m; k++) {
    for (int j = 0; j < m; j++) {
      int i = k - j;
      if (i < 0 || i >= n) continue;
      left[i][j] = 1;
      int ni = i + 1;
      int nj = j - 1;
      if (ni < n && nj >= 0 && a[ni][nj] == a[i][j]) left[i][j] += left[ni][nj];
    }
  }
  for (int k = 0; k < n + m; k++) {
    for (int j = 0; j < m; j++) {
      int i = k - j;
      if (i < 0 || i >= n) continue;
      up[i][j] = 1;
      int ni = i - 1;
      int nj = j - 1;
      if (ni >= 0 && nj >= 0 && a[ni][nj] == a[i][j]) up[i][j] += up[ni][nj];
    }
  }
 
  for (int k = 0; k < n + m; k++) {
    for (int j = 0; j < m; j++) {
      int i = k - j;
      if (i < 0 || i >= n) continue;
      dp[i][j] = 1;
      int ni = i;
      int nj = j - 2;
      if (ni >= 0 && nj >= 0 && a[ni][nj] == a[i][j]) dp[i][j] = min(left[i][j], min(up[i][j], dp[ni][nj] + 1));
    }
  }
  for (int k = 0; k < n + m; k++) {
    for (int j = 0; j < m; j++) {
      int i = k - j;
      if (i < 0 || i >= n) continue;
      ans[i][j] = 1;
      int ni = i;
      int nj = j - 1;
      if (ni >= 0 && nj >= 0 && a[ni][nj] == a[i][j]) {
        ans[i][j] = min(dp[i][j], dp[ni][nj] + 1);
      }
    }
  }

Solution #2: dp[i][j] = min(dp[i+1][j-1] + 1, dp[i-1][j-1] + 1, dp[i][j-2] + 1, dp[i][j-1] + 1)

Actually, we can replace left[i][j] and up[i][j] with dp[i+1][j-1] + 1 and dp[i-1][j-1] + 1 respectively. The code becomes much simpler.

  int ret = 0;
  for (int k = 0; k < n + m; k++) {
    for (int j = 0; j < m; j++) {
      int i = k - j;
      if (i < 0 || i >= n) continue;
      if (j < 2
          || i < 1
          || i + 1 >= n
          || a[i][j] != a[i][j - 1]
          || a[i][j] != a[i - 1][j - 1]
          || a[i][j] != a[i + 1][j - 1]
          || a[i][j] != a[i][j - 2]) {
        ans[i][j] = 1;
      } else {
        ans[i][j] = min({ans[i][j - 1], ans[i][j - 2], ans[i - 1][j - 1], ans[i + 1][j - 1]}) + 1;
      }
      ret += ans[i][j];
    }
  }

Solution #2: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1], dp[i-2][j]) + 1

If we redefine the dp[i][j] as the number of rhombuses with the bottom point as (i, j), we can do a usual for loop.

  int ret = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (i < 2 ||
          j < 1 ||
          j + 1 >= m ||
          a[i][j] != a[i - 1][j - 1] ||
          a[i][j] != a[i - 1][j] ||
          a[i][j] != a[i - 1][j + 1] ||
          a[i][j] != a[i - 2][j]) {
        f[i][j] = 1;
      } else {
        f[i][j] = min({f[i - 1][j - 1],
                       f[i - 1][j],
                       f[i - 1][j + 1],
                       f[i - 2][j]}) + 1;
      }
      ret += f[i][j];
    }
  }

The input optimization

With the following statements that disables the sync of iostream buffers, cin/cout can be as fast as scanf/printf.

  ios_base::sync_with_stdio(0);
  cin.tie(0);

Looking back

More thinking results in simpler code. Solving problems is also an optimzation we can do to get

1. correct solution
2. fast solution
3. simple code

and the ultimate goal is to get the maximum points, which in practice, is the timestamp of quick submittion - alpha * # of wrong submittion.

tags: Codeforces - DP - counting in matrix

Posts

subscribe via RSS