# (Optional) Bitsets

Author: Benjamin Qi

Examples of how bitsets give some unintended solutions on recent USACO problems.

### Prerequisites

- Errichto - Bitwise Operations Pt 1

## Tutorial

tl;dr some operations are around 32-64x faster compared to a boolean array. See the C++ Reference for the operations you can perform.

Resources | ||||
---|---|---|---|---|

CPH | speeding up Hamming distance | |||

CF |

## Knapsack

Focus Problem – try your best to solve this problem before continuing!

Of course, the first step is to generate the sizes of each connected component.

#include <bits/stdc++.h>using namespace std;struct DSU {vector<int> e; void init(int N) { e = vector<int>(N,-1); }int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }bool sameSet(int a, int b) { return get(a) == get(b); }int size(int x) { return -e[get(x)]; }bool unite(int x, int y) { // union by sizex = get(x), y = get(y); if (x == y) return 0;

A naive knapsack solution would be as follows. For each $0\le i\le \texttt{comps.size()}$, let $\texttt{dp}[i][j]=1$ if there exists a subset of the first $i$ components whose sizes sum to $j$. Then the answer will be stored in $\texttt{dp}[i]$. This runs in $\mathcal{O}(N^2)$ and is too slow if implemented naively, but we can use bitset to speed it up!

Note: you can't store all $N$ bitsets in memory at the same time (more on that below).

Full Solution

**Challenge**: This solution runs in $\approx 0.3\text{s}$ when $N=10^5$ and
there are no edges. Find a faster solution which can also be sped up with bitset
(my solution runs in 0.03s).

## Cowpatibility (Gold)

Focus Problem – try your best to solve this problem before continuing!

Label the cows from $0\ldots N-1$. For two cows $x$ and $y$ set `adj[x][y]=1`

if
they share a common flavor. Then the number of pairs of cows that are compatible
(counting each pair where $x$ and $y$ are distinct twice) is equal to the sum of
`adj[x].count()`

over all $x$. It remains to compute `adj[x]`

for all $x$.

Unfortunately, storing $N$ bitsets each with $N$ bits takes up $\frac{50000^2}{32}\cdot 4=312.5\cdot 10^6$ bytes of memory, which is greater than USACO's $256$ megabyte limit. We can reduce the memory usage by half in exchange for a slight increase in time by first computing the adjacency bitsets for all $x\in [0,N/2)$, and then for all $x\in [N/2,N)$ afterwards.

First, we read in all of the flavors.

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef bitset<50000> B;const int HALF = 25000;int N;B adj[HALF];vector<int> flav[1000001];

Then for each flavor, we can look at all pairs of cows that share that flavor and update the adjacency lists for those $x\in [0,HALF)$.

int main() {input();for (int i = 1; i <= 1000000; ++i)for (int x: flav[i]) if (x < HALF)for (int y: flav[i]) adj[x][y] = 1;for (int i = 0; i < HALF; ++i) ans += adj[i].count();}

`adj[i].count()`

runs quickly enough since its runtime is divided by the bitset
constant. However, looping over all cows in `flav[i]`

is too slow if say,
`flav[i]`

contains all cows. Then the nested loop could take $\Theta(N^2)$ time!
Of course, we can instead write the nested loop in a way that takes advantage of
fast bitset operations once again.

for (int i = 1; i <= 1000000; ++i) if (flav[i].size() > 0) {B b; for (int x: flav[i]) b[x] = 1;for (int x: flav[i]) if (x < HALF) adj[x] |= b;}

The full main function is as follows:

Full Solution

Apparently no test case contains more than $25000$ distinct colors, so we don't actually need to split the calculation into two halves.

## Lots of Triangles

Focus Problem – try your best to solve this problem before continuing!

First, we read in the input data. `cross(a,b,c)`

is positive iff `c`

lies to the
left of the line from `a`

to `b`

.

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<ll,ll> P;#define f first#define s secondll cross(P a, P b, P c) {

There are $\mathcal{O}(N^3)$ possible lots. Trying all possible lots and
counting the number of trees that lie within each in $\mathcal{O}(N)$ for a
total time complexity of $\mathcal{O}(N^4)$ should solve somewhere between 2 and
5 test cases. Given a triangle `t[0], t[1], t[2]`

with positive area, tree `x`

lies within it iff `x`

is to the left of each of sides
`(t[0],t[1])`

,`(t[1],t[2])`

, and `(t[2],t[0])`

.

