You are not logged in. Please login at www.codechef.com to post your questions!

×

LOCJUL17/AMITNITI

2
2

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
link to my solution

asked 31 Jul '17, 11:44

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

edited 31 Jul '17, 11:49


10

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^17log(2^17))number of testCases..

You can follow my this solution for approach..

link

answered 31 Jul '17, 12:17

kauts_kanu's gravatar image

5★kauts_kanu
1.1k110
accept rate: 19%

Nice solution!

(31 Jul '17, 12:30) dhruvsomani3★

@kauts_kanu nice solution!!! thanks

(31 Jul '17, 13:16) phantomhive4★
(31 Jul '17, 13:17) kauts_kanu5★

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. :)

link

answered 31 Jul '17, 23:21

ista2000's gravatar image

4★ista2000 ♦
2.4k722
accept rate: 20%

edited 31 Jul '17, 23:38

Awesome! It would be great if u can share your code.

(01 Aug '17, 22:57) dishant_185★

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) meooow ♦6★
(02 Aug '17, 08:48) ista2000 ♦4★

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(p) + 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(p) + 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).

link

answered 31 Jul '17, 13:32

rumblefool's gravatar image

6★rumblefool
513
accept rate: 0%

edited 01 Aug '17, 19:04

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) meooow ♦6★

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

(01 Aug '17, 19:00) rumblefool6★

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.

link

answered 31 Jul '17, 16:00

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

edited 31 Jul '17, 16:09

Can you please share your code?

(31 Jul '17, 17:31) bansal12325★

Sure, this was my mubmission: link

(31 Jul '17, 18:29) meooow ♦6★

I am still having a problem to grasp it fully. Would you like to explain it with relevant example?

(31 Jul '17, 19:35) bansal12325★
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) kauts_kanu5★

@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.

(02 Aug '17, 04:27) meooow ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×135

question asked: 31 Jul '17, 11:44

question was seen: 906 times

last updated: 02 Aug '17, 08:48