Problem Link:
Setter: Alei Reyes
Tester: Triveni Mahatha
Editorialist: Alei Reyes
Difficulty:
MEDIUM-HARD
Prerequisites:
Bitmask, Topology
Problem:
Given a topology over a set X, find accumulation points of some subset R of X.
Explanation:
The hands of Goro defines a topology. Formally a topology over a set X is a collection T of subsets of X called open sets, in which the following conditions are satisfied:
- \phi and X belongs to T
- Any finite intersection of sets that belongs to T also belongs to T
- Any union of sets that belongs to T also belongs to T
In our case, X = {1, …, m}, a recipe is a subset R \subset X, and Suzumo is finding the accumulation points of R.
Formally, p is an accumulation point of set S, iff for every open set G that contains p, (G - {p}) ∩ S \neq \phi.
Let’s denote the set of accumulation points of set A by A’. It turns out that (A ∪ B)’=A’ ∪ B’. This observation suggests to find the accumulation points of every unitary set, and then use the union operation to find the accumulation points of any arbitrary set!
Let’s represent sets as bitmasks of length m, bit i will be 1 if element i belongs to the set or 0 otherwise. Now we can use bitwise operations instead of set operations.
j is not an accumulation point of the unitary set {i} iff there exists an open set that contains j but not i. In bitwise language, it means that there exists a bitmask with a one in position j, and a zero in position i.
Instead of finding the accumulation points, it is easier to find the points that are not accumulation points.
Let f[x] be the points that are not accumulation points of {x}. We can fill f by performing the following operation over every open set b: f[i] |= b, where i iterates over every bit turned off in b.
Notes:
- i is not an accumulation point of {i}.
- It is not necessary to generate all the possible intersections of open sets.
- Since the number of elements is at most 100, we can use __int128_t in C++, other ways to represent the bitmasks are a pair of long longs or bitsets
SOLUTION:
Time Complexity:
Let’s say c is a constant to represent bitwise operations of bitset size m. Then,
O(N m c) pre-computation. And, O(m c) per query to answer them.
Space Complexity:
O(m c)