My Weblog

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

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