(EDIT: I no longer require pity because it turns out my solution was much more wrong than I thought, and my "fixed" solution would've failed too)
I had a 1 character bug on https://codeforces.me/contest/1396/problem/E in contest, and was just a tiny bit too slow to fix it. So now I'm sharing my story in hopes of collecting pity and contribution. See if you can find the bug faster than I did :)
The submission I made: (timestamp 1:56:00) https://codeforces.me/contest/1396/my
I found the fix & saved it at 2:00:01...
~/codeforces/666div1 ls -lT e.cpp
-rw-r--r-- 1 stevenhao staff 4107 Aug 30 09:35:01 2020 e.cpp
Here is the code, before the fix:
// ============= Solution ============= //
int main() {
int n;
ll k;
cin >> n >> k;
vector<vector<int>> ed(n + 1);
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
ed[a].push_back(b);
ed[b].push_back(a);
}
vector<int> subtreesize(n, 1);
auto go1 = yc([&](auto dfs, int cur, int prv = -1) -> void {
for (int nxt: ed[cur]) {
if (nxt == prv) continue;
dfs(nxt, cur);
subtreesize[cur] += subtreesize[nxt];
}
});
go1(0);
for (int i: subtreesize) {
k -= i % 2;
}
if (k % 2 == 1) {
cout << "NO\n";
return 0;
}
vector<pii> matches;
ed[n++].push_back(0); // new root
vector<vector<int>> buffers(n);
pp(k);
auto go2 = yc([&](auto dfs, int cur, int prv = -1) -> vector<int>& {
pp(cur, k);
vector<int> &res = buffers[cur];
res.push_back(cur);
for (int nxt: ed[cur]) {
if (nxt == prv) continue;
vector<int> &bb = dfs(nxt, cur);
k -= sz(bb) / 2 * 2;
while (sz(bb) >= 2 && k < 0) {
matches.push_back(pii(bb[sz(bb) - 2], bb[sz(bb) - 1]));
bb.pop_back();
bb.pop_back();
k += 2;
}
if (sz(res) < sz(bb)) {
swap(res, bb);
}
for (int i: bb) {
res.push_back(i);
}
}
return res;
});
vector<int> final_output = go2(n - 1);
if (k > 0) {
cout << "NO\n";
} else {
pp(k);
cout << "YES\n";
for (pii p: matches) {
cout << p.fi + 1 << " " << p.se + 1 << "\n";
}
}
}
The bug I found was...
I remember that once I was ~20 mins late for TopCoder's round and I was frantically coding Hard in last minutes. It was last minute and my code had a lot of compile errors. When I thought I fixed the last one I didn't even try to compile it and run it, so I submitted it with a few seconds left not even knowing whether it compiles and never running it before. What a surprise that was when it turned out that it indeed compiled and passed sample tests and worked exactly as I wanted! Too bad it was a heuristic approach that didn't get accepted :<. (It was one of the greatest problems ever — "Zero Point Six Three Six" one and it was very tempting to submit heuristic solutions there, but actually they were bound to fail).
Oh man, being late to a round and then running out of time implementing on the hard problem is the worst feeling. :(
Maybe off-topic, but why do you use y-combinator instead of explicitly defining the lamdas with
std::function?Hmm, I copy pasted y_combinator directly from ecnerwala's template so I can't claim to understand its differences or advantages over std::function. It seems to allow anonymous functions, though, so I guess in theory that's an advantage?
why would he pay unneeded overhead?
Could you please elaborate? What overhead are you referring to?
Recursive lambdas are a little hard in a programming language; essentially, each lambda has a unique type, and the compiler doesn't know the type of the lambda until it parses/typechecks the whole body, so you can't really refer to yourself. This is obviously a solvable problem, and there are tricks/exceptions to get around this for non-lambdas with auto-return-type, but they haven't gotten incorportated into the standard for lambdas yet; I think that's coming in C++20 or something.
There are 3 solutions:
It looks like y-combinator is an overhead. Compiler can't get with it like with usual functions. It always passes self as a parameter and can't get rid of tail recursion even on simple example.
I was comparing to std::function, not plain functions. It also involves a function call and more stuff
I didn't really quite get why y_combinator as written not optimized to a loop like a hand-rolled version, though https://godbolt.org/z/1Wba4v
Hm, when I fiddled with flags, the hand-rolled version actually got optimized into a constant "return 3628800". I think the y_combinator might be a bit harder to optimize because there's an extra function call? I'm not too sure, tail-recursion-optimization and stuff is pretty tricky.
Something similar happened to me. In gr9 my last submission(with 20s left) was a compilation error, because I had to add
#define int long longin order to fix overflow and forgot to changeint main()to something else. I would've finally escaped orange yesterday if that didn't happen.Always have "int32_t main()", rookie mistake :D
signed main()is also a good idea. I learned this in a source code that had another great tip on combinatorics --(ans += a*b) %= mod;, summation & modular arithmetics in one place.Doing that modular hack (because I view using fact that "+=" returns reference to ans as a hack) is not a big gain compared to sum=(sum+a*b)%mod
You can just write "main()" instead.
Another common compilation error with
#define int long longisa = max(0, a).