My Weblog

Blog about programming and math

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

June 25, 2011 - Posted by | Programming | , ,

1 Comment »

  1. 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 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: