Editorial for Baltic OI '19 P2 - Nautilus - DMOJ: Modern Online Judge

Editorial for Baltic OI '19 P2 - Nautilus

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.

Subtask 1

( $1 \le R, C, M \le 100$ ~1 \le R, C, M \le 100~; there are no ? queries)

The solution to this subtask is straightforward — try all possible starting positions. It is simple to verify whether the ship could have started at a given position: simply simulate the ship's movement, starting from that position. If you hit an edge or island, you know that the ship couldn't have started there.

Verifying this for each position takes $\mathcal O(M)$ ~\mathcal O(M)~ time. There are $RC$ ~RC~ possible starting positions: total time complexity will be $\mathcal O(RCM)$ ~\mathcal O(RCM)~.

Subtask 2

( $1 \le R, C, M \le 100$ ~1 \le R, C, M \le 100~)

We solve this using dynamic programming. We want $dp[i][j][t]$ ~dp[i][j][t]~ to be $1$ ~1~ if and only if it is possible that the ship is in position $i, j$ ~i, j~ after the first $t$ ~t~ steps, considering only the first $t$ ~t~ characters of $M$ ~M~.

We can make some observations. If there is an island at position $(i, j)$ ~(i, j)~, then $dp[i][j][t]$ ~dp[i][j][t]~ will be $0$ ~0~, so let's look at the case where there is no island at position $(i, j)$ ~(i, j)~. It's clear that $dp[i][j][0] = 1$ ~dp[i][j][0] = 1~ for any $i$ ~i~ and $j$ ~j~. If the message at position $t$ ~t~ is a letter, for example E, then $dp[i][j][t] = dp[i][j-1][t-1]$ ~dp[i][j][t] = dp[i][j-1][t-1]~, because if the ship indeed was at position $(i, j)$ ~(i, j)~ at time $t$ ~t~ and went east before that, then it must have been at $(i, j-1)$ ~(i, j-1)~ at time $t-1$ ~t-1~. If the message at position $t$ ~t~ is a question mark, then $dp[i][j][t]$ ~dp[i][j][t]~ is $1$ ~1~ if and only if at least one of $dp[i][j-1][t-1]$ ~dp[i][j-1][t-1]~, $dp[i][j+1][t-1]$ ~dp[i][j+1][t-1]~, $dp[i-1][j][t-1]$ ~dp[i-1][j][t-1]~, $dp[i+1][j][t-1]$ ~dp[i+1][j][t-1]~ is $1$ ~1~, because the ship must have come from one of these squares.

Using these relations, we can calculate $dp[i][j][M]$ ~dp[i][j][M]~ for all $i$ ~i~ and $j$ ~j~. The answer is the number of pairs $(i, j)$ ~(i, j)~ such that $dp[i][j][M] = 1$ ~dp[i][j][M] = 1~.

The complexity is once again $\mathcal O(RCM)$ ~\mathcal O(RCM)~.

Subtask 3

( $1 \le R, C \le 500; 1 \le M \le 5000$ ~1 \le R, C \le 500; 1 \le M \le 5000~)

The complexity shall still be $\mathcal O(RCM)$ ~\mathcal O(RCM)~, but we are going to use a very powerful way to optimize: bitsets! In C++, bitset is a data type that can be thought of as an array of booleans that supports, among other things, the following operations: bitwise "or" (denoted $\mid$ ~\mid~); bitwise "and" (denoted $\&$ ~\&~) and the left and right bitwise shifts (denoted $\ll$ ~\ll~ and $\gg$ ~\gg~ respectively). Bitwise "and" and "or" are simply the logical "and" and "or" operations, applied to each bit separately. For example:

$\displaystyle \begin{array}{ccccccccc} & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ \mid & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \end{array}\qquad\begin{array}{ccccccccc} & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ \& & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \end{array}$

The bitwise shifts shift the whole string by an integer number of positions, appending or prepending zeroes if necessary. For example: $00110101 \ll 3 = 10101000$ ~00110101 \ll 3 = 10101000~; $11001111 \gg 2 = 00110011$ ~11001111 \gg 2 = 00110011~. Compared to manually doing those operations on an array of booleans, they are very fast, because there exist machine-level instructions for doing them.

We represent $dp[i][t]$ ~dp[i][t]~ as a bitset, where $dp[i][t]$ ~dp[i][t]~ consists of what $dp[i][1][t], dp[i][2][t], \dots, dp[i][C][t]$ were in the last subtask. Also let $sea[i]$ ~sea[i]~ be a bitset of the $i^\text{th}$ ~i^\text{th}~ row of the grid – where . is converted to $1$ ~1~ and # is converted to $0$ ~0~. Now notice that we can do the entire computation in bitsets:

$\displaystyle dp[i][t] = \begin{cases} dp[i+1][t-1] \mathbin\& sea[i] & \text{if the }t^\text{th}\text{ message is }\tt N \\ (dp[i] \ll 1) \mathbin\& sea[i] & \text{if the }t^\text{th}\text{ message is }\tt E \\ (dp[i+1][t-1] \mid dp[i-1][t-1] \mid (dp[i][t-1] \ll 1) \mid (dp[i][t-1] \gg 1)) \mathbin\& sea[i] & \text{if the }t^\text{th}\text{ message is }\tt ? \end{cases}$

Cases S and W are handled analogously.

How to do this in Java or Python? In Python, the jury simply used Python's big integers and treated them as bitstrings. In Java, both the BigInteger and BitSet classes exist, but neither work for this problem: BigInteger is too slow and BitSet lacks the bit-shift operators that we require. Instead, we replaced each bitset with a short array of longs.

In fact, there are other ways to optimize the C++ solution. For example including the following line:

#pragma GCC optimize("Ofast")