Editorial of MindCoding 2017 Round 3 Take Off Labs (Div. 2)

We can observe that:

1. The first element is always on an odd position, so it never gets removed.
2. The second value we need to output is located at position 1 + 2^i-1, where i is the largest value such that 1 + 2^i-1 < N.

A similar approach, implemented in Haskell:

import Data.Bits
import Data.Int

closestPower x = if null smallerPowers then max 1 $ closestPower (x-1)
                                       else x - sum (init smallerPowers)
    where smallerPowers = [2^i | i <- [0..32], not $ elem (x .&. (shift 1 i)) [0, x]]

main = do
    input <- getContents
    let [a,b,n] = map read $ words input :: [Int64]

    putStrLn $ show (a + b) ++ " " ++ show (a * (succ $ closestPower n) + b)

We can solve the problem using dynamic programming:

Let dp[i][L][R] = the minimum total cost of typing the first i characters, such that we end up with the left finger on the L key and the right finger on R.

Initially, dp[0]['F']['J'] = 0 and dp[everything else] = inf.
Now, assume we are in the state [i][L][R]. There are two ways of having reached this state:

• from [i-1][prevL][R], by moving the left finger from prevL to L
• from [i-1][L][prevR], by moving the right finger from prevR to R

Notice that, regardless of what we choose, one of the fingers stays in the same position.
In addition, we know that by reaching [i][L][R], we have just typed the i^th character.
As a consequence, either L or R must be equal to s[i].

Finally, we construct the following recursion:

• dp[i][s[i]][prevR] = min(dp[i][s[i]][prevR], dp[i-1][prevL][prevR] + manhattanDist[prevL][s[i]]);
• dp[i][prevL][s[i]] = min(dp[i][prevL][s[i]], dp[i-1][prevL][prevR] + manhattanDist[prevR][s[i]]);

The answer is the minimum value of dp[N][L][R], for any L, R in the alphabet.