Can any one help me with this question , in my solution i tried the brute force way and generated every possible subse
which is 2^30 which wont pass the time limit for 100 points.
thanks
2 Likes
You have to use brute force here… but in little smart way… 
you can see that you can solve till 2^22 using brute force by generating all possible sums… and you can also see that 33th element of series should be sufficient because N<=10^10 and 33th element of series would be greater that 10^10. But 2^33 summations cannnot be calculated in given time limit. So…
Here is trick:
Just divide series of 34 elements into two parts of 17-17 elements… now all summations that can be formed by both of them are two arrays of size 2^17. sort them… And iterate over one array and find n-a[i] in second array using binary search… So now it’s Time Complexity would be of O(2^17*log(2^17))*number of testCases…
You can follow my this solution for approach…
10 Likes
Nice solution!
I did the problem in O(log n) time complexity. My solution
Observe that any general term of the sequence can be defined as a[2k+1]=6*(4^(k-1))+7*(4^k-1)/3 and a[2k+2]=6*(4^(k-1))+7*(4^k+2)/3 for k>=1. So if we consider summation of any n number of such terms observe that the sum S=6*§ + 7*(4p+c)/3 where p=4^(k1-1)+4^(k2-2)+… which will occur in the n terms chosen and c can take values between -n and 2n depending if we chose even numbered term or odd. So 6*§ + 7*(4p+c)/3=n => (3n-7c)/46=p. So check for c values ranging from -20 to 40 approx and if 3n-7c is divisible by 46 then (3n-7c)/46 in base 4 should contain only the digits 0 1 or 2. Note that this does not work if the numbers 2 or 7 are also a part of the subset whose sum is n. So check for n, n-2,n-7 and n-9. This solution works in O(log n).
5 Likes
Although I imagine @kauts_kanu’s meet-in-the-middle approach was the intended solution, there is a simple optimization to the standard recursive \mathcal{O}(2^n) subset sum code that can solve this. Let S be the sequence. Generate Z such that Z_i=\sum_{j=0}^i S_j. Then at any index i if the required sum is greater then Z_i, immediately return False.
function subsetsum(i, req_sum):
if req_sum==0:
return True
if i<0 or req_sum<0 or req_sum>Z[i]:
return False
x = recur(i-1, req_sum-S[i])
if not x:
x = recur(i-1, req_sum)
return x
This works here because the sequence S increases very fast, and there are large gaps where making the subset sum is impossible. For example, S_{28}=1029002579 and Z_{27}=686001750, so all numbers from 686001751 to 1029002578 cannot be made, and the code can quickly detect this.
5 Likes
Awesome! I initially tried to find a formula but gave up. Also can you share your code via pastebin/ideone? The contest solutions haven’t been made visible yet.
2 Likes
Can you please share your code?
I am still having a problem to grasp it fully. Would you like to explain it with relevant example?
@bansal1232 When you applying brute force you could return false in recursive solution as soon as you find sum is greater than n. And start recursion from biggest element so that this situation will arrive early… Thats all what he is saying…
1 Like
If you observe then every time A[i] = A[i-1]+3*A[i-2], it is a super increasing sequence. A super increasing sequence is a sequence in which each term is greater than the sum of all the terms that precede it. A super increasing sequence has a nice property that you can solve the subset sum problem using greedy and not DP. For example, powers of 2, i.e, {1, 2, 4, 8, 16…} and also normal coin dinomination, i.e, {1, 2, 5, 10, 20, 50…}.
Proof: Suppose you can take the ith term to make the sum S, if you don’t take it into account, all the terms that precede it combined will not suffice because ith term is greater than the sum of all the terms that precede it.
So, what you can do here is try to do greedy but in a different way. Take the first 32 terms of the sequence. Then you can consider adjacent pairs. This is because the +7 terms are not super increasing but pairwise they are. If you can take both the numbers of the pair, then you have to take them, else if you can take any one you can consider either one of them else skip the pair and consider the previous pair. The time complexity for this will be O(2^N) where N = 16 because there are 16 pairs in all and you are considering them one at a time.
Feel free to coment any queries if any.
6 Likes
There are a slight bit more details that I left yesterday. You also need to check all the possible values of c. You’ll need to figure that out using the representation of (3n-7c)/46 in base 4. If a digit in base 4 of the number (3n-7c)/46 is 1, it means you can either add -1 or add 2 to c and the digit 2 means you must add 1 to c (since one term will contain -1 and one term will contain 2). My solution: https://pastebin.com/QtLVe9NG
Awesome! It would be great if u can share your code.
Nice, didn’t think of that. I suspect the complexity of my optimized naive algorithm can also be be shown to be the same as your method, since they use the same property of the sequence to improve performance.
@bansal1232 Z is nothing but the prefix sum of S. If the required sum is greater that Z_i, that means even if we take all S_0 to S_i we cannot make up the sum.
For example, if the required sum is 1029002578, all S_i : i \ge 28 are greater then the sum. At i=27, normally we would recurse further into (26, 1029002578) and (26, 1029002578-S_{27}), but since 1029002578>Z_{27}, we can safely return False.