# how to solve (https://www.codechef.com/LOCJUL17/problems/CAVECOIN) ??

what i have tried…
for selecting the bats which are going to help him…i first sort the bats (first by end day and if it is same than one having lowest start will come first) then i filter the days and select those which is not in the range of above bat(like if the order is (3 5), (3 4), (2 3) i just skip (3 4)) and after doing this i greedily select the bats…now i have made a string with all the bats position set…and then simply multiply them.

After knowing positions of bat:

For 50 Points:

lets say k = "110"

ans positions of bats are: A = [2,3]; Then

Just make an array call it SUM of size highest element of A + size of k (I am caring about carry here and finding sum for ith position SUM array), with all elements 0; Then

SUM = [0,0,0,0,0,0]

now just update SUM array in range(shift, shift + size of k), because while shifting we are adding 0 at back so shifting will affect only this range of SUM [shift, shift+size of k], so after choosing 2 SUM will become:

SUM = [0,0,0,1,1,0] (I am taking k in opposite direction to make it clear for shifting and changing it binary in later part)

After second part it will become:

SUM = [0,0,0,1,2,1]

Then we can convert this array to binary string easily by just traversing from left to right and using carry. so answer will become:

ANS = “0001001” then reverse it again, because we reverse it initially for our convenience.

ANS = "1001000"

So basically this solution will give complexity of O(numberOfBatsPositions*size(k)) so, third case will pass because max numberOfBatsPositions can be 1000000(b upper limit) and size(k) <= 60

You can follow my solution here for same. Follow code after this line for above steps:

``````ll kLen = k.length();
``````

For 100 Points:

Now convert k into a signal. let’s make an array which stores pos of ones in it. Because once SUM array is calculated then we are done(because it was main time consuming part). For Example if:

k = “110” => reverseK = “011” (because for convenience we were taking SUM array reverse for clarity of shifting and addition later)

then onePos = [2,3] (1 Indexed) this is our first signal;

and second signal is shifting array. [2,3].

Now for calculating SUM we have to start SUM with all 0 and update it like this:

``````SUM = [0,0,0,0,0,0]
for i in onePos:
for j in shifts:
SUM[i+j] += 1
``````

but again this would be of same order as above. Now above operation can be done in O(NLog(N)) instead of O(N^2) by finding convolution using FFT. In simple terms you can find convolution using FFT in python like this:

``````import scipy.signal

def hist(X):
h = [0]*(max(X)+1)
for x in X:
h[x] += 1
return h
onePos = [2,4]
shifts = [1,3]
print scipy.signal.fftconvolve(hist(onePos),hist(shifts))
``````

here histogram is doing nothing but calculating frequencies of each element in array for FFT convolution.

I know this solution looks too messy, but hope it’s clear enough to understand.

thanks you very much!! i really appreciate the time and efforts in writing this …
one thing i want to know …suppose selected bats are (2, 3, 4) then if i make an array with these positions set.i.e (0111) and if the k is (110) then simply multiplying them can’t we get correct answer?
because i used same technique for 50 points as mentioned but afterward i think of this solution but this give me only 30 points…
i am unable to get my bug (http://ideone.com/fQzkmo) if possible then plz look into it !

What do you mean exactly when you are saying simply multiply them?? let’s say bats positions come 2,3,4. then you just multiply 234?? did not get you there.

by multiplication i mean binary multiplication

thanks !! i really appreciate the time and efforts in writing this …
i have the same doubt as asked by pk301…can you please clear this…