when you (think you) fix your bug exactly 1 second after the contest ends...

Revision en6, by stevenkplus, 2020-08-30 20:32:53

(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.com/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.com/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...

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English stevenkplus 2020-08-30 20:32:53 719
en5 English stevenkplus 2020-08-30 20:01:56 2
en4 English stevenkplus 2020-08-30 20:01:34 19 Tiny change: 'ved it at exactly 09:35:01:\n~~~~~\n~' -> 'ved it at 2:00:01...\n~~~~~\n~'
en3 English stevenkplus 2020-08-30 20:01:10 84
en2 English stevenkplus 2020-08-30 20:00:33 120
en1 English stevenkplus 2020-08-30 19:59:41 2343 Initial revision (published)