aman_naughty's blog

By aman_naughty, history, 4 weeks ago, In English,

Problem link: link

My code

Spoiler

We have 2 choices for each element either + or — I am considering both the choices and then picking the optimal one. In the code the dp[i].first = the minimum number of sign inversions dp[i].second = the optimal sum we achieve by either inverting this one or not;

It fails on array 10 4 3 2 1

Can someone point out why my aaproach is wrong?

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Slight advancement of subset sum problem

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

    Can you help me?

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

      You have to proceed as subset sum problem but instead of just storing if a particular sum is possible, store the minimum number of elements required to make that sum. Now iterate over all the possible sums. Let s be the current sum and t be the total one. Find the minimum positive value of (t — s). The answer will be the minimum elements required to make that sum (which you have already calculated.)