int main() {input();vector<int> res(N-2);for (int i = 0; i < N; ++i) for (int j = i+1; j < N; ++j)for (int k = j+1; k < N; ++k) {vector<int> t = {i,j,k};if (cross(v[t[0]],v[t[1]],v[t[2]]) < 0) swap(t[1],t[2]);int cnt = 0;for (int x = 0; x < N; ++x) {if (cross(v[t[0]],v[t[1]],v[x]) <= 0) continue;

The analysis describes how to count the number of trees within a lot in
$\mathcal{O}(1)$, which is sufficient to solve the problem. However,
$\mathcal{O}(N)$ is actually sufficient as long as we divide by the bitset
constant. Let `b[i][j][k]=1`

if `k`

lies to the left of side `(i,j)`

. Then `x`

lies within triangle `(t[0],t[1],t[2])`

as long as
`b[t[0]][t[1]][x]=b[t[1]][t[2]][x]=b[t[2]][t[0]][x]=1`

. We can count the number
of `x`

such that this holds true by taking the bitwise AND of the bitsets for
all three sides and then counting the number of bits in the result.

Fast Solution

## Knapsack Again

(GP of Bytedance 2020 F)

Given $n$ ($n\le 2\cdot 10^4$) positive integers $a_1,\ldots,a_n$ ($a_i\le 2\cdot 10^4$), find the max possible sum of a subset of $a_1,\ldots,a_n$ whose sum does not exceed $c$.

Consider the case when $\sum a_i\ge c$. The intended solution runs in $\mathcal{O}(n\cdot \max(a_i))$; see here for more information. However, we'll solve it with bitset instead.

As with the first problem in this module, let $\texttt{dp}[i][j]=1$ if there exists a subset of the first numbers components that sums to $j$. This solution runs in $\mathcal{O}(n\cdot \sum a_i)$ time, which is too slow even if we use bitset.

Taking inspiration from this CF blog post, we'll first shuffle the integers randomly and perform the DP with the following modification:

- If $\left|\frac{ci}{n}-j\right| \ge X$ for some $X$ that we choose, then set $\texttt{dp}[i][j]=0$.

Since we only need to keep track of $2X+1$ values for each $i$, this solution runs in $\mathcal{O}(nX)$ time, which is fast enough with $X=5\cdot 10^5$ using bitset.

It turns out that $X\approx \max a_i\cdot \sqrt n$ (up to a constant) suffices for correctness with high probability (briefly mentioned here). I'm not totally sure about the details, but intuitively, the random shuffle reduces the optimal subset to some distribution with variance at most $(\max a_i)^2\cdot n$. In the special case where each $a_i$ is either $0$ or $\max a_i$, we can bound the probability of failure using the Catalan numbers. I think it is something like $e^{-\frac{m^2}{n}}$ if we let the bitset have size $m\cdot \max a_i$.

Solution

## Other Applications

Use to speed up the following:

- Gaussian Elimination in $\mathcal{O}(N^3)$
- Bipartite matching in $\mathcal{O}(N^3)$ (dense graph with $N$ vertices on each side)
- Though $\mathcal{O}(NM)$ Kuhn's algorithm is probably fast enough ...

- BFS through dense graph in $\mathcal{O}(N^2)$
~~In general, passing solutions with an additional factor of $N$.~~

Operations such as `_Find_first()`

and `_Find_next()`

mentioned in Errichto's
blog can be helpful.

Resources | ||||
---|---|---|---|---|

GFG | only resource I could find :P |

A comment regarding the last two applications:

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSA | Hard | ## Show TagsDSU |

In USACO Camp, a similar problem appeared with $N\le 10^5$ and a $6$ second time
limit (presumably to allow $\mathcal{O}(N\log ^2N)$ solutions to pass). I had
already done this problem but ~~forgot how I had solved it~~ decided to try
something new. Try to guess what I did!

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsBitset, TopoSort | |||

AC | Easy | ## Show TagsBitset | |||

TOKI | Easy | ## Show TagsBitset | |||

Baltic OI | Normal | ## Show TagsBitset | |||

Baltic OI | Normal | ## Show TagsBitset, Knapsack | |||

COCI | Normal | ## Show TagsBitset | |||

Plat | Hard | ## Show TagsBitset, Sliding Window | |||

IZhO | Hard | ## Show TagsBitset, Knapsack | |||

Baltic OI | Hard | ## Show TagsBitset, Knapsack | |||

CF | Hard |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!