1
$\begingroup$

For a finite sequence of $N$ positive integers $a_1, a_2,.., a_N$ let us define its weight as $w (\{a_i\}) = \log(N) \cdot \sum_{1}^{N}{a_i}$.

I want to partition such sequence into $K$ non-empty subsequencies
$\{a_1, a_2,.., a_{j1}\}, \{a_{j1+1}, a_{j1 + 2},.., a_{j2}\},.., \{a_{j(K-1)+1}, a_{j(K-1)+2},.., a_{N}\}$
in a way that their weights are close to equal.
Or, more formally, I want to minimize maximum weight in resulting subsequences: $\max w (\{a_i\}_j) \rightarrow \min$.

I need a solution that can be calculated in $O(N \log N)$ time.
I don't need a precise solution, numerical and approximate one will suffice.

$\endgroup$
2
  • $\begingroup$ Is the weigth actually $w(\{a_i\}) = \sum_{i=1}^N a_i \log(N)$ or is it $w(\{a_i\}) = \sum_{i=1}^N a_i \log(i)$? Both have pretty simple solutions I think. Also by subsequences, do you mean continous subsequences? $\endgroup$
    – Yuumita
    Mar 10, 2023 at 11:53
  • $\begingroup$ @Yuumita I rewrote the formula. Yes, I mean continous subsequences. $\endgroup$ Mar 10, 2023 at 12:09

2 Answers 2

0
$\begingroup$

Well the $\log N$ in the formula doesn't really affect our strategy. In general even if you had $w(a)=\sum_{i}a_if(i)$ with $f(i) >0$ the strategy would be the same, just with doing the following for the array $a_i' = a_i f(i)$. Keep in mind that the details and implementations are different depending on how you treat the $\log N$ coefficient. We will suppose that it is part of $a_i$.

Rewriting the problem

We wish to parition $a$ in $K$ segments $S_1\dots S_K$ such that $S_1=[1, i_1]=[i_0,i_1], S_2=[i_1+1,i_2],\dots,S_K =[i_{K-1}, i_K]=[i_{K-1}, N]$ such that $\max_{i=1}^Kw(S_i)$ is minimum in $O(N\log N)$. Where $w(T) =\sum_{i\in T}a_i$.

Solution: Binary search on the maximum weight. In that way you can find the minimum maximum weight, which is what you want to find. It suffices to be able to check if $a$ can be partitioned in $K$ continuous subsequences each having weight smaller than $m\in\mathbb{R}$, i.e find if the minimum maximum is not greater than $m$, in $O(N)$.

Finding if the minimum maximum is not greater than $m$

This is a very simple problem which can be solved greedily in $O(N)$.

If there is an element $a_i > m$ it can't happen. Now suppose $a_i\leq m$, $\forall i\in[N]$. Also notice that, since we must have $K\leq N$ and $a_i > 0$, if we can partition tha array in $K'\leq K$ parts such that their maximum is not greater than $m$, we can also parition them in $K$ such parts (just start seperating elements from the $K'$ partitions).

Let's say you have partitioned $a$ in segments $[1,i_1],[i_1+1,i_2],\dots[i_{K-1}+1, i_K]$ named $S_1,\dots S_K$. If $w(S_1) + w(\{a_{i_1 +1}\})\leq m$ then $S_1\cup \{a_{i_1+1}\}, S_2\setminus \{a_{i_1+1}\}, S_3, \dots ,S_k$ is also a valid solution. This implies that we can try and fit as many elements as we can in each part. If we can fit all the parts in not greater than $K$ segments, then we are done.

We have solved the problem in $O(N\log N)$ time ($O(N)$ for checking each of the $O(\log N)$ values we will have to check).

$\endgroup$
5
  • $\begingroup$ Why do you think that $\log N$ doesn't really affect the solution? If the sequence is large and integers are of high variance then the solution that takes the logarithm multiplier into account will deviate greatly from yours. $\endgroup$ Mar 10, 2023 at 12:49
  • $\begingroup$ @AndreyGodyaev I am not really describing the solution, I am describing the strategy. My solution works for any $a\in\mathbb{R}_+^N$ with weigths $w_a(I)=\sum_{i\in I}a_i$ so setting $b_i := a_i \log N$ you get a sequence $b\in\mathbb{R}_+^N$ with weights $w_b(I) = \sum_{i\in I}b_i = \log N\sum_{i\in I}a_i$ (which is the problem you have stated). What I am trying to say is that your problem is equivalent to finding a way to partition a sequence to continous subsequences such that the maximum sum is minimized (the problem itself isn't depended on the $\log N$ factor). $\endgroup$
    – Yuumita
    Mar 10, 2023 at 13:27
  • $\begingroup$ my problem is not equivalent to the minimization of maximum sum because $\log N$ is not a constant multiplier, it depends on each subsequence length. $\endgroup$ Mar 10, 2023 at 13:36
  • $\begingroup$ @AndreyGodyaev Well obviously you don't clarify that since you're using $N$ for the length of the sequence. I am sorry for my previous answer then but I don't really have the time to answer the new one, however I am fairly certain one can prove that again the best tactic is binary search + greedy. Meaning that you still binary search on $m$ and for the $m$ you try to fit as many elemnts from left to right as you can (when you start a segment at $i$ then you find the largest $j$ such that $w([i,j])=\log(j-i+1)\sum_{k=i}^ja_k \leq m$ which you can easily do until the end of the array in $O(N)$) $\endgroup$
    – Yuumita
    Mar 10, 2023 at 15:22
  • $\begingroup$ definition of $w$ does not contain any ambiguity. $\endgroup$ Mar 10, 2023 at 15:36
0
$\begingroup$

Let $t$ be a threshold. I'll show how to test whether or not there exists a solution, where all subsequences have weight $\le t$, in $O(N)$ time.

Now use binary search on $t$, to find the smallest $t$ such that the answer is "yes there exists a solution". Binary search takes logarithmically many iterations, and each iteration takes $O(N)$ time. Assuming the sum of the $a_i$'s is not too large (specifically, polynomial in $N$), the whole procedure can finish in $O(N \log N)$ time, or something similar.

So how do you test whether there exists a solution where subsequences have weight $\le t$? Use a greedy algorithm. Add as many items as possible to the first subsequence, without exceeding weight $t$. Then do the same for the second subsequence, and so on. No need to backtrack. If in the end you find a solution where all subsequences have weight $\le t$, and you need $\le K$ subsequences, then the answer is "yes there exists a solution". Otherwise the answer is "no there does not exist a solution".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .