Dynamic sum-over-subset dp with element addition and extraction in O(2^(k/2)) time

Правка en1, от Peter-007, 2024-03-23 14:37:12

About two months ago I invented this (probably well known though) when trying to solve problem that I made. Haven't seen any blogs on this, so decided to make one.

Main idea is that we can use meet-in-the-middle here.

In an naive algorithm to insert a value or erase a value, we will create a vector of size $$$2^k$$$, where $$$dp_{mask}$$$ denotes how many elements with such mask are there, and just do $$$dp_{mask}++$$$ (or do $$$dp_{mask}--$$$), so it will take $$$O(1)$$$ time, and to make a query we will iterate over all submasks of $$$mask$$$ in $$$O(2^k)$$$. It seems obvious that we can balance this.

So we can split bits in half, to add a value or erase it we will iterate over all UPmasks (in UPmask, we are replacing some zeroes with ones) of the first half of the bits (name it $$$maskup$$$) and add the second half here (name it $$$masksec$$$), so do $$$dp_{maskup+masksec}++$$$ (in case we want to add a value, but if we want to erase, substract one).

To make a query we will do an inverse of that: first half is fixed, and we iterate over all SUBmasks of the second one.

The only issue here is that we still use $$$O(2^k)$$$ memory, we can have map or unordered_map, but that's pretty slow, or alternitevly some clever of vectors.

Code (using vectors with O(2^(k/2)) memory)
Problem (some other solutions not using that idea might exist)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru3 Русский Peter-007 2024-03-23 15:07:31 4 Мелкая правка: 'ь тип $1$ to $k$ $(1 \' -> 'ь тип $1$ до $k$ $(1 \'
ru2 Русский Peter-007 2024-03-23 15:06:30 26 Мелкая правка: '_size; // sizes of parts\n vect' -> '_size; // размеры частей\n vect'
ru1 Русский Peter-007 2024-03-23 15:05:43 5681 Первая редакция перевода на Русский
en1 Английский Peter-007 2024-03-23 14:37:12 5702 Initial revision (published)