I am desensitised to books and video games and need some copium
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | Um_nik | 162 |
2 | maomao90 | 162 |
2 | atcoder_official | 162 |
5 | -is-this-fft- | 157 |
5 | adamant | 157 |
7 | awoo | 155 |
7 | djm03178 | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
I am desensitised to books and video games and need some copium
I am unfortunately not very good at writing code and can barely function without an easy way to debug said code. I therefore need a debug template at ICPC and spent some time reducing the length of the debug template I use normally. I think it's pretty short already, but it seems like it can be shortened further. I don't know how to do so, hence this blog.
Some considerations:
Now, if C++ 20 were allowed, one could simply use the following:
template<typename T>
void __print(const T& x) {
if constexpr (is_arithmetic_v<T> or is_same_v<T, string>) cerr << x;
else {
cerr << '{';
if constexpr (requires {x.first;})
__print(x.first), cerr << ", ", __print(x.first);
else {
int f = 0; for(auto i : x) cerr << (f ++ ? ", " : ""), __print(i);}
cerr << '}';
}
}
template <typename... A>
void _print(const A&... a) {((__print(a), cerr << ", "), ...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__); cerr << "]\n";
__print()
works by repeatedly considering the elements that constitute x
and calling __print()
on them (whilst ensuring that the output of each __print()
call is separated by ,
) until <<
is defined for x
by default.
Now, what's the problem with making this code compatible with C++17?
The problem is that there doesn't seem to be a short (in terms of code length) way in C++17 to differentiate between pairs and iterable containers.
I found two solutions, both of which aren't good at all:
is_literal_type_v
to check if T
is a pairtemplate<typename T>
void __print(const T& x) {
if constexpr (is_arithmetic_v<T> or is_same_v<T, string>) cerr << x;
else {
cerr << '{';
if constexpr (is_literal_type_v<T>)
__print(x.first), cerr << ", ", __print(x.second);
else {
int f = 0; for(auto i : x) cerr << (f ++ ? ", " : ""), __print(i);}
cerr << '}';
}
}
template <typename... A>
void _print(const A&... a) {((__print(a), cerr << ", "), ...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__); cerr << "]\n";
This will work if we have pairs like std::pair<int, float>
but not with something like std::pair<int, vector<int>>
. This is a significant loss of functionality since we now cannot debug things like map<int, vector<int>>
which are often used.
struct {
template<typename T>
void __print(const T& x) {
if constexpr (is_arithmetic_v<T> or is_same_v<T, string>) cerr << x;
else {
cerr << '{';
int f = 0; for(auto i : x) cerr << (f ++ ? ", " : ""), __print(i);
cerr << '}';
}
}
template<typename X, typename Y>
void __print(const pair<X, Y>& x){
cerr << '{', __print(x.first), cerr << ", ", __print(x.second), cerr << '}';
}
template <typename... A>
void _print(const A&... a) {((__print(a), cerr << ", "), ...);}
}_d;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ["; _d._print(__VA_ARGS__); cerr << "]\n";
This is also bad because:
__print()
functions as they can call each other.Can someone help me fix these issues and/or make the code shorter in general? Right now, I think the last one is the best. I can't believe I spent the last 3 hours shortening a piece of code by 5 lines.
For whatever reason, GPT and Claude seems to be unhelpful here. I ran out of access to 4o trying to get it to help me, despite purchasing GPT plus T_T
I couldn't find a nice dynamic bitset template so I wrote one.
It can be found here.
It has additional functionality as compared to std::bitset
(you can answer many kinds of range queries on it, for example: "Find $$$k$$$-th set bit in range $$$[l, r]$$$).
>>
and <<
).For most functions, their use is obvious. For others:
T prefix(int i)
: returns block of size $$$B$$$ with only first $$$i$$$ bits set.T suffix(int i)
: returns block of size $$$B$$$ with only last $$$i$$$ bits set.T range(int l, int r)
: returns block of size $$$B$$$ with only bits in range $$$[l, r]$$$ set (note that this function is 1-indexed but everything else is 0-indexed).T submask(int l, int r)
: given that $$$l$$$ and $$$r$$$ belong to the same block $$$x$$$, returns $$$x$$$ with all bits outside $$$[l, r]$$$ turned off.trim()
: turns off extra bits in the last block, if any.o=
operator where o
is some bitwise operator: if you do a o= b
where a
and b
are bitsets of different sizes, the operation is done assuming that the smaller bitset is padded with 0s to make the sizes of the two equal.Count()
: returns total number of set bits.FindFirst()
: returns position of first set bit (returns -1 if no such bit).FindLast()
: returns position of last set bit (returns -1 if no such bit).RangeProcess(int l, int r, auto block_brute, auto block_quick)
: can be used to process some range queries on the bitset. For example, "Finding $$$k$$$-th set bit in range $$$[l, r]$$$". See implementation of below functions to understand how it works.RangeSet(int l, int r, bool val)
: set all bits in given range to given value.Count(int l, int r)
: count number of set bits in given range.FindFirst(int l, int r)
: find position of first set bit in given range (returns -1 if no such bit).FindLast(int l, int r)
: find position of last set bit in given range (returns -1 if no such bit).Firstly, always use the following pragmas with it:
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
They can reduce runtime by upto 50% (thanks to mr qmk for enlightening me on this).
I am too lazy to run any proper benchmarks, but I solved a few problems with it and it was always faster than std::bitset
and tr2::dynamic_bitset
. Here are some sets of submissions on the same problem with all 3:
&=
, |
and >>
Bitset | Time | Memory |
---|---|---|
My bitset | 765 ms | 944 KB |
std::bitset | 859 ms | 1628 KB |
tr2::dynamic_bitset | 1077 ms | 1240 KB |
&=
, >>=
edit: Redid these because apparently the server was under high load at the time of the initial submissions.
Bitset | Time | Memory |
---|---|---|
My bitset | 343 ms | 1124 KB |
std::bitset | 405 ms | 1140 KB |
tr2::dynamic_bitset | 390 ms | 844 KB |
So it seems that my bitset is as good or slightly better in every manner. I have no idea why this is the case though, as there is nothing which seems particularly faster in my implementation.
Parting notes:
Thanks for reading my blog.
thanks to degenerates on AC
Notice the decline by 3 million last year? OpenAI kidnapped 3 million chinese kids and they are serving as the backend for GPT-o1 from a basement.
#FreeChineseKids
Hello, in this blog I'll share a funny way to construct a suffix tree in $$$O(n \log^2{n})$$$ time, for a given string $$$S$$$ of length $$$n$$$. I am going to call the underlying idea the "Leader Split Trick". It can probably be used to solve other problems too.
A suffix tree of a string $$$S$$$ is a radix tree constructed from all the suffixes of $$$S$$$. It's easy to see that it has $$$O(n)$$$ nodes. It can be constructed in $$$O(n)$$$ using this.
I am going to share a simple and practically useless way of building it in a worse time complexity, $$$O(n\log^2{n})$$$.
Initially, we start with an empty tree (with a virtual root node), and a set $$$G$$$ of all suffixes from $$$1$$$ to $$$n$$$, these suffixes will be stored in the form of their starting index.
It's easy to see that the paths from the root node to $$$l_u \forall (u \in G)$$$ will share some common prefix till an internal node $$$s_G$$$, after which these paths will split apart along some downward edges of the internal node. Let's define $$$d_G$$$ to be the longest common prefix across the paths $$$(\text{root}, l_u) \forall u \in G$$$.
Our algorithm will essentially do the following:
Find $$$d_G$$$.
Split apart $$$G$$$ into disjoint subsets $$$G'$$$ (each subset $$$G'$$$ will have suffixes whose leaves lie in the subtree of a unique child node of $$$s_G$$$).
Solve the problem recursively for each subset, and add an edge in the suffix tree from $$$s_G$$$ to $$$s_{G'}$$$ for every $$$G'$$$.
Now, we define a recursive function $$$f(G, L, \text{dep}, \text{dis})$$$.
In each call, $$$f(G, L, \text{dep}, \text{dis})$$$, we do the following:
If the "Leader" element $$$L$$$ is undefined:
Set $$$L$$$ to a random element of $$$G$$$.
For every suffix $$$i \in G$$$, find $$$\text{dis[i]}$$$, the longest common prefix of the suffixes $$$i$$$ and $$$L$$$. This can be done in $$$O(\vert G \vert \cdot \log{n})$$$ using binary search + hashing. We store $$$\text{dis}$$$ in a sorted manner.
Let $$$m$$$ be the minimum value in $$$\text{dis[]}$$$. It's easy to see that the internal node created from splitting $$$G$$$ will occur at depth $$$\text{dep} + m$$$. We create $$$s_G$$$, and add an edge corresponding to the substring $$$S[L + dep + 1, L + \text{dep} + m]$$$ from $$$s_{G_p}$$$ to $$$s_G$$$.
Now, we delete all suffixes $$$i \in G : \text{dis[i]} = m$$$, from $$$G$$$ (and their corresponding elements from $$$\text{dis}$$$), and group them into disjoint subsets based on the character $$$S_{i + \text{dep} + m + 1}$$$ for suffix $$$i$$$ (basically the next character after the internal node).
We call $$$f(G', \text{null}, \text{dep} + m, \text{null})$$$ for every newly created subset $$$G'$$$, and also call $$$f(G, L, \text{dep + m}, \text{dis})$$$ for the modified subset $$$G$$$.
Note: There might be some off-by-one errors.
Consider the following problem:
We have $$$n$$$ singleton sets, and are given some set merge operations. When merging sets $$$A$$$ and $$$B$$$, we merge $$$B$$$ to $$$A$$$ with probability $$$\frac{\vert A \vert}{\vert A \vert + \vert B \vert}$$$ and $$$A$$$ to $$$B$$$ with the probability $$$\frac{\vert B \vert}{\vert A \vert + \vert B \vert}$$$.
The above problem is computationally equivalent to Randomized Quicksort, which has an expected time complexity of $$$O(n \log{n})$$$.
It's not difficult to see that our split operations are simply the operations that will occur in the above problem in a reversed manner (Formally, we can define a bijective relationship between the two sets of operations, such that related sets of operations will occur with the same probability) . Therefore, the time taken by all the split operations is $$$O(n \log{n})$$$.
However, every time we perform a split operation (merge in reverse), we also compute $$$\text{dis}$$$ for the child set $$$C$$$ (which gets merged into the parent set), and that takes $$$O(\vert C \vert \log{n})$$$ time. Thus, our entire algorithm has an expected time complexity of $$$O(n \log^2{n})$$$.
My implementation can be found here.
This trick seems to have some "online capability", as we can efficiently split a group of nodes into multiple groups (given that the information for query for a group can be processed mostly through a randomly chosen leader element). For example, consider the following problem:
You are given a tree on $$$n$$$ nodes. You also have a set containing all nodes, $$${1, 2, \dots , n}$$$. You have to process the following queries online:
- "$$$1\; m\; x\; v_1\; v_2\; \dots \; v_x$$$" : Remove the nodes $$$v_1, v_2 \dots, v_x$$$ from the set $$$S$$$ whose maximum element is $$$m$$$, and create a new set with these elements (it is guaranteed that there exists some set with maximum element $$$m$$$ and $$$v_i \in S \; \forall \; i$$$).
- "$$$2 \; m$$$" : Let the set whose maximum element is $$$m$$$ be $$$S$$$. Find some node $$$x \in S \mid \max_{y \in S}{\text{dis}(x, y)} = \max_{u, v \in S}{\text{dis}(u,v)} $$$.
[to be updated]
Name |
---|