Editorial for Yet Another Contest 6 P6 - No More Snakes and Ladders

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Subtask 1

We can solve each query separately using dynamic programming. The DP states are the current position in the grid, and the number of remaining times we may ignore the contribution of a cell's value to the total sum. The transitions are straightforward.

Time complexity: $\mathcal{O}(QNM\max(K_i))$ ~\mathcal{O}(QNM\max(K_i))~

Subtask 2

We can use divide and conquer to answer the queries offline. Consider a recursive function which solves for all queries inside a particular subgrid. Imagine a vertical line of cells down the middle of the subgrid. Every query inside this subgrid must fall into one of three categories:

Both the starting and ending cells of the query are completely on the left of the vertical line.
Both the starting and ending cells of the query are completely on the right of the vertical line.
The starting cell is on the left or on the splitting line, and the ending cell is on the right or on the splitting line.

The first two categories are handled by the 'divide' part of the divide and conquer. So, we will only focus on the third category of queries.

Each of the queries' paths must pass through at least one of the cells in the vertical line. So, for each cell on the vertical line, we can utilise the subtask 1 solution to precompute two DPs per cell; the first DP involves paths going down and right, starting at the cell, whilst the other DP involves paths going up and left, starting at the cell. If we fix the cell which a particular query's path must pass through, we can combine these two DPs to find the answer. So it suffices to precompute these DPs for each cell on the vertical line, and to iterate through every cell on the vertical line for each query.

Note that we can do exactly the same thing using a horizontal line of cells instead. It is optimal to choose between a vertical and horizontal line such that the two new subgrids are as close to squares as possible.

Time complexity: $\mathcal{O}(N\max(K_i)(N^2+Q))$ ~\mathcal{O}(N\max(K_i)(N^2+Q))~, assuming $M = \mathcal{O}(N)$ ~M = \mathcal{O}(N)~

Comments

4

Geothermal commented on Dec. 27, 2022, 6:53 a.m. ← edited →

How do we prove the time complexity for the full solution? I got AC while splitting only on vertical lines, which should run in $\mathcal{O}(NM^2K \log N)$ ~\mathcal{O}(NM^2K \log N)~ but is fast enough to pass comfortably because the constant factor is relatively small. However, I don't immediately see how to show that adding the option of splitting over horizontal lines eliminates the log factor.

0

spheniscine commented on Dec. 27, 2022, 11:36 p.m. ← edit 2 →

I tried implementing it but I am having trouble with the constant factor; even subtask 1 ran in 452 ms in the worst case, and I think I ran into the $\mathcal{O}(NKQ)$ ~\mathcal{O}(NKQ)~ bottleneck in the full task

edit: Got it in 494 ms after optimizing memory usage to $\mathcal{O}(NMK)$ ~\mathcal{O}(NMK)~, which incidentally reduced indirection

5

Josh commented on Dec. 27, 2022, 8:20 a.m. ← edit 2 →

Here’s how I reason about it. We will ignore the queries for the complexity analysis and instead focus on the DP calculations. Also, let’s ignore $K$ ~K~ entirely for now.

For simplicity, assume that the grid is a square. For every splitting line, let’s say that every cell in the current subgrid is related to the splitting line. Consider any particular cell, and calculate the sum of the lengths of all splitting lines related to it. If we sum this value over all cells, we get our final complexity.

But each cell is related to a length $N$ ~N~ vertical splitting line, a length $\frac{N}{2}$ ~\frac{N}{2}~ horizontal splitting line, a length $\frac{N}{4}$ ~\frac{N}{4}~ vertical splitting line, and so on. Then, the sum of these lengths is approximately $2N$ ~2N~, so the total complexity is $\mathcal{O}(N^3)$ ~\mathcal{O}(N^3)~.

Alternatively, let $T(N)$ ~T(N)~ be the total time to solve for a $N$ ~N~ by $N$ ~N~ grid. Consider calculating the DPs for a vertical splitting line of length $N$ ~N~ and two horizontal splitting lines of length $\frac{N}{2}$ ~\frac{N}{2}~, then recursing on each of the four smaller subgrids. We have a recurrence in the form $T(N) = 4T(\frac{N}{2}) + \mathcal{O}(N^3)$ . Applying case $3$ ~3~ of the master theorem, we see that $T(N) = \Theta(N^3)$ ~T(N) = \Theta(N^3)~ as desired.

I typed this on my phone and it was very painful :(

3

Geothermal commented on Dec. 27, 2022, 3:38 p.m.

Thanks for the explanation!