Edit: I have realized that this blog has been sent quite a lot on discord servers, so I am adding a content page at the start to help organize this blog better.

Prerequisites

Let us first define the classical knapsack, unbounded knapsack and subset sum problems.

Subset Sum

There are N$N$ items. The i$i$-th item has weight wi$w_i$. Find a set S$S$ such that ∑i∈Swi=C$\sum _{i\in S}{w}_i=C$.

Knapsack

There are N$N$ items. The i$i$-th item has weight wi$w_i$ and value vi$v_i$. Find a set S$S$ such that ∑i∈Swi≤C$\sum _{i\in S}{w}_i\le C$ and ∑i∈Svi$\sum _{i\in S}{v}_i$ is maximized.

Unbounded Knapsack

There are N$N$ items. The i$i$-th item has weight wi$w_i$ and value vi$v_i$. Find a multiset S$S$ such that ∑i∈Swi≤C$\sum _{i\in S}{w}_i\le C$ and ∑i∈Svi$\sum _{i\in S}{v}_i$ is maximized.

You should know how to do both versions of knapsack in O(NC)$O(NC)$ and subset sum in O(NC32)$O(\frac{NC}{32})$ before reading this blog.

In this blog post, I will just show some results that speed up the above problems for special cases.

Content of this Blog

I would like to thank:

• tfg for his helpful discussions, digging through papers and implementing SMAWK.
• maomao90 for proofreading.

Subset Sum Speedup 1

There are N$N$ items. The i$i$-th item has weight wi$w_i$. Let ∑i=1Nwi=C$\sum _{i=1}^N{w}_i=C$. For each k∈[1,C]$k\in [1,C]$, can we find a set S$S$ such that ∑i∈Swi=k$\sum _{i\in S}{w}_i=k$?

It turns out we can do this in O(CC√32)$O(\frac{C\sqrt{C}}{32})$.

Let us first consider an algorithm that seems like it is O(CC√logC32)$O(\frac{C\sqrt{C}\log C}{32})$. We will group items of equal weights together, so we will get M$M$ tuples of the form (wi,occi)$(w_i,oc{c}_i)$ where there are occi$oc{c}_i$ occurrences of wi$w_i$ in the original items. For each tuple, we will decompose it into powers of 2$2$. For example, for (wi,15)$(w_i,15)$, we will decompose it into {wi,2wi,4wi,8wi}$\{w_i,2w_i,4w_i,8w_i\}$, for (wi,12)$(w_i,12)$, we will decompose it into {wi,2wi,4wi,5wi}$\{w_i,2w_i,4w_i,5w_i\}$. If you think about these things as binary numbers, it is not too difficult to see that we will get the same answers when we use these new weights instead of the original weights.

Furthermore, it is well known that if you have some weights that sum to C$C$, then there are only 2C−−−√$\sqrt{2C}$ distinct weights. So we can already determine that M≤2C−−−√$M\le \sqrt{2C}$. Since occi≤C$oc{c}_i\le C$, we can figure out that each tuple will contribute logC$\log C$ elements. Giving up a simple upper bound of O(CC√logC32)$O(\frac{C\sqrt{C}\log C}{32})$.

However, this is actually bounded by O(CC√32)$O(\frac{C\sqrt{C}}{32})$ [1]${}^{[1]}$. Consider the set of tuples that contribute a weight k⋅wi$k\cdot w_i$, we will call this set Sk$S_k$. We want to show that ∑k≥1|Sk|=O(C−−√)$\sum _{k\ge 1}|S_k|=O(\sqrt{C})$. Firstly, we note that most of the new weights will be a multiple of 2k$2^k$ of the original weight, for each tuple, it will only contribute at most 1$1$ new weight that is not a power of 2$2$. Therefore, if we can show that ∑k=2z|Sk|=O(f(C))$\sum _{k=2^z}|S_k|=O(f(C))$, then

Unable to parse markup [type=CF_MATHJAX]

It is obvious that ∑i∈Skwi≤Ck$\sum _{i\in S_k}{w}_i\le \frac{C}{k}$ and we can conclude that |Sk|≤Ck−−√$|S_k|\le \sqrt{\frac{C}{k}}$.

