## Google code jam qualification round 2011

I solved 3 problem out of 4. I was not able to get the problem A.With 80 points , i got a prime number ( 2221 ) rank in the list :P. The Magicka problem was based on simulation. Just simulate the process . I wrote Haskell solution for this problem after the contest.

import Data.List as L import Data.Map as M rInt::String -> Int rInt = read checkFun::[String] -> String ->String -> Bool checkFun xs [] s = False checkFun xs ( y:ys ) s = if or [ elem ( [y] ++ s ) xs , elem ( s ++ [y] ) xs ] then True else checkFun xs ys s solve :: [ String ] -> String solve xs = let c = rInt . head $ xs t_1 = take c . tail $ xs tmp_1 = drop c . tail $ xs d = rInt . head $ tmp_1 t_2 = ( take d . tail $ tmp_1 ) ++ ( L.map reverse ( take d . tail $ tmp_1 ) ) -- i got the list in both order tmp_2 = drop d . tail $ tmp_1 s = concat.tail $ tmp_2 t_l = L.map ( take 2 ) t_1 t_r = L.map ( drop 2 ) t_1 m = M.fromList $ zip ( t_l ++ ( L.map reverse t_l ) ) ( t_r ++ t_r ) in solveHelp [ head s ] ( tail s ) m t_2 solveHelp:: String -> String -> Map String String -> [String] -> String solveHelp xs [] _ _ = xs solveHelp xs [y] m t_2 = case M.lookup ( [ L.last xs ] ++ [ y ] ) m of Just c -> L.init xs ++ c _ -> case M.lookup ( [ y ] ++ [ L.last xs ] ) m of Just c -> L.init xs ++ c _ -> case checkFun t_2 xs [ y ] of True -> [] _ -> xs ++ [ y ] solveHelp xs (y_1:ys) m t_2 = case M.lookup ( [ L.last xs ] ++ [ y_1 ] ) m of Just c -> solveHelp ( L.init xs ++ c ) ys m t_2 _ -> case M.lookup ( [ y_1 ] ++ [ L.last xs ] ) m of Just c -> solveHelp ( L.init xs ++ c ) ys m t_2 _ -> case checkFun t_2 xs [ y_1 ] of True -> solveHelp [ head ys ] ( tail ys ) m t_2 _ -> solveHelp ( xs ++ [y_1] ) ys m t_2 format :: String -> String format [] = "[]" format [x] = "[" ++ [x] ++ "]" format ( x:xs ) = "[" ++ [x] ++ helpFormat xs ++ "]" where helpFormat [] = "" helpFormat ( x:xs ) = ", " ++ [x] ++ helpFormat xs main::IO() main = interact $ unlines . zipWith (++) ["Case #" ++ show i ++ ": " |i<-[1..]] .L.map format . L.map (solve . words) . tail . lines

I really liked Candy problem. First i solved it for small cases using brute force method which was not good enough for large test case. I noticed the sum was xor property and one of my friend told me the property of xoring the sequence of N numbers. If you xor N numbers and if it is zero then xor of any N-1 numbers will be equal to excluded one number.

import Data.List import Data.Bits part::[ Int ] -> String part xs = let ( x:xs' ) = sort xs t = foldr xor x xs' in if t /= 0 then "NO" else show ( sum xs' ) rInt::String->Int rInt = read main = interact $ unlines.zipWith (++) ["Case #" ++ ( show i ) ++ ": " | i<-[1..] ]. map part.(map.map) rInt.filter (\x -> length x /= 1) . map words . lines

Gorosort problem was totally my intuition . I was not sure about the correctness of algorithm but i remembered a online judge problem , probably http://acm.timus.ru/ , regarding the cycles in permutation.I worked with few test cases and it worked. Just count how may cycles are in the permutation.

import Data.List rInt :: String -> Integer rInt = read solve :: [ Integer ] -> Double solve xs = fromIntegral . length . filter (\x -> x == True ) . zipWith ( /= ) [1..] $ xs removeOdd :: [String] -> [ String ] removeOdd (_:x:xs) = x : removeOdd xs removeOdd _ = [] main = interact $ unlines.zipWith (++) ["Case #" ++ ( show i ) ++ ": " | i<-[1..] ]. map ( show . solve ) .( map . map ) rInt . map words . removeOdd . tail . lines

You can get the analysis of all the problems on code jam home. To get the solution of problem in different languages , check go-hero.

No comments yet.

## Leave a Reply