Diane

Below is my solution to the Codeforces div2 735 problem D: Diane.

We want to find the simplest way to construct a string $s$ which has no substrings occuring an odd number of times. Let us consider the string $a^{k}$. If $k$ is even then we have the followin substring properties.

If $k$ is odd, then we have the opposite parities. Observe that if we could separate $a^k$ and $a^{k+1}$ then because $k$ and $k+1$ have opposite parity, the substrings each occur an odd number of times.

Thus $s=a^kba^{k+1}$ generates strings of length $2k+2$, i.e. $2, 4, 6, \cdots$. Furthermore, $s=a^kbca^{k+1}$ generates strings of length $2k+3$, i.e. $3, 5, 7, \cdots$. Finally, if $n=1$, we trivially set $s=a$. Note the time required to print out the string is $O(n)$, so this solution passes.

Explorer space

 This is my solution to Codeforces round 718 div2 + div1 problem D: Explorer Space.

First we observe that it is only possible to return to $(i, j)$ iff $k$ is even. This is because for every step away from $(i, j)$ we need one step back, so we can pair up each step of a walk meaning $k$ must be even.

Next we observe that we can never have a different path in to $(i, j)$ than the path taken out from it. To prove this, suppose we could take a different path in, call it $p_{\text{in}}$, then we know the cost of $p_{\text{in}} \leq p_{\text{out}}$. But then we can swap $p_{\text{out}}$ with $p_{\text{in}}$, giving us a lower cost path.

Now we can use dynamic programming to compute the minimum cost path of length $k$. Concretely, let $dp_{i, j, k}$ denote the minimum cost path to $(i, j)$ with exactly $k$ steps. Then

$$dp_{i, j, k} = \min_{\text{all edges $e$ incident to $(i, j)$}}{dp_{e, k-1} + w_e}$$

This solution takes $O(nmk)$ time.