Therefore, ∑k=2z|Sk|≤∑z≥02C2z−−−√=2C−−−√(∑z≥012z√)=O(C−−√)$\sum _{k=2^z}|S_k|\le \sum _{z\ge 0}\sqrt{\frac{2C}{2^z}}=\sqrt{2C}\left(\sum _{z\ge 0}\frac{1}{\sqrt{2^z}}\right)=O(\sqrt{C})$.

However, there is a simpler way to do this [2]${}^{[2]}$. Consider processing the weights from smallest to largest, with an initially empty list W′$W^{\prime }$ as the list of our new weights. Suppose there are occ$occ$ occurrences of the smallest weight w$w$. If occ$occ$ is odd, we add occ−12$\frac{occ-1}{2}$ occurrences of 2w$2w$ to the original weights and 1$1$ occurrence of w$w$ to W′$W^{\prime }$. The case if occ$occ$ is even is similar, we add occ−22$\frac{occ-2}{2}$ occurrences of 2w$2w$ to the original weights and 2$2$ occurrence of w$w$ to W′$W^{\prime }$.

It is not hard to see that |W′|≤22C−−−√=O(C−−√)$|W^{\prime }|\le 2\sqrt{2C}=O(\sqrt{C})$, since we only add at most 2$2$ occurences of some weight to W′$W^{\prime }$.

Problems:

• CC MINFUND (testcases are super weak)
• CF755F
• CC TREUPS↵

Subset Sum Speedup 2

There are N$N$ items. The i$i$-th item has weight wi≤D$w_i\le D$. Can we find a set S$S$ such that ∑i∈Swi=C$\sum _{i\in S}{w}_i=C$?

We will solve this in O(ND)$O(ND)$ [3]${}^{[3]}$. Firstly, if ∑wi<C$\sum w_i<C$, the answer is obviously no, so we will ignore that case.

Let us find the maximal k$k$ such that ∑i=1kwi<C$\sum _{i=1}^k{w}_i<C$. The basic idea is that we initially have an answer of w1+w2+…+wk$w_1+w_2+\dots +w_k$, then we can either subtract wi$w_i$ for i≤k$i\le k$ or add wi$w_i$ for i>k$i>k$ in some order such that the cost of our items is in the range [C−D,C+D]$[C-D,C+D]$, which is not too hard to show constructively. The proof sketch is just: if the current weight is more than C$C$, remove something, otherwise add something.

Let us define can(total,l,r)$can(total,l,r)$ as a dp function that returns true iff there exists λl,λl+1,…,λr∈[0,1]${\lambda }_l,{\lambda }_{l+1},\dots ,{\lambda }_r\in [0,1]$ such that ∑i=1l−1wi+∑i=lrλiwi=total$\sum _{i=1}^{l-1}{w}_i+\sum _{i=l}^r{\lambda }_i{w}_i=total$, where total∈[C−D,C+D]$total\in [C-D,C+D]$.

Notice that can(total,l,r)=true$can(total,l,r)=true$ implies that can(total,l−1,r)=true$can(total,l-1,r)=true$, this means that can$can$ is monotone on the dimension l$l$. Therefore, let us define a new dp function dp(total,r)$dp(total,r)$ that stores the maximal l$l$ such that can(total,l,r)=true$can(total,l,r)=true$.

Furthermore, can$can$ is monotone on the dimension r$r$, so dp(total,r)≤dp(total,r+1)$dp(total,r)\le dp(total,r+1)$.

Let us consider the transitions.

From dp(total,r)=l$dp(total,r)=l$, we can extend r$r$, transitioning to dp(total+wr+1,r+1)$dp(total+w_{r+1},r+1)$ or dp(total,r+1)$dp(total,r+1)$. We can also extend l$l$ and transition to dp(total−wl′,r)=l′$dp(total-w_{l^{\prime }},r)=l^{\prime }$ for l′<l$l^{\prime }<l$. However, this transition would be O(N)$O(N)$ per state, which is quite bad.

