### harsh-apcr's blog

By harsh-apcr, history, 7 weeks ago,

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

• +10

 » 7 weeks ago, # |   -10 Why don't you just iterate over both of the arrays, and for each index take the smaller value (min(x[i], y[i])) ???
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +10 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$.
 » 7 weeks ago, # |   +10 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.
•  » » 7 weeks ago, # ^ |   0 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