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 asked 31 Jul '17, 11:44

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 1717 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 na[i] in second array using binary search.. So now it's Time Complexity would be of O(2^17log(2^17))number of testCases.. You can follow my this solution for approach.. answered 31 Jul '17, 12:17
Nice solution!
(31 Jul '17, 12:30)
@kauts_kanu nice solution!!! thanks
(31 Jul '17, 13:16)
(31 Jul '17, 13:17)

If you observe then every time A[i] = A[i1]+3*A[i2], 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...}. answered 31 Jul '17, 23:21
Awesome! It would be great if u can share your code.
(01 Aug '17, 22:57)
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.
(02 Aug '17, 04:24)
https://ideone.com/7tROO3 Here you go.
(02 Aug '17, 08:48)

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^(k1))+7(4^k1)/3 and a[2k+2]=6(4^(k1))+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(p) + 7(4p+c)/3 where p=4^(k11)+4^(k22)+... 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(p) + 7(4p+c)/3=n => (3n7c)/46=p. So check for c values ranging from 20 to 40 approx and if 3n7c is divisible by 46 then (3n7c)/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, n2,n7 and n9. This solution works in O(log n). answered 31 Jul '17, 13:32
2
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.
(31 Jul '17, 16:06)
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 (3n7c)/46 in base 4. If a digit in base 4 of the number (3n7c)/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
(01 Aug '17, 19:00)

Although I imagine @kauts_kanu's meetinthemiddle 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 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(i1, req_sumS[i]) if not x: x = recur(i1, 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. answered 31 Jul '17, 16:00
Can you please share your code?
(31 Jul '17, 17:31)
Sure, this was my mubmission: link
(31 Jul '17, 18:29)
I am still having a problem to grasp it fully. Would you like to explain it with relevant example?
(31 Jul '17, 19:35)
1
@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.. :)
(31 Jul '17, 22:20)
@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.
(02 Aug '17, 04:27)
