## SPOJ 8756. Shake Shake Shaky

SPOJ 8756. Shake Shake Shaky is similar to PIE. The idea is binary search. The second point of problem ** 2. All the candies which a student get must be from a single box only. ** is really important. Suppose you have 2 box each having 2 and 10 candy respectively and you have 2 students . You can’t distribute 6 candy to each because of this statement so each student can maximum have 5 candy from second box. See discussion regarding this problem on topcoder.Technically this code is not fully owned by me. I modified the code on topcoder forum and accepted. I will try to write a Haskell code for this problem.

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; int N,K,t,i,j,k,ar[50010]; int solve(int x) { k=K; for(i=N-1;i>=0;i--) { k-=(ar[i]/x); if(k<=0) return 1; } return 0; } int binarySearch() { int low=1,high=ar[N-1]+1; int mid; while(low<high) { mid=(low+high)>>1; if(solve(mid)) low=mid+1; else high=mid; } return low-1; } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&N,&K); for(i=0;i<N;i++) scanf("%d",&ar[i]); sort(ar,ar+N); printf("%d\n",binarySearch()); } return 0; }

Finally wrote Haskell solution but getting time limit exceed. Time limit is too strict for functional languages.

import Data.List import qualified Data.ByteString.Lazy.Char8 as BS import Data.Array bHelper ::Int -> Int -> Integer -> Integer -> Array Int Integer -> Bool bHelper cnt b k amt arr | cnt > b = if k<=0 then True else False | otherwise = if k <= 0 then True else bHelper ( cnt+1 ) b ( k - div ( arr!cnt ) amt ) amt arr {--bHelper k amt [] = if k<=0 then True else False bHelper k amt (x:xs) | k<=0 = True | otherwise = bHelper ( k - div x amt ) amt xs --} bSearch ::Array Int Integer -> Integer -> Integer bSearch arr k = bsearchHelp 1 ( arr!b + 1 ) where (a,b) = bounds arr bsearchHelp low high | low >= high = low - 1 | bHelper a b k mid arr = bsearchHelp ( mid + 1 ) high | otherwise = bsearchHelp low mid where mid = div ( low + high ) 2 solve::[Integer] -> BS.ByteString solve (n:k:xs) = BS.pack.show.bSearch ( listArray ( 0 ,length xs - 1 ) $ sort xs ) $ k readInt :: BS.ByteString -> Integer readInt x = case BS.readInteger x of Just ( i , _ ) -> i Nothing -> error " upseperable ints " format :: [BS.ByteString] -> [BS.ByteString] format [] = [] format (x:y:xs ) = BS.append ( BS.append x (BS.pack " ") ) y :format xs main = BS.interact $ BS.unlines . map ( solve .map readInt . BS.words) . format . tail . BS.lines

Advertisements

need help on the logic,how do we use binary search here and what does solve indicate.please help!!!

Comment by avinish | December 25, 2014 |