06 September 2020

Codeforces Round #668 (Div. 2) Postmortem

Trying a different format with problem-by-problem breakdowns, which hopefully will be more useful when I review my postmortems. I will also backfill the postmortems.

A: I first implemented the metric computation (sort sums of adjacent elements) without having any idea of how to create a different permutation to achieve the same metric. Then I realized that reversing the input preserves the adjacent sums. I won't complain about a 0:02 submission.

B: If the first nonzero element were negative, then we have to incur cost equal to its magnitude. I thought this was it, but some sample inputs didn't pass. Then I noticed that if the first nonzero element were positive, we can add the magnitude to negative terms later in the array, which existed because of the constraint that all elements sum to 0 and that the sum stays 0 after every operation. I quickly patched my solution to keep a reserve from the magnitude of positive elements and using the reserve to decrease the cost of negative elements before incurring their costs. Again, not complaining about a 0:08 submission.

C: This is where I started to struggle. Having the same number of 0s as 1s in every K subarray is the same as the subarray sum equal to K/2. I got hung up on the "system of equations" representation, where every question mark was a variable (question mark at i would be a_i), which seemed extremely hard to solve. Then I thought that I can just look at the number of equations and the number of variables, which seemed sketchy, but I YOLO-ed and incurred a WA.

At about the 0:55 mark, I realized that the system of equations implied that a_i = a_j for i = j mod K. Facepalm. I quickly coded this solution for a 1:02 submission. RIP

D: Clearly, if B is at most DA away from A, then A can reach B in the first move and win. From the problem statement, I inferred that their 10^100 limit meant that either A will reach B in finite time, or B can always move to stay DA away from A. I quickly realized that the best chance of B dodging A is on the diameter of the tree, since in no other scenario will B have the space to run away from A. This implied that if A can go from the center(s) to the ends of the diameter in DA, then A can catch B.

I made the assumption that if DA > DB (it seemed intuitive), then A will be able to reach B eventually because B will run out of space. Thinking that these three criteria were sufficient, I submitted at 1:31 for my first WA on D. Given feedback that my solution failed pretest 2, I came up with the following counterexample to my solution:

1---2---3---4---5---6
        ^           ^
        A           B
DA = 2, DB = 3

My solution would incorrectly say that A never reaches B, while after two moves, A will first move from 3 to 5 and B will move from 6 to 3, letting A move from 5 to 3 on the third move. This really tripped me up, leading me to think about the relative difference between DA and DB. I tried that if the relative difference is larger than the half the diameter of the tree, then A cannot catch B, for another WA at 1:44. Finally, as a last ditch attempt, I thought that if DB is twice or more than DA and if the diameter is greater than twice DA, then A cannot catch B, for my third and final WA at 1:59.

25 June 2020

Educational Codeforces Round 90 Postmortem

What went well
  • B, C, D took me 5 minutes, 9 minutes, and 24 minutes respectively.
What went poorly
  • A took 21 minutes (drew a huge blank; no, I did not wake up late), which was a massive penalty, since it increases the penalties for B, C, and D.
  • Couldn't get E in an hour.
Where I got lucky
  • D was on the easier side.

23 June 2020

Codeforces Round #652 (Div. 2) Postmortem

What went well
  • 0:00 submission for A!
  • Got ABCD (albeit slowly).
What went poorly
  • Incurred one wrong answer for B and C each (and took a long time too).
  • Took half an hour to recognize the recursion for the tree structure in D.
  • Thought that the residues of numbers compare the same way as the the numbers themselves (i.e. a > b implies (a % m) > (b % m)…no, just no).
Where I got lucky
  • Got D with 9 minutes to go, which involved a slight wild guess.

21 June 2020

Codeforces Round #651 (Div. 2) Postmortem

What went well
  • Decently fast ABC (0:01, 0:10, 0:23).
What went wrong
  • Walled by D. I didn't recognize that binary search works because I didn't know how to verify that a subsequence with max less than or equal to a target value was doable in O(N).
  • I thought incorrectly (yet again) that O(N lg N) is too slow for N <= 10**6, so I tried something silly to find the minimum # subsequences of the form (01)+ or (10)+, when a straightforward O(N lg N) would have worked.
Where I got lucky
  • Gained rating!

13 June 2020

Bugforces (ft. senile logarithmic exponentiation)

Sad things happen when you lose your mind:
using i64 = long long;

// Precondition: (base, exponent) won't cause overflow
i64
my_pow(const i64 base, const i64 exponent)
{
  i64 accumulator = 0;
  for (i64 exponent2 = exponent, current_power = base; exponent2 > 0;
      exponent2 >>= 1, current_pow *= current_pow)
  {
    if (exponent2 & 1)
    {
      accumulator += current_power;
    }
  }
  return accumulator;
}

04 June 2020

Codeforces Round #647 (Div. 2) Postmortem

What went well
  • Got B in 5 minutes -- straightforward problem.
  • Got C in 5 minutes -- another straightforward problem.
  • Got D in 20 minutes, once I figured out how to read. :-P
  • New personal best!!!
What went poorly
  • Wrote an extremely clumsy solution for A because I decided after a brief tradeoff analysis to match the problem statement as close as possible instead of thinking about a better implementation
  • IlliterateForces strikes again -- misread D, so submitted a solution that solves a similar problem, which cost ~20min and a submission penalty.
  • Couldn't get E.
Where I got lucky
  • Got extremely lucky with B and C. I have been struggling with Bs recently; this B's 5 minute solve time thankfully bucks the trend. My previous fastest C solve time was ~15 minutes.

26 April 2020

Bugforces (ft Education Codeforces Round 86)

Consider the following implementation to find the smallest multiple of x at least as big as y:

typedef long long i64;

i64
next_mult_ge(const i64 y, const i64 x)
{
    return ceil(y / (double) x) * x;
}

What can go wrong?

Educational Codeforces Round 86 Postmortem

What went well
  • Sampling other submissions, my solution to C is cleaner and more intuitive (if only it worked!!!)
What went poorly
  • A took a long time
  • My C implementation died to nuances of ceil(); I wanted to find the multiple of a number at least as large as some threshold.
Where I got lucky
  • I was able to use fast-slow testing to determine a test case that breaks my C.

25 April 2020

TopCoder SRM 784 Postmortem

What went well
  • I was able to solve Div2C/Div1A.
  • I was able to fix a bug in my implementation for C.
What went poorly
  • Got A wrong because I couldn't understand the problem.
  • I realized the bug in my C after submitting my code, so the resubmission incurred a significant (200pt) penalty).
Where I got lucky
  •  Div2C/Div1A seemed a lot easier than usual.

14 April 2020

Codeforces Round #635 (Div. 2) Postmortem

What went well
  • A was trivial.
  • B was easy.
  • I didn't feel stuck when attempting D.
What went poorly
  • C took a long time because I didn't realize that I had to consider two criteria for the greedy solution (first Wrong Answer). Then I didn't realize that the two criteria were not mutually exclusive (second Wrong Answer). All said and done, I spent 1h30.
Where I got lucky
  • Somehow still above 1700!