However, it would only make sense to transition to dp(total−wl′,r)=l′$dp(total-w_{l^{\prime }},r)=l^{\prime }$ for dp(total,r−1)≤l′<dp(total,r)=l$dp(total,r-1)\le l^{\prime }<dp(total,r)=l$, otherwise this case would have been covered by another state and there would be no need for this transition. Since dp(total,r)≤dp(total,r+1)$dp(total,r)\le dp(total,r+1)$, the total number of transitions by extending l$l$ is actually bounded by O(ND)$O(ND)$ using amortized analysis.

Therefore, our dp will have O(ND)$O(ND)$ states with a total of O(ND)$O(ND)$ transitions.

Actually there is a scammy way to do this. Similarly, we find the maximal k$k$ such that ∑i=1kwi<C$\sum _{i=1}^k{w}_i<C$, then we want to solve the subset sum problem with the weights {−w1,−w2,…,−wk,wk+1,…,wN}$\{-w_1,-w_2,\dots ,-w_k,w_{k+1},\dots ,w_N\}$ and sum C−∑i=1kwi$C-\sum _{i=1}^k{w}_i$.

Let us randomly shuffle the list of weights and pretend C−∑i=1kwi$C-\sum _{i=1}^k{w}_i$ is very small. Then this can be viewed as a random walk with 0$0$ sum. The length of each step is bounded by D$D$, so we can expect O(DN−−√)$O(D\sqrt{N})$ deviation from the origin (my analysis is very crude). Using bitsets, we can obtain a complexity of O(NDN√32)$O(\frac{ND\sqrt{N}}{32})$ which is probably good enough.

The paper also mentions a way to generalize this technique to knapsack where weights are bounded by D$D$ and values are bounded by V$V$ in O(NDV)$O(NDV)$ but I think it is not a significant speedup compared to the usual knapsack to be used in competitive programming.

Problems:

• GP of Bytedance 2020 F
• ABC221G
• NCPC21E (Thank you nigus)

Knapsack Speedup 1

Consider SG NOI 2018 Prelim knapsack.

The editorial solution is to only consider O(SlogS)$O(S\log S)$ items, since only Sw$\frac{S}{w}$ items for a certain weight w$w$ can be used, to get a complexity of O(S2logS)$O(S^2\log S)$. But I will discuss a slower O(NS)$O(NS)$ solution.

Let dp(i,j)$dp(i,j)$ be the maximum value of items if we only consider the first i$i$ types using a weight of j$j$.

Then our transition would be dp(i,j)=max0≤k≤Ki(dp(i−1,j−k⋅Wi)+k⋅Vi)$dp(i,j)=\underset{0\le k\le K_i}{max}(dp(i-1,j-k\cdot W_i)+k\cdot V_i)$. If we split each dp(i,j)$dp(i,j)$ into the residue classes of j%Wi$j\mathrm{\%}{W}_i$, it is easy to see how to speed this up using the sliding deque trick or using an RMQ.

Now, let us talk about a more general speedup. But first, we will have to introduce a convolution that appears frequently in dp.

(max,+) convolution

The problem statement is this: Given 2$2$ arrays A$A$ and B$B$ of length N$N$, find an array C$C$ of length 2N−1$2N-1$ such that Ci=maxj+k=i(Aj+Bk)$C_i=\underset{j+k=i}{max}(A_j+B_k)$.

Doing this in O(N2)$O(N^2)$ is easy. Can we do better? It seems that doing this faster is a really hard problem and so far the fastest known algorithm is a very scary O(n2logn)$O(\frac{n^2}{\log n})$ or O(n2(loglogn)3(logn)2)$O(\frac{n^2(\log \log n{)}^3}{(\log n{)}^2})$, which does not seem practical for competitive programming.

Note that (max,+)$(max,+)$ and (min,+)$(min,+)$ convolution are not too different, we can just flip the sign. In the rest of this section, I will use (min,+)$(min,+)$ convolution to explain things.

First, we note that if both arrays A$A$ and B$B$ are concave, then we can do this convolution in O(N)$O(N)$ time [5],[6]${}^{[5],[6]}$. The basic idea is we can consider the union of the slopes of the lines {Ai−Ai−1}∪{Bi−Bi−1}$\{A_i-A_{i-1}\}\cup \{B_i-B_{i-1}\}$ and sort them to get the slopes of C$C$.

