v

Introduction

Today, I'm gonna write an editorial for a BOJ PS problem. It's been a long time since I wrote a PS post but writing an editorial in English might help me practice writing about a variety of topics.

The problem which I'll cover is BOJ 33918-맛있는 스콘 만들기. It was a pretty difficulty problem for me. The level of that problem is Platinum 3. I had solved neumorous Platinum problems, but I haven't practiced PS consistently for the past3 years.

At a first glance

For solving this problem, we have to check the limitations of the problem like the time limit, maximum input size.

Fortunately, we have small $N$ and quite a reasonable $N \times M$. One step further, it doesn't look hard to come up with a solution. It seems a simple dynamic programming formula has to work.

Although we have an $O(NM)$ memory complexity, filling the DP table up isn't easy.

Let me define the formula.

DP[i][j] = at the time i, the maximum tastiness of scone

We should fill in each DP table cell like the following.

DP[i][j] = M - | b[i] - j | + max(dp[i-1][j-D], dp[i-1][j-D+C], ..., dp[i-1][j+D])

Right?

We have to calculate each dp cell in $O(logM)$ time at most. How can we do that?

Divide and Conquer

Sorry, I didn't mean real a D&C algorithm. If we read the problem description carefully, we must catch a weird limitation. It's that $D$ is divisible by $C$.

That means we can divide the problem into each dimension of residuals, which is the result of dividing by $C$.

There must be $C$ problems. I'll call this $R(0 \le R \le C-1)$.

For example, for $R=1$, local index $i'=0$ is equivalent to real index $i=1$ , and $i'=1$ is $i=1+C$.

So, we can map the real index $i$ to the local index $i'$ as $i'=i / C + R$.

This leads us to solve just one problem with index mapping. The global maxima among the $C$ independent local maximas will be the answer for the problem.

Finally, without loss of generality, we can focus on just one residue class.

Monotone Deque

Monotone deque(also known as Deque Range Maximum Trick) is a problem-solving technique of managing deque with obeying monotonicity.

Monotonicity is a property that elements in the collection are managed in a sequential manner like ascending or descending.

Thanks to monotonicity, $O(1)$ speed of finding the largest element in the current range is possible.

In each $R$ dimension, we can manage a left-side deque and a right-side deque both.

An element of left-side deque, $L[i]$ stores the largest value in the range $[i - R, i]$. $R$ is an equivalent of right sided. $R$ can be built by reversing the process.

We can query easily what is the largest value in the range $[i-R, i+R]$ in step size of $C$ with $O(1)$ time complexity.

Code

My code is not good at dividing subproblems. You might be able to come up with a neater approach.

void solve() {
  int n, m, c, d;
  cin >> n >> m >> c >> d;
  vi b(n);
  vvi dp(n, vi(m + 1, -1e9));
  fv(b);
  for (int i = 0; i <= m; i++)
    dp[0][i] = m - abs(b[0] - i);

  int bucket_cap = m / c + 1;
  int w = d / c;

  auto create_deque = [&](int i, int r, vi &L, vi &R) {
    {
      deque<pi> dq;
      for (int j = r == 0 ? c : r; j <= m; j += c) {
        while (sz(dq) && dq[0].fi < j - d)
          dq.pop_front();
        while (sz(dq) && dq[sz(dq) - 1].se <= dp[i][j])
          dq.pop_back();
        dq.pb({j, dp[i][j]});
        L[j / c] = dq.front().se;
      }
    }
    {
      int right_end = m - ((m - r) % c);
      assert(right_end <= m);
      deque<pi> dq;
      for (int j = right_end; j >= 1; j -= c) {
        while (sz(dq) && dq[0].fi > j + d)
          dq.pop_front();
        while (sz(dq) && dq[sz(dq) - 1].se <= dp[i][j])
          dq.pop_back();
        dq.pb({j, dp[i][j]});
        R[j / c] = dq.front().se;
      }
    }
    debug(i, r);
    debug(dp[i]);
    debug(L, R);
  };

  auto get_maximum = [&](const vi &L, const vi &R, int r, int j) -> int {
    int index_in_bucket = (j) / c;
    debug(r, j, index_in_bucket);
    assert(index_in_bucket < sz(L) && index_in_bucket < sz(R));
    int l_max = L[index_in_bucket];
    int r_max = R[index_in_bucket];
    return max(l_max, r_max);
  };

  int ans = 0;
  for (int i = 0; i <= m; i++) {
    maxa(ans, m - abs(b[0] - i));
    dp[0][i] = m - abs(b[0] - i);
  }
  assert(ans == m);
  for (int r = 0; r < c; r++) {
    for (int i = 1; i < n; i++) {
      vi L(bucket_cap), R(bucket_cap);
      create_deque(i - 1, r, L, R);
      for (int j = r == 0 ? c : r; j <= m; j += c) {
        dp[i][j] = get_maximum(L, R, r, j) + m - abs(b[i] - j);
        maxa(ans, dp[i][j]);
      }
    }
  }
  cout << ans;
}