Peter-007's blog

By Peter-007, history, 8 months ago, In English

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)
  • Vote: I like it
  • +42
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How would you react if I posted a rather large among us crewmate png here?