stevenkplus's blog

when you (think you) fix your bug exactly 1 second after the contest ends...
By stevenkplus, history, 4 years ago, In English

(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.net/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.net/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...
  • Vote: I like it
  • +112
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Oh man, being late to a round and then running out of time implementing on the hard problem is the worst feeling. :(

    → Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Maybe off-topic, but why do you use y-combinator instead of explicitly defining the lamdas with std::function?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    why would he pay unneeded overhead?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Could you please elaborate? What overhead are you referring to?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +55 Vote: I do not like it

        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:

        1. Forward declare the variable as an std::function<int(int,int)>, and then refer to the forward-declared function in the lambda. This has a runtime cost because std::function uses "type-erasure"; it pretty much uses inheritance/virtual functions, so each time you call the function, it has to do a vtable lookup. It also probably prevents inlining.
        2. Use std::y_combinator; this uses a little template trickery with generic lambdas (auto self) to essentially plug in the recursive type correctly. It's nothing groundbreaking, but it has no runtime cost and I think things inline efficiently too. It's a little clunky to use, though.
        3. Provide a builtin mechanism in the C++ spec. I think this is coming soon(TM). http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0839r0.html provides a straightforward mechanism for naming yourself in a lambda, but I think the standards committee is leaning towards http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p0847r4.html which is a more general language feature.
        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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 long in order to fix overflow and forgot to change int main() to something else. I would've finally escaped orange yesterday if that didn't happen.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Always have "int32_t main()", rookie mistake :D

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    You can just write "main()" instead.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another common compilation error with #define int long long is a = max(0, a).

    → Reply