I did some magical stuff here.

First, reduce the input $$$(N, D, S)$$$ into $$$(n, d, s) = (\lfloor \frac{N}{S} \rfloor, \lfloor \frac{D}{S} \rfloor, 1)$$$.

First observation is that the answer is clearly $$$x_1 x_2 S$$$, with the variables being such that $$$1 \le x_1 \le d$$$, $$$1 \le x_2 \le \lfloor \frac{d}{x_1} \rfloor + 1$$$ and $$$1 \le x_1 x_2 \le n$$$.

Thus, now we can try every $$$x_1$$$ and $$$x_2$$$ to find the answer.

Magical parts (that I myself can't yet prove why they worked): I only probed $$$x_1$$$ and $$$x_2$$$ until each of them reached either $$$10^6$$$ or $$$d$$$, whichever is lower. Had to probe both variables independently — $$$x_1$$$ in range $$$[1, \text{lim}]$$$ and $$$x_2$$$ in range $$$[2, \text{lim}]$$$ — only doing one of them caused WA.

You can think about contribution of each element. Suppose u want to see if an element x contribute, the segment it is on must have all elements on its row before < x and after it >= x (to handle duplicate x cases, allow only the earliest x to contribute), then on the other row it must have an element > x. So for each element u can calculate the ranges that satisfy for your row and the range it dont satisfy for the other row, which can be done fast Then, you just do probability calculations for each element to find probability it contribute to sum once u have the ranges

• Consider adjacent words $$$s[i,j],s[j+1,k]$$$.It should be $$$s[i,j]<s[j+1,k]$$$,you can see that the valid $$$k$$$ is an interval, or more accurately, a suffix.Define $$$k_{mn}$$$ as the minimum value of $$$k$$$.Define $$$dp_{i,j}$$$ as the maximum number of words with the first $$$i$$$ characters ending in $$$s[i, j]$$$.You can see $$$dp_{i,j}$$$ can update $$$dp_{j+1,k}$$$ with a time complexity of $$$O(1)$$$ using suffix marking.
• You can use $$$exkmp$$$(aka.$$$Z\;function$$$),$$$suffix\;array$$$ or others to calculate $$$k_{mn}$$$ quickly.
• Forgive my Chinglish.

Thank you so much for pointing this out. We've updated this blog with an announcement.

Yes, the following grader is a modification to the function BDFS() that runs in $$$O(N+M)$$$.

BDFS_Grader(K):
  let S be an empty stack
  let FLAG be a boolean array of size N which are all false initially
  let counter be an integer intialized with 0

  push 1 to S

  while S is not empty:
    pop the top element of S into u

    counter += num_of_neighbours(u)
    if counter > K: return WA()
    if visited[u] is true: continue
    visited[u] = true

    for each v neighbour of u in ascending order:
      if visited[v] is false:
        push v to S

  if counter != K: return WA()
  return AC()

This is also part of the observation to simplify brainstorming the valid construction, although we are aware it is possible to find the construction without this observation.

Hello, here is the original editorial that I wrote when I proposed the problem. I thought this version is a bit long-winded and I tried to simplify it. I apologize for it ended up being harder to understand.

There are 4 simple yet important lemmas to solve this problem.

Lemma 1. The answer is either INVALID for all scenarios or the total penalty of all cycles in the grid is $$$0$$$.

Proof. Suppose that there is a cycle with a total penalty of $$$x$$$. Notice how the cycle in the opposite direction has a total penalty of $$$-x$$$ (negative cycle).

Define this property of "all cycles have total penalty of $$$0$$$" as zero-cycle.

Lemma 2. A grid is zero-cycle if all cycles from two-by-two sub-grids have a total penalty of $$$0$$$.

Proof. This lemma is the hardest to prove. I saw many solutions that just run DFS from $$$(1, 1)$$$ and check if a negative cycle exists. This is basically doing the same thing but without realizing/proving this lemma.

As mentioned in the editorial, any cycle can be transformed into any other cycle through a series of substitutions of the penalty. It is hard to explain it in words but easier to demonstrate. Here's a rough sketch that I drew, hopefully this helps to understand why it is correct.

With Lemma 2, we can check whether the grid is zero-cycle or not with a simple $$$O(NM)$$$ loop. Now, we just need to calculate the shortest path.

Denote $$$d(u, v)$$$ as the minimum total penalty from cell $$$(r_u, c_u)$$$ to $$$(r_v, c_v)$$$. Note that all cycles have a total penalty of $$$0$$$ (because the scenario is invalid, otherwise).

Lemma 3. $$$d(u, v) = -d(v, u)$$$.

Proof. $$$u \rightarrow v \rightarrow u$$$ is a cycle. Therefore, $$$d(u, v) + d(v, u) = 0$$$.

Lemma 4. $$$d(u, v) = d(u, k) + d(k, v)$$$.

Proof. $$$u \rightarrow k \rightarrow v \rightarrow u$$$ is a cycle. Therefore, $$$d(u, k) + d(k, v) + d(v, u) = 0$$$. By Lemma 3, $$$d(u, k) + d(k, v) - d(u, v) = 0$$$.

Lemma 4 is very important. Note how the minimum total penalty is not affected with what path you take. This simplify the problem drastically, for instance, you can choose to only move left/right for the horizontal move, and only move up/down for the vertical move of the path. Using 2D Prefix Sum, you can solve each scenario in $$$O(1)$$$ and this is an alternate solution. However, there is a simpler and more elegant solution.

Denote cell $$$s$$$ as the most top-left cell, or cell $$$(1, 1)$$$. Note that $$$d(u, v) = d(u, s) + d(s, v) = d(s, v) - d(s, u)$$$, which basically turn this problem into single-source shortest path. It sounds dumb to move back to cell $$$(1, 1)$$$ first, but as proven in Lemma 4, the minimum total penalty won't change.

Furthermore, using Lemma 4 again, we can precompute $$$d(s, u)$$$ easily by moving right first, then moving down. This can be easily done in a simple $$$O(NM)$$$ loop. Finally, each scenario can be answered in $$$O(1)$$$ using the precomputed $$$d(s, u)$$$. Funny enough, the final solution doesn't even contain any graph/shortest path algorithm.

I hope this editorial version is clearer to follow.

UPD1. Here is my code.

Fun fact 1: you can use Lemma 2 to generate a random zero-cycle grid easily. This is how I generate the test cases.

Fun fact 2: Originally, the problem doesn't have any query (only ask one scenario). However, I found Lemma 3 and Lemma 4 right before I submitted this problem. I found this transitivity property on the distance pretty interesting (I think I called it "vector addition" in the editorial) but unfortunately I can't find a better application than making it a "query" problem.