Hi Codeforces.
Today I came across a legendary problem: 896E - Welcome home, Chtholly. It’s rated $$$3100$$$ and is known for being a nightmare for data structure enthusiasts. The tags say "DSU" and "Data Structures," and the intended solutions involve complex Sqrt-decomposition or Segment Tree Beats.
But as my future handle suggests -- $$$SegTreeIsAMyth$$$. I decided to see if a simple $$$O(N \cdot M)$$$ brute force could pass.
To my surprise, it didn't just pass: it $$$crushed$$$ the tests in $$$1750ms$$$ (with a 3s limit)!
Screenshot:
The Code
The core of my solution is just a simple loop. No complex trees, no heavy pointers.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define debug cout << "Debug\n"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
---===ASCII help===---
'0' -> 48 '9' -> 57
'A' -> 65 'Z' -> 90
'a' -> 97 'z' -> 122
*/
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
int arr[n];
for (int i = 0; i < n; ++i) cin >> arr[i];
while (m--) {
int t, l, r, x; cin >> t >> l >> r >> x;
--l; --r;
if (t == 1) {
for (int i = l; i <= r; ++i) {
if (arr[i] > x) arr[i] -= x;
}
}
else {
ll ans = 0;
for (int i = l; i <= r; ++i) {
if (arr[i] == x) ++ans;
}
cout << ans << '\n';
}
}
}
Why did it pass?
Many of you might think $$$10^{10}$$$ operations shouldn't pass in 3 seconds. Here is why it did:
GCC 14 & AVX2: The
#pragma GCC target("avx2")allows the compiler to use SIMD instructions. It processes multiple integers in a single CPU cycle.Loop Unrolling:
#pragma GCC optimize("unroll-loops")reduces the overhead of the loop control.Cache Locality: A simple array traversal is the most cache-friendly operation possible. While a Segment Tree jumps around in memory causing cache misses, the CPU prefetcher loves this linear scan.
Modern Judges: Codeforces' upgraded hardware is incredibly fast at executing vectorized code.
Conclusion
Next time you see a 3100-rated problem, don't be afraid. Sometimes, the "dumb" solution with the right pragmas is more powerful than the most sophisticated data structure.
This is very funny. But I think this is why they usually use 200k now (I've also seen 300k and 500k for seemingly no apparent reason in very cache-unfriendly/high-constant brute-force-in-N^2 problems) and probably testers will try an AVX brute and make sure it doesn't work.
Exactly! That's why I'm glad this problem is from 2017. Modern hardware is a beast.
Not so surprising considering even some recent problems rely on the order of 1e9, 1e10 simple operations being fast enough to fit within a few seconds time limit too. I've complained about such intentional problem design as requiring trust/willingness to try more than skill.
Both hardware and compilers have come a long way in the years since those lower-numbered rounds. You could check assembly too, maybe there's some compiler tricks or autovectorization involved that didn't exist before.
I remember that the earliest problems were designed for CF-on-shitty-backend and got their time limits cut down by half at some point — maybe this one's already in that time range, or it should be but didn't get updated TL. Or maybe it just had a loose TL originally too, that wouldn't be the worst thing problemsetters have done.
Totally agree. It’s fascinating how the gap between 'intended complexity' and 'raw CPU power' has widened over the years. This problem feels like a perfect benchmark for how much modern compilers and SIMD can compensate for a 'naive' approach. 1e10 operations used to be a death sentence, but today, with a bit of luck and the right pragmas, it’s a 1.7s reality.
So real, in some recent div 2 problem I was practicing with there was an intended $$$n \sqrt{n}$$$ for $$$n = 200k$$$ and I was super confused if it was intended or not. And there was also this IOI problem whose intended solution was $$$n \sqrt{n} \log{n}$$$ for $$$n = 200k$$$ to run in 8 seconds on 2009 hardware...
1e10 is crazy tho i thought even like 8e8 was pushing the limit
You said this problem can be solved using Segment Tree Beats. Could you give me such a solution?