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

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

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.

Haskell implementation:

solve [a, b] = (sum $ map subsequences deltas) `mod` (10^9+7)
    where deltas         = zipWith (-) (tail interestPoints) interestPoints
          interestPoints = a : (dropWhile (<= a) $ takeWhile (<= b) powers) ++ [b+1]
          subsequences x = (x * succ x) `div` 2
          powers         = map (2^) [1..]

main = do
    input <- getContents
    let queries = map ((map read) . words) $ (tail . lines) input
    sequence $ map (print . solve) queries

The first observation we can make is that 0 ≤ orSum(S') < 2^19 for any subset S' of S1. Let's see if we can construct a set Q, having 0 ≤ orSum(Q) < 2^19 using the integer values from S1. It is enough to consider for this all elements of S1 which are completely included in Q. An element x is completely included in a set S if orSum(S) | x = orSum(S), i.e. there is no position 0 ≤ i < 19 for which orSum(S) & 2^i == 0 and x & 2^i != 0. If these are not enough to form Q, then we cannot obtain Q at all.

We now need to compute for each such Q the orSum of all elements “completely included” in S1. We can compute dp[x] = orSum(dp[x - 2^i]), where 0 ≤ i < 19 and x & 2^i == 2^i. Remark: if x belongs to S1, then dp[x] = x.

Now, S2 needs to contain all numbers x having dp[x] = x and orSum({dp[x - 2^i] where 0 ≤ i < 19 and x & 2^i == 2^i}) < x. This assures us that they cannot be generated by applying orSum on a subset of numbers from S1, so they must be in S2.