Any ideas?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | maomao90 | 162 |
3 | Um_nik | 162 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
7 | adamant | 156 |
8 | awoo | 155 |
9 | Dominater069 | 154 |
10 | TheScrasse | 153 |
Name |
---|
Try all permutations of array
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).
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
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?
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).
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.