Given two arrays of integers $$$x$$$ and $$$y$$$, of length $$$n$$$, find a partition of indices $$${1, \ldots, n}$$$ such that you minimise the score, where the score of a partition $$$S_1, S_2$$$ is defined as $$$\max(\sum \limits_{j \in S_1} x[j], \sum \limits_{j \in S_2} y[j])$$$
just find the minimum score that can be achieved, I fancy a dp approach, any help is appreciated, thanks
EDIT : assume the sums of $$$x$$$ and $$$y$$$ are bounded above by $$$M$$$, then a solution with time complexity parametrised by $$$M$$$ might be good
Why don't you just iterate over both of the arrays, and for each index take the smaller value (min(x[i], y[i])) ???
Hi, sorry, I don't think that would work, consider $$$x = 2, 5, 3$$$ and $$$y = 3, 4, 2$$$
then you'd select $$$2$$$ from $$$x$$$ and $$$4, 2$$$ from $$$y$$$ giving you a score of $$$6$$$ whereas optimal is $$$5$$$, i.e. $$$2, 3$$$ from $$$x$$$ and $$$4$$$ from $$$y$$$.
What constraints are we looking for here? If I understand the problem correctly then $$$x=y$$$ seems strictly harder than the partition problem, which is NP-complete, so I don't think there's anything polynomial.
yes I believe so too, I took the problem from an OA and it didn't had any constraints mentioned, I think it may help to assume $$$max(\sum_i x[i], \sum_i y[i])$$$ is bounded by say $$$M$$$, then time complexity in terms of $$$M$$$ may be good