 |
tgen
|
|
tgen
|
Adversarial generation for specific problems. More...
Functions | |
| std::string | tgen::hack::abacaba (int n) |
| Returns the prefix of the infinite word "abacabad...". | |
| std::pair< std::string, std::string > | tgen::hack::unsigned_polynomial_hash () |
| Returns two strings that force polynomial hash collision for power-of-two mod. | |
| std::pair< std::string, std::string > | tgen::hack::polynomial_hash (int alphabet_size, int base, int mod) |
| Returns two strings that force polynomial hash collision given base and mod. | |
| std::pair< std::string, std::string > | tgen::hack::polynomial_hash (int alphabet_size, std::vector< int > bases, std::vector< int > mods) |
| Returns two strings that force polynomial hash collision given bases and mods. | |
| std::vector< long long > | tgen::hack::std_unordered (int size) |
| List of integers that tries to force collision on std::unordered_set. | |
| std::vector< std::pair< int, int > > | tgen::hack::mo_worst_case (int n, int q) |
| Query list that forces asymptotic worst-case for Mo's algorithm. | |
| std::vector< std::string > | tgen::hack::string_set_worst_case (int size) |
| List of strings that have high cost to insert in a std::set. | |
| egraph< int >::value | tgen::hack::non_strict_relaxation_dijkstra_bug (int n) |
| Directed weighted graph for Dijkstra with non-strict relaxation. | |
| egraph< int >::value | tgen::hack::stale_heap_dijkstra_bug (int n) |
| Directed weighted graph for Dijkstra without a stale-heap check. | |
| egraph< int >::value | tgen::hack::spfa (int n) |
| Worst-case for FIFO-SPFA. | |
| egraph< int >::value | tgen::hack::dinitz_worst_case (int k, int l) |
| Flow network for Edmonds-Karp and Dinitz worst-case. | |
| std::vector< geometry::point< double > > | tgen::hack::naive_rotating_calipers_max_dist_bug () |
| Convex polygon that breaks naive rotating calipers for maximum distance. | |
| template<typename T> | |
| std::vector< bool > | tgen::hack::mt19937_xor_hash () |
| Mask that forces a zero XOR hash from std::mt19937 or std::mt19937_64. | |
| std::pair< std::vector< int >, std::vector< std::vector< int > > > | tgen::hack::segment_tree_beats_worst_case (int k, int q) |
| Array and updates for worst case of segment tree beats. | |
Adversarial generation for specific problems.
|
inline |
Returns the prefix of the infinite word "abacabad...".
| n | Length of the prefix. |
O(n).
|
inline |
Flow network for Edmonds-Karp and Dinitz worst-case.
| k | Core size. |
| l | Source and sink chain length. |
Builds the Zadeh (1972) anti-shortest-paths network, a worst-case instance for both Edmonds-Karp and Dinitz. The source is vertex 0 and the sink is vertex 4l + 2k + 1.
References:
O(l + k^2).
|
inline |
Query list that forces asymptotic worst-case for Mo's algorithm.
| n | Size of the array operated upon. |
| q | Number of queries to be returned. |
Forces Theta(q sqrt n) pointer moves for any ordering.
O(n log n + q).
| std::vector< bool > tgen::hack::mt19937_xor_hash | ( | ) |
Mask that forces a zero XOR hash from std::mt19937 or std::mt19937_64.
| T | int for std::mt19937, long long for std::mt19937_64. |
For any seed, if rng is the corresponding engine and
then hash = 0.
Reference:
O(1).
|
inline |
Convex polygon that breaks naive rotating calipers for maximum distance.
Returns a strictly convex polygon on which the naive rotating-calipers loop (advance j while dist(i, next(j)) > dist(i, j)) reports a diameter smaller than the true one.
Reference:
O(1).
|
inline |
Directed weighted graph for Dijkstra with non-strict relaxation.
| n | Number of vertices. |
Forces Omega(2^{n/2}) time on Dijkstra from 0 if relaxation uses d + w <= dist[j] instead of <.
O(n).
|
inline |
Returns two strings that force polynomial hash collision given base and mod.
| alphabet_size | Alphabet size. |
| base | Base. |
| mod | Mod. |
Computes two strings that have the same polynomial hash for given base and mod.
Characters are in [a, a + alphabet_size). The larger the alphabet, the smaller the colliding strings.
Reference:
O(sqrt(mod) log mod).
|
inline |
Returns two strings that force polynomial hash collision given bases and mods.
| alphabet_size | Alphabet size. |
| bases | Bases. |
| mods | Mods. |
Computes two strings that have the same polynomial hash for given bases and mods, up to 2 (base, mod) pairs.
Characters are in [a, a + alphabet_size). The larger the alphabet, the smaller the colliding strings.
Reference:
O(sqrt(mod) log^2 mod), with mod = max(mods).
|
inline |
Array and updates for worst case of segment tree beats.
| k | Hack order (defines the size N of the array). |
| q | Number of updates to generate. |
Reference:
O(fib(2k+1)^3 + q).
|
inline |
Worst-case for FIFO-SPFA.
| n | Number of vertices. |
Builds two parallel chains of length k = n/2 (upper a_1..a_k, lower b_1..b_k):
The upper chain reaches each a_{i+1} with a loose estimate first; once b_i is settled on the zero-weight lower chain, the cross edge can strictly improve a_{i+1} and re-enqueue it in FIFO-SPFA.
Forces Omega(n^2) time on FIFO-SPFA from vertex 0 (Theta(n * m).
O(n).
|
inline |
Directed weighted graph for Dijkstra without a stale-heap check.
| n | Number of vertices. |
Forces Omega(n^2) time on Dijkstra from 0 if the heap pop does not skip stale entries (if (d > dist[i]) continue).
O(n).
|
inline |
List of integers that tries to force collision on std::unordered_set.
| size | Size of the list. |
Creates hack for both std::unordered_set and std::unordered_map, forcing quadratic behavior. The hack might not be effective due to differences in C++ implementations.
O(size).
|
inline |
List of strings that have high cost to insert in a std::set.
| size | Total number of characters. |
Inserting these strings in a std::set takes Theta(size log(size)) time, and that is asymptotically the maximum one can achieve.
O(size log(size)).
|
inline |
Returns two strings that force polynomial hash collision for power-of-two mod.
Computes two strings that have the same polynomial hash for any base and power-of-two mod (up to 2^64).
Characters are in [a, b].
Reference:
O(1).
1.14.0