SRM 524

Although i could not participate in the single round match 524 but i solved the division two problems in Haskell using gettc. For more detail , see the editorial .

ShippingCubes .

module ShippingCubes where 

minimalCost :: Int -> Int
minimalCost n = minimum  [ i + j + k | i <- [ 1 .. n ] , j <- [ 1 .. n ] , k <- [ 1 .. n ] , i * j * k == n ]

MagicDiamonds

module MagicDiamonds  where 

prime :: [ Integer ] 
prime = 2 : 3 : filter isPrime [ 2 * k + 1 | k <- [ 1 .. ] ] 

isPrime :: Integer -> Bool  
isPrime n 
	| n <= 1 = False 
	| otherwise =  all ( ( /= 0 ).mod n ) . takeWhile ( <= ( truncate . sqrt . fromIntegral $ n ) ) $ prime 

minimalTransfer :: Integer -> Integer
minimalTransfer n 
  | n == 3 = 3 
  | isPrime n = 2 
  | otherwise = 1 

MultiplesWithLimit. For this problem , see the post of Smart.Coder.

module MultiplesWithLimit where 
import Data.List
import qualified Data.Sequence as S
import qualified Data.IntMap as M 

minMultiples :: Int -> [Int] -> String
minMultiples n forbiddenDigits =  format ret  where 
	lst = [ ( show i , mod i n ) | i <- [ 1 .. 9 ] , notElem i  forbiddenDigits ] ;
	mp = M.fromList . zip  ( map snd lst ) $ [ 1,1..]
	ret = helpMinMultiples ( S.fromList lst )  mp where 
	 helpMinMultiples t mp' 
	   | S.null t = "IMPOSSIBLE"
	   | snd x == 0 = fst x 
	   | otherwise = helpMinMultiples xs'' mp'' where 
		( xs'' , mp'' )  = lookupfunction x xs mp' [ 0..9 ] forbiddenDigits n 
		(x S.:< xs ) = S.viewl t 

lookupfunction :: ( String , Int ) -> S.Seq ( String , Int )  -> M.IntMap Int -> [ Int ] -> [ Int ] -> Int -> 
		( S.Seq ( String , Int )  , M.IntMap Int ) 

lookupfunction _ xs mp' [] _ _ = ( xs , mp' ) 
lookupfunction x xs mp' ( y : ys )  forbid n 
 |  elem y forbid = lookupfunction x xs mp' ys forbid n 
 |  otherwise = case M.lookup ( mod (  snd x  * 10 + y ) n ) mp' of 
		 Nothing -> lookupfunction x ( xs S.|>  ( fst x ++ show y , mod (  snd x  * 10 + y ) n ) ) mp'' ys forbid n 
		 	    where mp'' = M.insert ( mod ( snd x  * 10 + y ) n ) 1 mp' 
		 _       -> lookupfunction x xs mp' ys forbid n  			

format :: String -> String 
format xs
 | xs == "IMPOSSIBLE" = "IMPOSSIBLE" 
 | length xs < 9 = xs 
 | otherwise = take 3 xs ++ "..." ++ drop  ( len  - 3 ) xs ++ "(" ++ show len ++" digits)"  where 
			len = length xs 						

SRM 385 – Division II, Level Three

Gettc is excellent software for practicing topcoder problems offline and specially in Haskell. I just wrote solution for SRM 385 Problem [ requires registration but its worth and excellent place for programmers ]. You can see the editorial for SRM 385. Haskell source code.

module SummingArithmeticProgressions where  

canRep :: Int -> Int -> Int -> Bool 
canRep a b n = canRephelp 1 a b n where 
	canRephelp x a b n 
	  | x > b = False
	  | n <= a * x = False
	  | mod ( n - a * x ) b == 0 = True
	  | otherwise = canRephelp  ( succ x ) a b n 


howMany :: Int -> Int -> Int -> Int
howMany left right k =  ans   where 
	a = k 
	b = div ( k * ( k - 1 ) ) 2
	d = gcd a b
	a' = div a d 
	b' = div b d
	left' = div ( left + d - 1 ) d 
	right' = div right d 
	ans = helphowMany a' b' left' right'  0
	

helphowMany :: Int -> Int -> Int -> Int -> Int -> Int
helphowMany a b left right cnt
	| and [ left <= right , left < 2 * a * b ] = if canRep a b left 
						      then helphowMany a b ( succ left ) right ( succ cnt )  
						       else helphowMany a b ( succ left ) right cnt 
	| otherwise = cnt + right - left + 1