These are the notes for Competitive Programming episode 85. On many judges, after your solution is accepted, other people can read it and hack it: run it on a test of their own, built to break it. Today's solutions are fast on every normal test and die on one built against them, and the defence is a little randomness. Count the Visitors puts 10^5 ticket numbers in an unordered_map: random tickets take hundredths of a second, but tickets that are all multiples of 172933 take about 5 seconds, because they all land in one bucket. A hash with a random seed (splitmix64 seeded from the clock) fixes it. The Middle Mark shows the same weakness in our own quickselect: a fixed first-element pivot is quadratic on sorted input, a random pivot is not. Same Bag compares two ranges as multisets: sorting per query is too slow, the sum of values is fooled (1 + 4 = 2 + 3, found by a stress test), and a sum of random 64-bit weights with prefix sums answers each query in O(1). Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real. Where a program prints a time-dependent or random detail, the notes say so.
The real-life hook
The coat check. A coat check has numbered hooks. Coat number 37 goes on hook 37 mod 10 = hook 7, so finding it again means looking at one hook. Usually each hook holds one or two coats: fast. Then a prankster arrives with coats 10, 20, 30, 40, ...: every one goes on hook 0, and to hang each new coat you dig through the whole pile. A hash map is the coat check; the prankster's coats are an anti-hash test.
The lock that changes its code. A lock whose code is printed in the manual is useless: anyone who reads the manual opens it. A lock that picks a new code every morning is safe, because the thief must guess today's code. Our hash picks its scramble when the program starts; the hacker wrote the test before that, so no fixed test can pile our keys into one bucket.
Weighing shopping bags. Are two bags of shopping the same? Emptying and sorting both is slow. Weighing is fast, but 1 kg + 4 kg weighs the same as 2 kg + 3 kg: the scale is fooled. If every kind of item had a strange random weight (3.7182 kg, 9.0451 kg), different shopping would almost never balance exactly. That is multiset hashing with random weights.
Hacks: a test built against you
- In a round with hacks (or with an open hacking phase after it), anyone can read your accepted code and submit a test that breaks it. A hacked solution counts as failed.
- Even without hacks, problem setters add anti-tests for well-known weak spots: the plain
unordered_map, first-element pivots,rand(). - A hacker needs your code to be predictable: they work out, before your program runs, exactly what it will do on their input. Randomness chosen at run time takes that away.
Problem R1 · Count the Visitors
A museum logs the ticket number of every visitor.
- Input: n (1 ≤ n ≤ 10^5), then n ticket numbers, each 1 ≤ t ≤ 10^18.
- Output: how many different ticket numbers there are.
- Time limit 2 seconds, and the round has hacks.
Sample: 5 12 5 7 12 5 → 3.
The plan is the obvious one: put every ticket into an unordered_map (average O(1) per operation) and print its size.
The plain unordered_map
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
unordered_map<ll, int> seen; // ticket number -> visits
for (int i = 0; i < n; i++) {
ll t;
cin >> t;
seen[t]++;
}
cout << seen.size() << "\n";
}
Input:
6
5 12 5 7 12 5
Output:
3
The largest test, made inside the program (so we don't paste a megabyte of input): 10^5 random tickets.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
mt19937_64 gen(85);
int n = 100000; // the largest test
unordered_map<ll, int> seen;
for (int i = 0; i < n; i++) {
ll t = gen() % 1000000000000000000LL + 1; // random tickets
seen[t]++;
}
cout << seen.size() << " distinct\n";
}
Output (in a few hundredths of a second):
100000 distinct
The hacker's test
Same size, but every ticket is a multiple of 172933:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
int n = 100000; // the largest test
unordered_map<ll, int> seen;
for (int i = 1; i <= n; i++) {
ll t = 172933LL * i; // the hacker's tickets
seen[t]++;
}
cout << seen.size() << " distinct\n";
}
Output, after about 5 seconds (0.01–0.03 s for the random test on the same machine):
100000 distinct
Same answer, roughly a hundred times slower: over the 2-second limit, Time Limit Exceeded. The accepted solution is hacked.
Why: one full bucket
What the hacker knows about std::unordered_map in g++ (libstdc++):
- The hash of an integer is the integer itself (
std::hash<long long>returns x). - The map stores keys in buckets: bucket = hash % bucket_count.
- The bucket count is always a prime from a fixed list inside the library, and it grows through that list as the map grows. 172933 is on the list; a map with about 10^5 keys uses it.
- So 172933 · 1, 172933 · 2, ... all have remainder 0: every key goes to bucket 0.
- Each insert first searches its bucket for the key, comparing against everything already there: 1 + 2 + ... + n ≈ n²/2 ≈ 5·10^9 comparisons for n = 10^5.
The weakness is not the hash map. It is that the hacker can predict where every key goes. Checking that for real:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
int n = 100000; // the largest test
unordered_map<ll, int> seen;
for (int i = 1; i <= n; i++) {
ll t = 172933LL * i; // the hacker's tickets
seen[t]++;
}
cout << seen.size() << " distinct\n";
cout << "buckets: " << seen.bucket_count() << "\n"; // how many boxes?
size_t most = 0;
for (size_t b = 0; b < seen.bucket_count(); b++) most = max(most, seen.bucket_size(b));
cout << "fullest bucket: " << most << "\n"; // how full is the worst box?
}
Output (after about 5 seconds):
100000 distinct
buckets: 172933
fullest bucket: 100000
172933 buckets, exactly the hacker's prime, and all 100000 keys in one bucket.
A hash with a random seed: SafeHash
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct SafeHash { // splitmix64 with a random seed
static ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(ull x) const {
static const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
return mix(x + SEED); // a new shuffle every run
}
};
int main() {
int n = 100000; // the largest test
unordered_map<ll, int, SafeHash> seen;
for (int i = 1; i <= n; i++) {
ll t = 172933LL * i; // the hacker's tickets
seen[t]++;
}
cout << seen.size() << " distinct\n";
size_t most = 0;
for (size_t b = 0; b < seen.bucket_count(); b++) most = max(most, seen.bucket_size(b));
cout << "fullest bucket: " << most << "\n";
}
mixis splitmix64: shifts, XORs and multiplications by odd constants that scramble all 64 bits. Nearby inputs give unrelated outputs, and it is a bijection (different inputs never give the same output), so the map's behaviour stays correct.SEEDis read fromchrono::steady_clockonce, the first time the hash is used (astaticlocal), so every run scrambles differently.- The map's third template argument is the hash:
unordered_map<ll, int, SafeHash>.
Output on the very same hacker test, in hundredths of a second:
100000 distinct
fullest bucket: 6
The fullest bucket holds a handful of keys (the exact number changes from run to run, because the seed does; 5–8 is typical). The pile is gone. The accepted program with normal input reading changes in one word:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct SafeHash { // splitmix64 with a random seed
static ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(ull x) const {
static const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
return mix(x + SEED); // a new shuffle every run
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
unordered_map<ll, int, SafeHash> seen; // only this line changed
for (int i = 0; i < n; i++) {
ll t;
cin >> t;
seen[t]++;
}
cout << seen.size() << "\n";
}
Input:
6
5 12 5 7 12 5
Output:
3
Other ways out, and why SafeHash is the habit
| Option | Hack-proof? | Notes |
|---|---|---|
unordered_map<ll,int> |
no | identity hash + known primes |
unordered_map<ll,int,SafeHash> |
yes | expected O(1); keep it in your template |
map<ll,int> (red-black tree) |
yes | O(log n), always; a good safe default |
sort + unique |
yes | O(n log n); simplest for "count distinct" |
gp_hash_table (pb_ds) + SafeHash |
yes | often faster than unordered_map |
m.reserve(n) alone |
no | changes the bucket count, but it is still a predictable prime |
Problem R2 · The Middle Mark (random pivots)
Up to 10^5 marks; print the middle one: the k-th smallest with k = n / 2 (0-based).
Quickselect: pick a pivot, move smaller marks to its left and the rest to its right (a partition), and keep only the side that holds position k.
- A pivot near the middle halves the work: n + n/2 + n/4 + ... ≈ 2n.
- With the first element as the pivot and sorted input, the pivot is the smallest every time, each round removes one mark: n + (n−1) + ... ≈ n²/2.
Same story as R1: a rule the hacker can predict.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int kth(vector<int>& a, int k) { // k-th smallest, 0-based
int l = 0, r = (int)a.size() - 1;
while (l < r) {
int p = l; // pivot: the first element
swap(a[l], a[p]);
int i = l;
for (int j = l + 1; j <= r; j++) // smaller ones go left
if (a[j] < a[l]) swap(a[++i], a[j]);
swap(a[l], a[i]); // the pivot lands at i
if (i == k) break;
if (k < i) r = i - 1; else l = i + 1;
}
return a[k];
}
int main() {
int n = 100000;
vector<int> a(n);
iota(a.begin(), a.end(), 1); // the hacker's test: already sorted
cout << "middle mark: " << kth(a, n / 2) << "\n";
}
Output, after about 3 seconds: the right answer, too late (TLE).
middle mark: 50001
One line changes: the pivot is a random position in [l, r], from a generator seeded by the clock.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int kth(vector<int>& a, int k) { // k-th smallest, 0-based
int l = 0, r = (int)a.size() - 1;
while (l < r) {
int p = l + rng() % (r - l + 1); // pivot: a random element
swap(a[l], a[p]);
int i = l;
for (int j = l + 1; j <= r; j++) // smaller ones go left
if (a[j] < a[l]) swap(a[++i], a[j]);
swap(a[l], a[i]); // the pivot lands at i
if (i == k) break;
if (k < i) r = i - 1; else l = i + 1;
}
return a[k];
}
int main() {
int n = 100000;
vector<int> a(n);
iota(a.begin(), a.end(), 1); // the hacker's test: already sorted
cout << "middle mark: " << kth(a, n / 2) << "\n";
}
Output, instantly:
middle mark: 50001
Stress test against sorting, on 2000 small arrays with many repeated values:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int kth(vector<int>& a, int k) { // k-th smallest, 0-based
int l = 0, r = (int)a.size() - 1;
while (l < r) {
int p = l + rng() % (r - l + 1); // pivot: a random element
swap(a[l], a[p]);
int i = l;
for (int j = l + 1; j <= r; j++) // smaller ones go left
if (a[j] < a[l]) swap(a[++i], a[j]);
swap(a[l], a[i]); // the pivot lands at i
if (i == k) break;
if (k < i) r = i - 1; else l = i + 1;
}
return a[k];
}
int main() {
mt19937 gen(85);
for (int it = 1; it <= 2000; it++) {
int n = gen() % 30 + 1;
vector<int> a(n);
for (int& x : a) x = gen() % 10; // small values: many repeats
int k = gen() % n;
vector<int> b = a;
sort(b.begin(), b.end()); // the slow, sure answer
if (kth(a, k) != b[k]) { cout << "differs on test " << it; return 0; }
}
cout << "all 2000 tests agree";
}
Output:
all 2000 tests agree
std::nth_element and std::sort are already safe (introselect / introsort fall back to a guaranteed method). This matters when you write your own quicksort, quickselect or treap.
Problem R3 · Same Bag
- An array a[1..n], values up to 10^9; n, q ≤ 2·10^5.
- Each query l1 r1 l2 r2: do the two ranges hold the same bag (multiset) of values? Order doesn't matter, how many times each value appears does.
- {1, 4} = {4, 1}, but {1, 4} ≠ {2, 3}.
Sample:
6 3
1 4 2 3 4 1
1 2 3 4 [1 4] vs [2 3] → NO
1 2 5 6 [1 4] vs [4 1] → YES
1 3 4 6 [1 4 2] vs [3 4 1] → NO
Brute force: sort both ranges
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
while (q--) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
vector<ll> x(a.begin() + l1, a.begin() + r1 + 1);
vector<ll> y(a.begin() + l2, a.begin() + r2 + 1);
sort(x.begin(), x.end()); // sort both bags
sort(y.begin(), y.end());
cout << (x == y ? "YES" : "NO") << "\n";
}
}
Input:
6 3
1 4 2 3 4 1
1 2 3 4
1 2 5 6
1 3 4 6
Output:
NO
YES
NO
Correct, but O(n log n) per query. On the largest test, stopping after only 200 of the 200000 queries:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
mt19937 gen(85);
int n = 200000, q = 200000; // the largest test
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) a[i] = gen() % 1000000000 + 1;
int yes = 0;
for (int t = 0; t < q; t++) {
if (t == 200) { cout << "only 200 queries done\n"; return 0; }
int len = gen() % n + 1, l1 = gen() % (n - len + 1) + 1, l2 = gen() % (n - len + 1) + 1;
vector<ll> x(a.begin() + l1, a.begin() + l1 + len), y(a.begin() + l2, a.begin() + l2 + len);
sort(x.begin(), x.end());
sort(y.begin(), y.end());
yes += x == y;
}
}
Output, after about 3 seconds, for one thousandth of the queries:
only 200 queries done
Attempt 2: compare sums of values (Wrong Answer)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<ll> pre(n + 1, 0);
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i]; // prefix sums
while (q--) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
bool same = r1 - l1 == r2 - l2 &&
pre[r1] - pre[l1 - 1] == pre[r2] - pre[l2 - 1]; // same total?
cout << (same ? "YES" : "NO") << "\n";
}
}
Input:
6 3
1 4 2 3 4 1
1 2 3 4
1 2 5 6
1 3 4 6
Output:
YES
YES
NO
The first answer is wrong: 1 + 4 = 2 + 3. On a different sample you might not even notice, so we run a stress test: the sum check against sorting on 3000 tiny arrays (values 1..5).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
bool slow(vector<ll>& a, int l1, int r1, int l2, int r2) { // sort both bags
vector<ll> x(a.begin() + l1, a.begin() + r1 + 1), y(a.begin() + l2, a.begin() + r2 + 1);
sort(x.begin(), x.end());
sort(y.begin(), y.end());
return x == y;
}
bool fast(vector<ll>& a, int l1, int r1, int l2, int r2) { // same total?
ll s1 = 0, s2 = 0;
for (int i = l1; i <= r1; i++) s1 += a[i];
for (int i = l2; i <= r2; i++) s2 += a[i];
return s1 == s2;
}
int main() {
mt19937 gen(85);
for (int it = 1; it <= 3000; it++) {
int n = gen() % 8 + 1;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) a[i] = gen() % 5 + 1; // tiny values 1..5
int len = gen() % n + 1, l1 = gen() % (n - len + 1) + 1, l2 = gen() % (n - len + 1) + 1;
int r1 = l1 + len - 1, r2 = l2 + len - 1;
if (fast(a, l1, r1, l2, r2) != slow(a, l1, r1, l2, r2)) {
cout << "differs on test " << it << ": ";
for (int i = l1; i <= r1; i++) cout << a[i] << " ";
cout << "vs ";
for (int i = l2; i <= r2; i++) cout << a[i] << " ";
return 0;
}
}
cout << "all 3000 tests agree";
}
Output:
differs on test 97: 5 1 5 1 vs 5 1 3 3
Both total 12, but the bags differ.
Random weights + prefix sums
- Give each different value v a random 64-bit weight w[v].
- pre[i] = w[a[1]] + ... + w[a[i]], in
unsigned long long, which wraps around mod 2^64. That's fine: we only compare. - A query: same length and pre[r1] − pre[l1−1] == pre[r2] − pre[l2−1]. Two subtractions: O(1).
The same stress test with random weights for 1..5:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
bool slow(vector<ll>& a, int l1, int r1, int l2, int r2) { // sort both bags
vector<ll> x(a.begin() + l1, a.begin() + r1 + 1), y(a.begin() + l2, a.begin() + r2 + 1);
sort(x.begin(), x.end());
sort(y.begin(), y.end());
return x == y;
}
ull W[6]; // a random weight per value 1..5
bool fast(vector<ll>& a, int l1, int r1, int l2, int r2) { // same total weight?
ull s1 = 0, s2 = 0;
for (int i = l1; i <= r1; i++) s1 += W[a[i]];
for (int i = l2; i <= r2; i++) s2 += W[a[i]];
return s1 == s2;
}
int main() {
mt19937 gen(85);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
for (int v = 1; v <= 5; v++) W[v] = rng();
for (int it = 1; it <= 3000; it++) {
int n = gen() % 8 + 1;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) a[i] = gen() % 5 + 1; // tiny values 1..5
int len = gen() % n + 1, l1 = gen() % (n - len + 1) + 1, l2 = gen() % (n - len + 1) + 1;
int r1 = l1 + len - 1, r2 = l2 + len - 1;
if (fast(a, l1, r1, l2, r2) != slow(a, l1, r1, l2, r2)) {
cout << "differs on test " << it << ": ";
for (int i = l1; i <= r1; i++) cout << a[i] << " ";
cout << "vs ";
for (int i = l2; i <= r2; i++) cout << a[i] << " ";
return 0;
}
}
cout << "all 3000 tests agree";
}
Output:
all 3000 tests agree
The full solution (SafeHash gives each value its weight; a 64-bit generator seeded by the clock makes them):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct SafeHash { // splitmix64 with a random seed
static ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(ull x) const {
static const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
return mix(x + SEED); // a new shuffle every run
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
unordered_map<ll, ull, SafeHash> w; // value -> random 64-bit weight
vector<ull> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
if (!w.count(a[i])) w[a[i]] = rng();
pre[i] = pre[i - 1] + w[a[i]]; // wraps around mod 2^64: fine
}
while (q--) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
bool same = r1 - l1 == r2 - l2 &&
pre[r1] - pre[l1 - 1] == pre[r2] - pre[l2 - 1];
cout << (same ? "YES" : "NO") << "\n";
}
}
Input:
6 3
1 4 2 3 4 1
1 2 3 4
1 2 5 6
1 3 4 6
Output:
NO
YES
NO
And all 200000 queries of the largest test:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct SafeHash { // splitmix64 with a random seed
static ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(ull x) const {
static const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
return mix(x + SEED); // a new shuffle every run
}
};
int main() {
mt19937 gen(85);
int n = 200000, q = 200000; // the largest test
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) a[i] = gen() % 1000000000 + 1;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
unordered_map<ll, ull, SafeHash> w; // value -> random 64-bit weight
vector<ull> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
if (!w.count(a[i])) w[a[i]] = rng();
pre[i] = pre[i - 1] + w[a[i]]; // wraps around mod 2^64: fine
}
int yes = 0;
for (int t = 0; t < q; t++) {
int len = gen() % n + 1, l1 = gen() % (n - len + 1) + 1, l2 = gen() % (n - len + 1) + 1;
yes += pre[l1 + len - 1] - pre[l1 - 1] == pre[l2 + len - 1] - pre[l2 - 1];
}
cout << q << " queries answered, " << yes << " YES\n";
}
Output, in a fraction of a second (9 of the random queries happen to compare a range with itself, or two whole-array ranges):
200000 queries answered, 9 YES
How likely is a wrong YES?
- Same bag → the sums are always equal (addition doesn't care about order).
- Different bags → the difference of the two sums is Σ c_v · w[v] mod 2^64, where c_v = (count of v in range 1) − (count in range 2), and at least one c_v ≠ 0. Fix all weights except that one w[v]: the sum is 0 for at most 2^t of the 2^64 values of w[v], where 2^t is the largest power of two dividing c_v. With |c_v| ≤ 2·10^5 < 2^18, t ≤ 17, so the chance is at most 2^17 / 2^64 = 2^-47, about 2^-46 or less per query.
- Over 2·10^5 queries: at most about 2·10^5 · 2^-46 ≈ 1 in 350 million.
XOR hashing: only for sets
Some people combine weights with XOR instead of +. But x ⊕ x = 0: XOR forgets pairs. {2, 2, 7} and {7, 5, 5} both XOR to w[7]. XOR is right when you only care which values appear an odd number of times (parity, sets of distinct values), as in practice problem 1 below; for bags use +.
Randomness done right in C++
| Tool | Use |
|---|---|
mt19937 rng(seed) |
32-bit Mersenne Twister; rng() gives 0..2^32−1 |
mt19937_64 rng(seed) |
64-bit version: random weights, 64-bit hashes |
chrono::steady_clock::now().time_since_epoch().count() |
a seed that changes every run |
uniform_int_distribution<ll>(lo, hi)(rng) |
an exactly uniform integer in [lo, hi] |
shuffle(v.begin(), v.end(), rng) |
a random order (random_shuffle is removed in C++17) |
rand() |
avoid: RAND_MAX is only 32767 on some judges (Windows compilers) |
rng() % m is very slightly biased when m doesn't divide 2^32; for contest purposes (pivots, weights) that doesn't matter, for exact probabilities use uniform_int_distribution.
Complexity vs the constraints
n, q ≤ 2·10^5 (10^5 for R1, R2), 2 s.
| Method | Time | Verdict |
|---|---|---|
R1: plain unordered_map |
O(n) average, ≈ n²/2 on the anti-hash test | TLE (about 5 s) |
R1: unordered_map + SafeHash |
O(n) expected, for every fixed test | Accepted |
R1: map or sort + unique |
O(n log n) | Accepted |
| R2: first-element pivot | O(n²) on sorted input | TLE (about 3 s) |
| R2: random pivot | O(n) expected | Accepted |
| R3: sort each query | O(q · n log n) | TLE (200 queries ≈ 3 s) |
| R3: sum of values | O(n + q) | Wrong Answer |
| R3: random weights + prefix sums | O(n + q) expected, wrong with chance ≤ ~2^-46 per query | Accepted |
Memory: O(n) everywhere.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
plain unordered_map in a hack round |
100000 distinct after about 5 s: TLE |
identity hash, known prime bucket counts | SafeHash with a clock seed |
mt19937 rng(12345) or a fixed hash seed |
hackable all the same (practice 3: fullest bucket: 2000) |
the hacker runs your code and sees the same numbers | seed from steady_clock |
rand() % n |
skewed, small values only | RAND_MAX is 32767 on some judges |
mt19937 / mt19937_64 |
| first-element pivot in your own quickselect | middle mark: 50001 after about 3 s: TLE |
sorted input, n²/2 | random pivot |
| sum of values as a bag check | YES for [1 4] vs [2 3]; differs on test 97: 5 1 5 1 vs 5 1 3 3 |
different bags, same total | sum of random 64-bit weights |
| XOR hashing for bags | WA: {2,2,7} = {7,5,5} | x ⊕ x = 0 forgets pairs | + instead of ⊕ |
| 32-bit weights | rare WA on big tests | collision chance ~2^-32 per query, times 2·10^5 | 64-bit weights |
Mini project: a randomness toolkit for your template
Paste this under your contest template: a clock-seeded 64-bit generator, a uniform rand_int, SafeHash, and a BagHash that gives every value its random weight on first use.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
// ── randomness toolkit: paste under your contest template ──
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand_int(ll lo, ll hi) { // uniform in [lo, hi]
return uniform_int_distribution<ll>(lo, hi)(rng);
}
struct SafeHash { // splitmix64 with a random seed
static ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(ull x) const {
static const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
return mix(x + SEED);
}
};
struct BagHash { // sum of random weights: compares multisets
unordered_map<ll, ull, SafeHash> w;
ull weight(ll v) {
auto it = w.find(v);
if (it != w.end()) return it->second;
return w[v] = rng();
}
};
// ── end of toolkit ──
int main() {
BagHash H;
vector<ll> a = {7, 3, 3, 9}, b = {3, 9, 7, 3}, c = {7, 3, 9, 9};
auto bag = [&](vector<ll>& v) { ull s = 0; for (ll x : v) s += H.weight(x); return s; };
cout << "a vs b: " << (bag(a) == bag(b) ? "same bag" : "different") << "\n";
cout << "a vs c: " << (bag(a) == bag(c) ? "same bag" : "different") << "\n";
vector<int> p(10);
iota(p.begin(), p.end(), 1);
shuffle(p.begin(), p.end(), rng); // a random order, new every run
int lo = INT_MAX, hi = INT_MIN;
for (int i = 0; i < 1000; i++) { int x = rand_int(1, 6); lo = min(lo, x); hi = max(hi, x); }
cout << "1000 dice rolls stayed in [" << lo << ", " << hi << "]\n";
cout << "shuffled 1..10 still sums to " << accumulate(p.begin(), p.end(), 0) << "\n";
}
Output:
a vs b: same bag
a vs c: different
1000 dice rolls stayed in [1, 6]
shuffled 1..10 still sums to 55
Ideas to extend it: a SafeHash for pair<int,int> (mix each half, combine with mix(a) ^ (mix(b) >> 1)), and a rolling string hash with a random base (episode 71).
Practice
The homework from the episode, written for this course. All outputs are real.
1. Even subarrays. Count the subarrays in which every value appears an even number of times. Sample: 1 2 2 1 3 3 → 4 ([2 2], [1 2 2 1], [3 3], the whole array).
Solution
Here we only care about parity, so XOR is exactly right: give each value a random 64-bit weight, take prefix XORs, and a subarray is "all even" exactly when its two prefix XORs are equal (every value inside it cancels in pairs). Count equal pairs of prefixes, as in episode 87's prefix-remainder counting. O(n log n) with map (or O(n) with SafeHash). Stress-tested against a direct count:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll fast(vector<ll>& a) { // prefix XOR of random weights
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
map<ll, ull> w; // value -> random weight
map<ull, ll> seen; // prefix XOR -> how many times
seen[0] = 1;
ull p = 0;
ll ways = 0;
for (ll x : a) {
if (!w.count(x)) w[x] = rng();
p ^= w[x]; // a pair of x cancels out
ways += seen[p];
seen[p]++;
}
return ways;
}
ll slow(vector<ll>& a) { // count every value in every subarray
ll ways = 0;
for (int l = 0; l < (int)a.size(); l++) {
map<ll, int> cnt;
int odd = 0;
for (int r = l; r < (int)a.size(); r++) {
odd += ++cnt[a[r]] % 2 ? 1 : -1;
ways += odd == 0;
}
}
return ways;
}
int main() {
vector<ll> s = {1, 2, 2, 1, 3, 3};
cout << "sample: " << fast(s) << " " << slow(s) << "\n";
mt19937 gen(85);
for (int it = 1; it <= 2000; it++) {
int n = gen() % 10 + 1;
vector<ll> a(n);
for (ll& x : a) x = gen() % 3 + 1;
if (fast(a) != slow(a)) { cout << "differs on test " << it; return 0; }
}
cout << "all 2000 tests agree\n";
}
Output:
sample: 4 4
all 2000 tests agree
2. Is it a permutation? Queries l r: is a[l..r] a permutation of 1..len, where len = r − l + 1? n, q ≤ 2·10^5.
Solution
A range is a permutation of 1..len exactly when its bag equals the bag {1, ..., len}. Give each value 1..n a random weight; perm[v] = W[1] + ... + W[v] is the weight of the bag {1..v}; compare the range's weight sum with perm[len]. Values outside 1..n get a fresh random weight (they can never be part of a permutation, and a fresh weight makes a false YES as unlikely as any other collision). O(n + q).
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<ull> W(n + 1), perm(n + 1, 0), pre(n + 1, 0);
for (int v = 1; v <= n; v++) W[v] = rng();
for (int v = 1; v <= n; v++) perm[v] = perm[v - 1] + W[v]; // weight of the bag {1, ..., v}
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
ull wx = (1 <= x && x <= n) ? W[x] : rng(); // values outside 1..n: any fresh weight
pre[i] = pre[i - 1] + wx;
}
while (q--) {
int l, r;
cin >> l >> r;
cout << (pre[r] - pre[l - 1] == perm[r - l + 1] ? "YES" : "NO") << "\n";
}
}
Input:
6 4
2 1 3 3 1 2
1 3
2 4
4 6
2 2
Output:
YES
NO
YES
YES
3. Break a fixed seed. Someone "fixed" the anti-hash problem with splitmix64 but a constant seed (12345). Show it is still hackable.
Solution
With a fixed seed the hash is still a fixed function: the attacker searches offline for keys whose hash % 172933 == 0 (about one in 172933 numbers qualifies), then submits those keys. Here we find 2000 of them in under a second and show they all share one bucket of a map with 172933 buckets. For a full 10^5-key hack the search takes about 50 times longer: well under a minute on a laptop, done once, before the contest.
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
struct FixedHash { // splitmix64, but with a FIXED seed
static ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(ull x) const { return mix(x + 12345); }
};
int main() {
const ull P = 172933; // a bucket count from the library's list
vector<ull> keys; // the attacker searches offline:
for (ull x = 1; keys.size() < 2000; x++) // keep keys whose hash % P == 0
if (FixedHash()(x) % P == 0) keys.push_back(x);
unordered_map<ull, int, FixedHash> m;
m.rehash(P); // a map that has grown to P buckets
for (ull k : keys) m[k]++;
size_t most = 0;
for (size_t b = 0; b < m.bucket_count(); b++) most = max(most, m.bucket_size(b));
cout << "buckets: " << m.bucket_count() << ", fullest bucket: " << most << "\n";
}
Output:
buckets: 172933, fullest bucket: 2000
With SEED read from the clock, the attacker would have to know the exact nanosecond your program starts.
4. Prove: quickselect with a random pivot does at most about 4n work on average.
Solution
Call a pivot good if it lands in the middle half of the current range (between the 25% and 75% positions). A random pivot is good with probability 1/2, so on average it takes 2 rounds to get a good pivot. After a good pivot, the side we keep has at most 3/4 of the elements. Group the rounds into phases: in phase j the range has at most (3/4)^j · n elements, each round costs at most that many comparisons, and a phase lasts 2 rounds on average. Expected total ≤ Σ 2 · (3/4)^j · n = 2n · 1/(1 − 3/4) = 8n with this rough argument; a sharper analysis (counting how often each pair is compared) gives about 2(1 + ln 2) n ≈ 3.4n for the median, under 4n. Either way it is O(n) expected, whatever the input, because the randomness is ours, not the hacker's.
Quick quiz
// bags A = {2, 2, 7} and B = {7, 5, 5}
// which test can tell them apart?
A) XOR of the values · B) XOR of random weights · C) Sum of random weights · D) Length of the range
Answer
C. XOR cancels the pairs (2 ⊕ 2 = 5 ⊕ 5 = 0), so both A and B (values or random weights) reduce to 7 or w[7]; the lengths are both 3; only the sum of random weights differs: 2·w[2] + w[7] vs w[7] + 2·w[5].
Interview questions
- Why can
std::unordered_mapbe slow on some inputs? Keys go to bucket hash % bucket_count. In g++, an integer's hash is itself and bucket counts are known primes, so multiples of one prime all collide; each operation then scans a bucket of size n: O(n), O(n²) in total. - How do you defend against it? A strong mixing hash (splitmix64) with a seed chosen at run time, or an ordered
map(O(log n) guaranteed). - What is splitmix64? A fast 64-bit mixer: add a constant, then xor-shift and multiply twice. It is a bijection, and changes in any input bit spread to all output bits.
- Expected vs worst-case complexity? Worst case is over all inputs; expected is the average over the algorithm's own random choices, for the worst input. Randomized quickselect is O(n) expected for every input.
- Why is a fixed random seed not enough? The output is then a fixed function of the input: anyone with your code can reproduce it and craft a bad test.
- How do you compare two multisets in O(1) after preprocessing? Random 64-bit weight per value, prefix sums; compare range sums (and lengths).
- Why sum and not XOR? XOR cancels equal pairs, so it only sees parity.
- What's the chance of a false positive? At most about 2^-46 per comparison with 64-bit weights and counts below 2^18; negligible for 10^5–10^6 queries. With 32-bit weights it would be about 2^-32 per query, too risky.
- Monte Carlo vs Las Vegas? Monte Carlo: always fast, rarely wrong (multiset hashing). Las Vegas: always right, usually fast (randomized quickselect).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Hack | A test written by another contestant to break your accepted code | multiples of 172933 |
| Anti-test / anti-hash test | A test built against a known weak spot | all keys in bucket 0 |
| Hash function | Turns a key into a number used to place it | std::hash<ll> (x → x in g++) |
| Bucket | One slot of a hash table; holds the keys with the same hash % bucket_count | bucket 0 |
| Bucket count | How many buckets the table has; a prime from a fixed list in g++ | 172933 |
| Collision | Two different keys in the same bucket (or with the same hash) | 172933 and 345866 |
| Load factor | Keys per bucket on average; the table grows when it exceeds 1 | 100000 / 172933 |
unordered_map |
Hash table: average O(1) per operation | unordered_map<ll,int> |
| Identity hash | A hash that returns the key itself | g++ for integers |
| splitmix64 | A fast 64-bit bit-mixing function | SafeHash::mix |
| Seed | The starting value of a random generator or hash | steady_clock count |
steady_clock |
A monotonic clock; its tick count makes a seed that changes per run | chrono::steady_clock::now() |
mt19937 / mt19937_64 |
Mersenne Twister random generators (32 / 64-bit) | mt19937_64 rng(seed) |
RAND_MAX |
The largest value rand() returns; 32767 on some judges |
avoid rand() |
| Randomized algorithm | Uses random choices, so no fixed input is always bad | random pivot |
| Expected time | Average running time over the algorithm's random choices | quickselect O(n) |
| Quickselect | Finds the k-th smallest by partitioning and keeping one side | kth(a, n/2) |
| Pivot | The element a partition splits around | a[l], or a random one |
| Partition | Moving smaller elements left of the pivot, the rest right | the for j loop |
| k-th smallest | The value at position k after sorting (0-based here) | the middle mark |
nth_element |
The STL's safe k-th element function | nth_element(a.begin(), a.begin()+k, a.end()) |
| Multiset (bag) | A collection where order doesn't matter but repeats do | {1, 4, 4} |
| Prefix sum | pre[i] = sum of the first i elements | range sum = pre[r] − pre[l−1] |
| Random weight | A random number assigned to each distinct value | w[v] = rng() |
| Multiset hashing | Comparing bags by sums of random weights | Same Bag |
| XOR hashing | Combining weights with ⊕; detects parity / sets | practice 1 |
| Unsigned wraparound | unsigned arithmetic is done mod 2^64 (well defined) |
ull prefix sums |
| Stress test | Many random tests against a slow, sure solution | all 3000 tests agree |
| Monte Carlo algorithm | Always fast, wrong with tiny probability | random weights |
| Las Vegas algorithm | Always right, fast on average | random pivot |
Summary
- A hack is a test built against predictable code. The g++
unordered_map(identity hash, fixed prime bucket counts) is the classic victim: multiples of 172933 put 10^5 keys in one bucket, about 5 s instead of hundredths. - SafeHash = splitmix64 + a seed from
steady_clock: one word in the map's type, and no fixed test can hurt it.mapand sort + unique are also safe. - Your own quickselect/quicksort needs a random pivot;
nth_elementandsortalready are safe. - Same Bag: sorting per query is too slow, sums of values are fooled, sums of random 64-bit weights with prefix sums give O(1) per query, wrong with chance ≤ ~2^-46.
- XOR hashing is for parity / sets only; seed from the clock, use
mt19937, neverrand(); stress test any fast check that might be fooled.
Solutions in C++, Java and Python
Every solution below was run on the samples.
Problem R1 · Count the Visitors
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct SafeHash { // splitmix64 with a random seed
static ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(ull x) const {
static const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
return mix(x + SEED); // a new shuffle every run
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
unordered_map<ll, int, SafeHash> seen; // only this line changed
for (int i = 0; i < n; i++) {
ll t;
cin >> t;
seen[t]++;
}
cout << seen.size() << "\n";
}
Java. HashMap/HashSet in Java hash a Long as (int)(x ^ (x >>> 32)) and turn a crowded bucket into a balanced tree (since Java 8), so the worst case is O(log n) per operation rather than O(n), but crafted collisions still slow it down. Storing mix(x + seed) (a bijection) keeps the count exact and spreads the keys. Fast input via a byte reader.
import java.io.*;
import java.util.*;
public class Main {
static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
static long nextLong() throws IOException {
int c = in.read();
while (c != '-' && (c < '0' || c > '9')) c = in.read();
boolean neg = c == '-';
if (neg) c = in.read();
long x = 0;
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = in.read(); }
return neg ? -x : x;
}
static long mix(long x) { // splitmix64
x += 0x9e3779b97f4a7c15L;
x = (x ^ (x >>> 30)) * 0xbf58476d1ce4e5b9L;
x = (x ^ (x >>> 27)) * 0x94d049bb133111ebL;
return x ^ (x >>> 31);
}
public static void main(String[] args) throws IOException {
int n = (int) nextLong();
long seed = System.nanoTime();
HashSet<Long> seen = new HashSet<>(); // store scrambled keys: mix is a bijection
for (int i = 0; i < n; i++) seen.add(mix(nextLong() + seed));
System.out.println(seen.size());
}
}
Python. Python's hash of an int is the number itself (mod 2^61 − 1) and is not randomised (only str and bytes are), so the same attack exists for set/dict of ints. XOR every key with a random salt first: x ^ salt is one-to-one, so the count is unchanged.
import sys, random
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
salt = random.getrandbits(62) # Python's int hash is not randomised: salt it
seen = {int(t) ^ salt for t in data[1:n + 1]} # x ^ salt is one-to-one, so the count is the same
print(len(seen))
main()
Input 6 / 5 12 5 7 12 5; output of all three:
3
Problem R2 · The Middle Mark
Input: n, then n marks; print the k-th smallest with k = n / 2 (0-based).
C++
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int kth(vector<int>& a, int k) { // k-th smallest, 0-based
int l = 0, r = (int)a.size() - 1;
while (l < r) {
int p = l + rng() % (r - l + 1); // pivot: a random element
swap(a[l], a[p]);
int i = l;
for (int j = l + 1; j <= r; j++) // smaller ones go left
if (a[j] < a[l]) swap(a[++i], a[j]);
swap(a[l], a[i]); // the pivot lands at i
if (i == k) break;
if (k < i) r = i - 1; else l = i + 1;
}
return a[k];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
cout << kth(a, n / 2) << "\n";
}
Java
import java.io.*;
import java.util.*;
public class Main {
static SplittableRandom rng = new SplittableRandom(System.nanoTime());
static int kth(int[] a, int k) { // k-th smallest, 0-based, random pivot
int l = 0, r = a.length - 1;
while (l < r) {
int p = l + rng.nextInt(r - l + 1);
int t = a[l]; a[l] = a[p]; a[p] = t;
int i = l;
for (int j = l + 1; j <= r; j++)
if (a[j] < a[l]) { i++; t = a[i]; a[i] = a[j]; a[j] = t; }
t = a[l]; a[l] = a[i]; a[i] = t;
if (i == k) break;
if (k < i) r = i - 1; else l = i + 1;
}
return a[k];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
System.out.println(kth(a, n / 2));
}
}
Python (three-way split around a random pivot, so repeated values are handled in one step)
import sys, random
def kth(a, k): # k-th smallest, 0-based, random pivot
while True:
p = random.choice(a)
lo = [x for x in a if x < p]
eq = sum(1 for x in a if x == p)
if k < len(lo):
a = lo
elif k < len(lo) + eq:
return p
else:
k -= len(lo) + eq
a = [x for x in a if x > p]
def main():
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
print(kth(a, n // 2))
main()
Input:
7
70 35 90 35 60 10 80
Output of all three (sorted: 10 35 35 60 70 80 90):
60
Problem R3 · Same Bag
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct SafeHash { // splitmix64 with a random seed
static ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(ull x) const {
static const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
return mix(x + SEED); // a new shuffle every run
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
unordered_map<ll, ull, SafeHash> w; // value -> random 64-bit weight
vector<ull> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
if (!w.count(a[i])) w[a[i]] = rng();
pre[i] = pre[i - 1] + w[a[i]]; // wraps around mod 2^64: fine
}
while (q--) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
bool same = r1 - l1 == r2 - l2 &&
pre[r1] - pre[l1 - 1] == pre[r2] - pre[l2 - 1];
cout << (same ? "YES" : "NO") << "\n";
}
}
Java (long arithmetic also wraps mod 2^64; weights from SplittableRandom seeded by System.nanoTime())
import java.io.*;
import java.util.*;
public class Main {
static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
static long next() throws IOException {
int c = in.read();
while (c < '0' || c > '9') c = in.read();
long x = 0;
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = in.read(); }
return x;
}
public static void main(String[] args) throws IOException {
int n = (int) next(), q = (int) next();
SplittableRandom rng = new SplittableRandom(System.nanoTime());
HashMap<Long, Long> w = new HashMap<>(); // value -> random 64-bit weight
long[] pre = new long[n + 1]; // long overflow wraps mod 2^64: fine
for (int i = 1; i <= n; i++) {
long v = next();
Long wv = w.get(v);
if (wv == null) { wv = rng.nextLong(); w.put(v, wv); }
pre[i] = pre[i - 1] + wv;
}
StringBuilder out = new StringBuilder();
while (q-- > 0) {
int l1 = (int) next(), r1 = (int) next(), l2 = (int) next(), r2 = (int) next();
boolean same = r1 - l1 == r2 - l2 && pre[r1] - pre[l1 - 1] == pre[r2] - pre[l2 - 1];
out.append(same ? "YES" : "NO").append('\n');
}
System.out.print(out);
}
}
Python (sums masked to 64 bits; the tokens are kept as bytes, whose hash Python does randomise per run)
import sys, random
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = data[2:2 + n]
MASK = (1 << 64) - 1
w = {} # value -> random 64-bit weight
pre = [0] * (n + 1)
for i, v in enumerate(a, 1):
if v not in w:
w[v] = random.getrandbits(64)
pre[i] = (pre[i - 1] + w[v]) & MASK # wrap mod 2^64, like unsigned in C++
out = []
pos = 2 + n
for _ in range(q):
l1, r1, l2, r2 = map(int, data[pos:pos + 4])
pos += 4
same = r1 - l1 == r2 - l2 and (pre[r1] - pre[l1 - 1]) & MASK == (pre[r2] - pre[l2 - 1]) & MASK
out.append("YES" if same else "NO")
print("\n".join(out))
main()
Input:
6 3
1 4 2 3 4 1
1 2 3 4
1 2 5 6
1 3 4 6
Output of all three:
NO
YES
NO