.-.-.-'s blog

Rearrange array elements to minimize the SUM of the subsegment with the largest sum
By .-.-.-, history, 7 weeks ago, In English

Any ideas?

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

»
7 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Try all permutations of array

→ Reply
»
7 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

In this problem it must be negative values in the array so, It is important to know that if you can achieve largest subsegment sum to be X then you can achieve largest subsegment sum equals to Y where Y >= X.

So you can make 2 vectors, first holding positive values and the other holding negative values and make binary search on the maximum subsegment sum.

To know if you can rearrange the elements so that the maximum subsegment sum is at most mid you can iterate over the positive values and start with variable sum is equal to 0 then you can choose to put positive value or negative value according to the state (the current maximum subsegment sum).

You can see this problem, It is similar to your idea, if the link dose not open, make sure to join here. and this is my solution (code).

→ Reply
  • »
    »
    7 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    6

    1 3 7 8 -17 -1

    breaks it

    your code would make 1 3 -17 7 -1 8 at mid = 9 which this doesnt satify

    however it can still work with mid = 9

    1 8 -17 3 -1 7

    ok i just read the other problem the differenece is you can still shuffle A and B here which screws up your algo

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

      Any ideas on how to solve the problem with the possibility of shuffling positive and negative values?

      Also, doesn’t the subsegment of last three values in your answer [3,-1,7] sum up to more than 9?

      → Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Two partition (given a multiset $$$S$$$ of positive integers, can you partition it into 2 sets with the same sum) can be reduced to this in the following way: let $$$t = sum(S)/2$$$ be the target sum. Then we can plug the multiset $$$\{t, t, t\} \cup S'$$$ into a solver for the blog's problem, where $$$S'$$$ contains the same elements as $$$S$$$ but with their signs flipped. The partition is possible iff the solver outputs $$$t$$$.

Since two partition is NP-complete, the blog's problem can't be solved in polytime unless P = NP (but there's probably some pseudopolynomial knapsack dp + binary search or whatever solution <- edit: turns out there isn't :p).

→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    If you do the same reduction, but then for 3-partition, so add a lot of $$$t$$$'s, and in particular reduce from the version where all elements are in $$$[t/4,t/2]$$$, the reduction also works. But 3-partition is NP-complete even if the weights are small (basically you encode the weights in unary). So a pseudopolynomial knapsack also seems out of the question.

    → Reply