For years, I have been dissuading people from using random vector in C++ unless it is necessary (like in adjacency lists, where otherwise it is very annoying to implement). The most common response I get is
BuT iT'S sO eAsY tO uSe!
Recently I finally had a prime example of why all these syntactic sugar will give you a sweet tooth. Witness Collect the Coins, a problem from the recent UCup contest.
The code we had in contest got TLE'ed:
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 100;
ll n;
pair<ll, ll> vec[maxn];
bool check(ll V) {
vector<bool> dp(n + 1);
multiset<pair<ll, ll>> all;
auto valid = [&](ll i, ll j) {
auto [t1, p1] = vec[i];
auto [t2, p2] = vec[j];
return abs(p1 - p2) <= abs(t1 - t2) * V;
};
auto insert = [&](ll pos) {
auto [t, p] = vec[pos];
// insert (p - tV, -p-tV)
// ...
auto x = p - t * V;
auto y = -p - t * V;
while (all.size()) {
auto it = all.lower_bound({x + 1, -3e18});
if (it == all.begin()) break;
auto [tx, ty] = *(--it);
if (ty <= y) all.extract({tx, ty});
}
bool flag = true;
if (all.size()) {
auto rit = all.lower_bound({x, y});
if (rit == all.end())
flag = true;
else {
auto [tx, ty] = *rit;
if (ty < y)
flag = true;
else
flag = false;
}
}
if (flag) all.insert({x, y});
};
for (int i = 2; i < n; i++) {
if (!valid(i - 1, i)) break;
dp[i + 1] = true;
}
// check st = 2, i = 3?
dp[2] = true;
for (ll i = 3; i <= n; i++) {
if (!valid(i - 2, i - 1)) {
all.clear();
}
// cout << "addr2" << endl;
if (dp[i - 1]) insert(i - 2);
// j-1
auto [qt, qp] = vec[i];
auto qx = qp - qt * V;
auto qy = -qp - qt * V;
auto it = all.lower_bound({qx, qy});
if (it != all.end()) {
auto [tx, ty] = *it;
if (ty >= qy) dp[i] = true;
}
}
for (int temp = n; temp >= 1; temp--) {
if (temp < n and !valid(temp, temp + 1)) break;
if (dp[temp]) return true;
}
return false;
};
void solve() {
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> vec[i].first >> vec[i].second;
}
unordered_set<ll> all_pos;
for (ll i = 1; i <= n; i++) {
all_pos.insert(vec[i].second);
}
if (all_pos.size() <= 2) {
cout << 0 << '\n';
return;
}
ll L = 1, R = 1e9 + 100;
while (L < R) {
ll mid = (L + R) / 2;
if (check(mid))
R = mid;
else
L = mid + 1;
}
if (L > 1e9) L = -1;
cout << L << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
However, just doing these three things is enough for AC:
- Move all data structure variables to global;
- Move all closures to functions;
- Last but not the least, stop using random vectors.
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 100;
ll n;
pair<ll, ll> vec[maxn];
set<pair<ll, ll>> all;
unordered_set<ll> all_pos;
ll V;
bool valid(ll i, ll j) {
auto [t1, p1] = vec[i];
auto [t2, p2] = vec[j];
return abs(p1 - p2) <= abs(t1 - t2) * V;
}
void insert(ll pos) {
auto [t, p] = vec[pos];
// insert (p - tV, -p-tV)
// ...
auto x = p - t * V;
auto y = -p - t * V;
bool flag = true;
auto rit = all.lower_bound({x, y});
if (rit == all.end())
flag = true;
else {
auto [tx, ty] = *rit;
if (ty < y)
flag = true;
else
flag = false;
}
if (flag) {
auto it = rit;
while (it != all.begin()) {
auto pit = prev(it, 1);
auto [tx, ty] = *pit;
if (ty <= y)
all.erase(pit);
else
break;
}
all.insert({x, y});
}
}
bool check() {
static bool dp[maxn];
std::fill(dp, dp + n + 1, 0);
all.clear();
for (int i = 2; i < n; i++) {
if (!valid(i - 1, i)) break;
dp[i + 1] = true;
}
// check st = 2, i = 3?
dp[2] = true;
for (ll i = 3; i <= n; i++) {
if (!valid(i - 2, i - 1)) {
all.clear();
}
// cout << "addr2" << endl;
if (dp[i - 1]) insert(i - 2);
// j-1
auto [qt, qp] = vec[i];
auto qx = qp - qt * V;
auto qy = -qp - qt * V;
auto it = all.lower_bound({qx, qy});
if (it != all.end()) {
auto [tx, ty] = *it;
if (ty >= qy) dp[i] = true;
}
}
for (int temp = n; temp >= 1; temp--) {
if (temp < n and !valid(temp, temp + 1)) break;
if (dp[temp]) return true;
}
return false;
};
void solve() {
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> vec[i].first >> vec[i].second;
}
all_pos.clear();
for (ll i = 1; i <= n; i++) {
all_pos.insert(vec[i].second);
}
if (all_pos.size() <= 2) {
cout << 0 << '\n';
return;
}
ll L = 1, R = 1e9 + 100;
while (L < R) {
ll mid = (L + R) / 2;
V = mid;
if (check())
R = mid;
else
L = mid + 1;
}
if (L > 1e9) L = -1;
cout << L << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Surely everyone will stop using random vectors instead of...
BuT mY tEaMmAtE wIlL hElP mE wItH tHe CoNsTaNtS!
Ugh for the love of...
okay, but why is the title "stop using C++23"?
A lot of the syntactic sugar is introduced in more recent c++ builds.
I don't think you have any idea what you're talking about, and as someone who missed qualification to an onsite final for not using vector, twice, I hope no one listens to you.
I submitted your exact second code to the problem and got TLE, but after changing
static bool dp[maxn]to a globalvector<int> dp(maxn), it gets AC. Incontrovertible evidence that vectors are faster than arrays, or is it just that your code is so close to TL that random fluctuations make a significant difference?Interesting. vector has given me only bad experiences.
Do you mind sharing your story with vector?
It has to do with array bounds mostly — in Google Code Jam 2019, I did something like this
but in the problem the limit was $$$n \le 10^6$$$: I miscounted the zeros, so I got RE. If I had added one more zero to that constant I would have made it to finals. With a vector this would not have mattered, as I would have likely done
vector<int> a(n)instead of defining a maxn constant.In the second case, I had a global
dparray,int dp[1100][1100];but later I realized the dimensions actually needed to be 3000 instead: I changed the dimensions of the dp array but forgot to change the code that clears it, leading to WA. If I created a vector for each test case instead, it would automatically come with zeros, and I wouldn't need to worry about clearing it.The other huge benefit, at least to me, is bounds checking — now that the vector has exactly the needed size, it's easy to get warnings when the vector is accessed out of bounds which makes finding errors so much easier.
I see. Yeah that sucks in GCJ especially.
I would probably still want my code to be fast, as I am usually the guy that tries to fit some random algo in time limit (see my previous blog as an example :) ). But I can see that argument.
BTW I tested and code with vector is 50ms slower, hence my conclusion that using vector is bad.
My vector submission passed with 880ms, and the code with array got TLE, so I can claim I tested and array is at least 120ms slower.
But like I implied, I don't think that this is what the difference really means, or that a 50ms difference would be easily measured. And even if you somehow rigorously measured such a difference, if random fluctuations like this are bigger than the difference, the difference really doesn't matter.
Interesting. I don't think generally servers can fluctuate over 100ms. Or maybe we should just submit multiple times in contest...
I guess I will have to test it once I get back to my laptop.
By the way, there's a reason I said I changed it to
vector<int> dp(maxn).vector<bool>is weird and slow and you should generally never use it.Wut
Yeah in contest we coded the bool thing-y...
Hmm one more thing to test.
By the way, I think one other lesson to learn, is that you don't have to care much about these kinds of differences, if you are not trying to cheese a problem with a worse complexity. There are faster (complexity-wise) solutions to this problem.
I don't think it's generally possible to tell whether a solution is 0.5 tl or 2 tl...
I am more of the 'take a good enough solution and run' type and I had much success just trying to do optimization.
I think it's better to prioritize correctness over performance. It's quite rare that I TLE on some problem because of constant factor, but I want to make debugging as easy as possible especially in an ICPC setting where you might not have print debugging available if you let your teammates code while you are debugging. If I am really concerned about time limit, then I might swap, but otherwise I think its better to reduce WA potential than TLE.
I don't think there is much WA potential... After all it's only one array size thing, which you should be estimating anyway.
Having your state reset if the problem is multitest is pretty useful, it's one less thing you have to worry about. Generally I keep all of my state local unless I am precomputing some constants like factorials or sieve. But the main thing is that I think it is fine to use C++23 constructs (including using lambdas if it helps) if it helps reduce the space for errors. Maybe the optimal construct (imo) is to have some global buffer allocated and allocate a constant sized vector on top of it with a custom allocator, but it doesn't seem worth it especially if you have to type it up every time instead of including in a template.
Hmm. My main concern is that it reduces preventable errors (array bounds, cleanup) at the cost of unpreventable TLEs, but I guess there's argument on both sides.