Another way to reason about this is using epigraphs (fancy word for colour everything above the line), which I find more intuitive. Because if we take the epigraph of A$A$ and B$B$, we get 2$2$ convex polygons, taking their Minkowski sum gets us the epigraph for C$C$ and finding Minkowski sum on convex polygons is well known as taking the union of their edges, which is why this is also known as the Minkowski sum trick.

This speedup can be used in several dp problems such as ABC218H and JOISC18 candies. Furthermore, this can be abused in several dp problems where we can think of slope trick as (min,+)$(min,+)$ convolution so we can store a priority queue of slopes such as in SG NOI 2021 Finals password. Another more direct application is CF1609G.

Anyways, we can actually solve (min,+)$(min,+)$ convolution quickly with a weaker constraint that only B$B$ is convex.

First, let us discuss a O(NlogN)$O(N\log N)$ method.

Define a i$i$-chain as the line segment with points {(i+1,Ai+B1),(i+2,Ai+B2),(i+3,Ai+B3),…}$\{(i+1,A_i+B_1),(i+2,A_i+B_2),(i+3,A_i+B_3),\dots \}$. Then I claim that 2$2$ chains only intersect at a point, which is the sufficient condition for using Li Chao tree to store these lines [7]${}^{[7]}$.

Let us prove that this is actually true. Let the equation for the i$i$-chain be fi(x)$f_i(x)$, so fi(x)$f_i(x)$ is a convex function. We want to show that for g(x)=fi(x)−fj(x)$g(x)=f_i(x)-f_j(x)$, there exists k$k$ such that g(x)<0$g(x)<0$ for x<k$x<k$ and 0≤g(x)$0\le g(x)$ for k≤x$k\le x$ whenever i<j$i<j$.

g(x)=(Ai+Bx−i)−(Aj+Bx−j)=(Bx−i−Bx−j)+(Ai−Aj)$g(x)=(A_i+B_{x-i})-(A_j+B_{x-j})=(B_{x-i}-B_{x-j})+(A_i-A_j)$.

Consider g(x+1)−g(x)=(Bx+1−i−Bx−i)−(Bx+1−j−Bx−j)$g(x+1)-g(x)=(B_{x+1-i}-B_{x-i})-(B_{x+1-j}-B_{x-j})$. Recall that B$B$ is convex (i.e. Bx+1−Bx≥Bx−Bx−1$B_{x+1}-B_x\ge B_x-B_{x-1}$). Since we have assumed that i<j$i<j$, we can conclude that (Bx+1−i−Bx−i)≥(Bx+1−j−Bx−j)$(B_{x+1-i}-B_{x-i})\ge (B_{x+1-j}-B_{x-j})$. Therefore, g(x+1)−g(x)≥0$g(x+1)-g(x)\ge 0$, i.e. g$g$ is a (non-strict) increasing function.

Therefore, we can insert all chains into a Li Chao Tree and find the convolution in O(NlogN)$O(N\log N)$.

Now, we will consider an O(N)$O(N)$ method. We will have to use the SMAWK algorithm [8]${}^{[8]}$ which I will not explain because the reference does a better job at this than me. Here I will actually use (max,+)$(max,+)$ convolution to explain.

Anyways, the result we will be using from SMAWK is that given an N×M$N\times M$ matrix X$X$ that is totally monotone, we can find the minimum value in each row.

A matrix is totally monotone if for each 2×2$2\times 2$ sub-matrix is monotone i.e. for (acbd)$\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$:

• If c<d$c<d$, then a<b$a<b$
• If c=d$c=d$ then a≤b$a\le b$

The way I think about this is consider the function σ(x)=⎧⎩⎨1,0,−1,if x>0if x=0if x<0$\sigma (x)=\{\begin{array}{ll}1,& \text{if }x>0\\ 0,& \text{if }x=0\\ -1,& \text{if }x<0\end{array}$. We pick 2$2$ columns 1≤i<j≤M$1\le i<j\le M$ and consider writing down [σ(H1,i−H1,j),σ(H2,i−H2,j),…,σ(HN,i−HN,j)]$[\sigma (H_{1,i}-H_{1,j}),\sigma (H_{2,i}-H_{2,j}),\dots ,\sigma (H_{N,i}-H_{N,j})]$. Then this sequence should be increasing when i<j$i<j$.