starboy_9879's blog

By starboy_9879, history, 7 months ago, In English

We have an array of n elements (1 <= n <= 60) We have to determine whats the maximum sum subsequence possible that is less than or equal to a value k (1 <= k <= 10^18). At most 15 of the elements in array, either a[i] >= 2*a[j] or a[j] >= 2*a[i] where j is not equal to i (1 <= a[i] <= 10^17)

This problem was asked in Visa OA and later also in Expedia OA and both the times I couldn't manage to get all test cases passes. The constraints are very big for any regular knapsack approach to work. I thought of dividing the array such that first one will have all those at most 15 elements which shows that mentioned property and rest are the regular ones, since 15 is very less we can use something like bitmasking, so choosing k1 from that set and rest k-k1 from other set. But I couldn't make this idea work it will end up a bruteforce maybe I'm missing some observation. Please help

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

does anyone knows any better approach to this problem

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I see an $$$O(nk + n\log{n})$$$ solution to this. Sort the array. Notice that each element has to be at least twice the previous element. Let $$$dp_{i,j}$$$ denote the maximum sum such that only the first $$$i$$$ elements are used and the length is $$$j$$$. $$$dp_{i,j} = max(dp_{i-1,j}, dp_{l,j-1} + A_i)$$$ where $$$l$$$ denotes the maximum index such that $$$2\times A_l \le A_i$$$. $$$l$$$ can be maintained using two pointers. The answer is just $$$dp_{n,k}$$$

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fix number of choosen elements. Then, foreach there is a limited set of elements which can be choosen in that position, since it must be smaller than half of the next element.

So, the bigger the number of choosen elements gets, the smaller the number of element wich can be choosen at each position. Assume a[] is sorted. Use memoizaton for the (fairly small) array maxSum.

$$$maxSum[idx][0]=0;$$$

$$$maxSum[idx][i]=a[idx]+max(maxSum[nextPossible(idx)][i-1])$$$ // if nextPossible(idx) exists

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have link to original problem?

»
6 weeks ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

There is an error in the question he reported. It is

"Apart from" At most 15 of the elements in array, either a[i] >= 2*a[j] or a[j] >= 2*a[i] where j is not equal to i (1 <= a[i] <= 10^17)

It can be solved by seperating the 15 elements. The way to do that would be to sort the array in descending order and iterate. If some element is not half or less separate it. Now do brute force on the 15 elements via recursion(two options-choose or not choose for sum). There will be max 2^15 possibilities. At the recursive leaf try to minimize the difference by greedily choosing the descending halving numbers if it makes the sum less than or equal to k. Output the best match.

I think this is what they had in mind while setting the question and how the 15 number is chosen so that it is not too slow.

Time O(nlogn+(2^15)*n) i.e. O(nlogn) Space O(n+(2^16-1)) i.e. O(n)

Actually I faced the same problem in Hackerrank and passed all cases using this approach

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @a_natural, can you elaborate the method of splitting the array lets array is [1,2,3,4,5] and K is 9

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The array will be splitted as Arr1 = [5,2,1] Arr2 = [4,3] Whatever not matching <= element/2 is seperated.

      Brute force -

      0 then +5+2+1 =8

      3 then +5+1 =9

      4 then +5 =9

      4+3 then +2 =9

      Output is 9

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        So basically these different element are present in Arr1, and for all possible combination of these, check with the values of arr2 to get sum. But again chosing element from arr2 will be generating all possibilities ? . If array elements are disperse like [1,2,4,8,16,32,64,128] and so on , all these elements will be again in a single array

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          We do not want to generate all possibilities for the array with halving elements. We can have a greedy approach.

          Since the next element will only be half or less and so on, that means that the sum of all forthcoming elements will be less than the array element.

          Here comes the greedy approach, if we can fit the current element, we should since we will not find a better fit later on; else leave it.

          This approach is guaranteed to be optimal.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            can you please share your code for this question if possible. I've almost understood your code but that will make it more clear.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you please share the code?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you pls share the link to the hackerrank problem.