Editorial of MindCoding 2017 Round 2 Bosch (Div. 2)

This problem is simple in theory, but the actual implementation makes it a bit trickier. Due to the constraints, some Fibonacci values may just barely exceed the maximum value that can be stored on a 64-bit numeric data type. The following implementation works as intended:

long long a = 0, b = 1;
while(a < x - b) {
    long long c = a + b;
    a = b;
    b = c;
    ++n;
}

Whereas this very similar piece of code fails the test cases:

long long a = 0, b = 1;
while(a + b < x) {
    long long c = a + b;
    a = b;
    b = c;
    ++n;
}

This overflow problem can be avoided altogether by using a language which provides large numeric data types:

Haskell implementation:

main = do
    input <- getContents
    let xs = map read (words $ last $ lines input) :: [Integer]

    putStrLn $ unwords $ map (show . solve) xs
        where solve x = length $ takeWhile (< x) fibos
              fibos = 1:1:zipWith (+) fibos (tail fibos)

Python implementation:

#!/usr/bin/python3

n = int(input())

ans = []
for x in map(int, input().split()):
    fibos = [0, 1]
    while fibos[-1] < x:
        fibos.append(fibos[-1] + fibos[-2])
    ans.append(len(fibos) - 2)

print(" ".join(map(str, ans)))

Approach #1

Try to swap each pair of bits once, and choose the maximum value. Complexity: O(log² N)

Approach #2

The maximum value can be obtained by swapping the first occurrence of a 0 bit with the last occurrence of a 1 bit. Complexity: O(log N).

Haskell implementation:

import Numeric (showIntAtBase, readInt)
import Data.Char (intToDigit, digitToInt)
import Data.List

bin x = showIntAtBase 2 intToDigit x ""
dec s = foldl' (\acc x -> acc * 2 + digitToInt x) 0 s

best x
    | not (elem '0' x)    = x
    | not (elem '1' x)    = x
    | firstZero > lastOne = x
    | otherwise           = front ++ "1" ++ middle ++ "0" ++ back
    where front     = take firstZero x
          middle    = take (lastOne-firstZero-1) (drop (firstZero+1) x)
          back      = drop (lastOne+1) x
          firstZero = head $ elemIndices '0' x
          lastOne   = last $ elemIndices '1' x

main = do
    input <- getContents
    let xs = map read $ words $ last $ lines input :: [Int]
    putStrLn $ concat $ intersperse " " $ map (show . dec . best . bin) xs

Key observation: the three components of a pixel (red, green and blue) are independent from each other and can be compressed individually.

Approach #1

For one component, the range of hexadecimal values is [0, 255] (that is, from #00 to #FF). Moreover, there are only 16 candidates (compressible values): #00, #11, …, #FF.

The actual pixel component can be converted to base 10. All 16 candidates can be converted to base 10 as well: they all belong to the set {x*16+x | 0 ≤ x ≤ 15}. At this point, we choose the candidate which has the smallest absolute difference compared to the original value.

Haskell implementation:

import Numeric
import Data.Char (toUpper)

data Pixel = Pixel Int Int Int
           deriving (Eq, Show)

pixelFromList (r:g:b:_) = Pixel r g b
pixelFromList _ = error "Pixel must have 3 components"

hexToDec = fst . head . readHex
decToHex x = map toUpper $ showHex x ""

compressP (Pixel r g b) = pixelFromList $ map compress [r,g,b]

compress n = snd $ minimum $ map (\x -> (abs (x-n), x)) compressibles
    where compressibles = [x*16+x | x <- [0..15]]

showCompressedP (Pixel r g b) = '#' : (foldr  (:)  [] $ map (last . decToHex) [r,g,b])

readP s = pixelFromList $ map hexToDec [r, g, b]
    where r = take 2 $ tail s
          g = take 2 $ drop 3 s
          b = drop 5 s

main = do
    input <- getContents
    let image = map (map (showCompressedP . compressP . readP) . words) $ drop 1 $ lines input
    sequence $ map (putStrLn . unwords) image

Approach #2

Upon closer inspection, we notice that the set of candidates can be reduced to just a select few. Consider the component #XY (where X and Y are hexadecimal digits). The most natural decision is to only change Y to match X, leading to the compressible value #XX. This works well in cases such as #14 → #11 (delta = 3), but performs sub-optimally in other scenarios: #1F → #22 (delta = 2) is a better choice than #1F → #11 (delta = 14).

The optimal decision in such cases is to only change X by one unit, leading to the compressible #(X-1)(X-1) or #(X+1)(X+1). We choose whichever value is closest to #XY.

Python implementation:

#!/usr/bin/python3
import sys

def diff(x, y):
    return abs(int(x, 16) - int(y, 16))

def compress(x):
    a = max('0', '9' if x[0] == 'A' else chr(ord(x[0])-1))
    b = x[0]
    c = min('F', 'A' if x[0] == '9' else chr(ord(x[0])+1))

    return min([(diff(a+a, x), a),
                (diff(b+b, x), b),
                (diff(c+c, x), c)])[1]

def compressPixel(p):
    return "#%c%c%c" % (compress(p[1:3]), compress(p[3:5]), compress(p[5:]))

def main():
    n, m = map(int, input().split())
    for line in sys.stdin:
        print(' '.join(list(map(compressPixel, line.split()))))

if __name__ == '__main__':
    main()