Good Bye 2019 Postmortem

Link to contest here

What went well

• I managed to prove that my solution to B is optimal.

What went wrong

• Proving that my B solution is optimal took close to an hour.
• I wasn't sure what to do with C. After expressing the sum as S and the xor as X, I first fell into a trap thinking that I can do it with one number, i.e. S + a = 2*(X ^ a). Nothing really came to mind. Then I thought about using two numbers, i.e. S + a + b = 2*(X ^ a ^ b), where I use a to get rid of S, i.e. make the bits of S be all 0s or all 1s. This led me to think about the lowest power of 2 greater than S, but nothing came to mind. I also never thought about using a to get rid of X, i.e. maybe set a = X, which then leads to a really nice solution S + X + b = 2*b, i.e. b = S + X.

 Where I got lucky

• A is a 3 minute problem!

COLDforces Round #611 (Div. 3) Postmortem

Link to contest here

What went well

• The contest was at 9am local time, so I had a good 2.5 hours to wake up.

What went wrong

• I was ill with a cold (laryngitis?!)
• My solution to E died to a silent index out of bounds!!! Time to switch to vector<T>::at() instead of vector<T>::operator[]?!
• I did not think of a working solution for C during the contest, but did so after the contest (and doing the obvious greedy solution worked and was easy to prove correct…) The junk that I submitted managed to pass system tests, but eventually got exposed by the serial hacker, who hacked over 20 C submissions!

Where I got lucky

• I got my first 1 minute submission!!
• C was such a massacre that I managed to gain elo despite solving only 3 problems! Back to blue again!

Educational COLDforces Round 79 Postmortem

Link to contest here

What went well

• Nothing really…

What went wrong

• I was still ill with a cold (laryngitis?!)
• I took a few passes to understand B; I misread the problem the first couple times. Eventually I got the problem after nearly an hour.
• I didn't realize that I misread C until after the contest. I thought one can remove multiple presents in between popping and pushing back the unused presents.

Where I got lucky

• A was back to a straightforward 3-minute problem.

COLDforces Round #610 (Div. 2) Postmortem

Link to contest here.

What went well

•  I was able to figure out a clean solution for B2.

What went poorly

• I was ill with a cold (laryngitis?!)
• I wasn't sure how to do C because I wasn't able to prove optimality of a solution.

Where I got lucky

• Not today

Educational Codeforces Round 78 (Div. 2) Postmortem

Link to contest.

What went well

• I got A in 3 minutes.

What went poorly

• I wasn't sure how to prove B during the contest. Then I decided to binary search when a linear search would have run in time. However, I had a bug in my binary search because I needed to look at particular residues mod 4, which required extra debugging to get right. All this took…1.5 hours.
• I was completely wrong for C because I didn't realize that not all larger subarrays may work.

Where I got lucky

• Apparently I probably won't lose too much elo.

Codeforces Global Round 6 Postmortem

Link to contest.

What went well

• I solved A, B, C.

What went poorly

• I don't know the properties of natural numbers divisible by 60. My solution is so disgusting that I would happily nominate my solution for this year's Wall of Shame. 
• I misread B and thought that the tower of dice was visible from just the front, instead of both front and back.

Where I got lucky

• I didn't lose much elo for a mediocre showing.

Codeforces Round #607 (Div. 2) Postmortem

Link to contest.

What went well

• I solved A in 2 minutes.

What went wrong

• I was too hasty on B, leading to two wrong submissions, and took a total of over 20 minutes.
• I took over an hour on C because I wasn't clear at all about my recurrences and starting values. 

Where I got lucky

• Everyone else sucks more at math, so a slow C with one penalty got me in the top 400 (top 6%).

Codeforces Round #604 (Div. 2) Postmortem

Link to contest.

What a dumpster fire of a contest.

What went well

• I got B quickly.

What went wrong

• I didn't know how to solve A, so came up with a horribly convoluted solution with lots of cases. This and weak testing resulted in an incorrect submission, but I realized my mistake after the Wrong Answer verdict and patched my solution.
• C was evil because it had ample opportunity for off-by-one errors, one of which killed my solution.
• My attempt at implementing D yielded a giant pile of spaghetti, which was unsurprisingly wrong.
• E is definitely doable in 20min start to finish, but my combinatorics skills isn't strong enough for me to write down the recurrence after reading the problem.

Where I got lucky

• What luck?!

Codeforces Round #603 (Div. 2) Postmortem

Link to contest.

What went well

• I got ABCD.
• Expanding on getting ABCD, I got C and D fairly quickly, at T+36min and T+48min respectively. (Then again, D was not particularly hard, as evidenced by its 1500 rating).

What went wrong

• I didn't get A until T+1h30 and two wrong tries.
• I did not upload anything for E because my fastest solution sketches were O(NlogN), which I thought were too slow for N = 1,000,000. Turns out that O(NlogN) and a good constant factor is fine for such large N.
• I also misread E: I thought that the cursor can be moved to the left of the starting position, but the problem clearly says that it can't.

Where I got lucky

• Implementing C and D went very smoothly, taking 12min from end (open problem statement) to end (pretests passed).
• E felt approachable.

Educational Codeforces Round 77 (Div. 2) Postmortem

Link to contest.

What went well

• I didn't give up.
• I quickly figured out the approach for D, which was binary searching for the answer.

What went wrong

• I got A four (!!!) minutes before the contest ended (at T + 01h56).
• I didn't get D.
• I incurred a lot of penalty from wrong-answering B (twice) and C (once).
• I had no milk for my pre-contest coffee.
• I felt pretty awful waking up at 0530 to do the contest.

Where I got lucky

•  The contest was hard for everyone else, so I only lost less than 50 elo for my poor performance.

A Taste of Quantitative Trading

Think you're interested in quantitative trading? Try your hand at this problem, courtesy of E6 Trading:

Two card players have hand strengths distributed independently & uniformly over [0, 1] and are playing for an existing pot of $100. Player 1 can check or bet $100. If Player 1 checks, the player with the stronger hand wins the pot. If Player 1 bets, Player 2 can call the bet or fold. Given both players are risk-neutral paperclip expectation maximizers, how does each play?

Codeforces Round #597 (Div. 2) Postmortem

Link to contest.

What went well

• I solved C and D relatively quickly. 
• I was pretty close on E1.

What went wrong

• I didn't get B.
• B had more than 2 errata.
• I didn't read E2 before I started to think about E1. This time, E2 was simply the same problem, but with higher limits.

Where I got lucky

• Fewer people than usual solved D, so I managed to get rank #401 (top 4%) with just ACD. Normally ranking that high needs a reasonably fast ABCD.

Pattern Matching Wildcard Commentary

While reading Google's Haskell training, I encountered some code for the function (&&), which I thought was mildly unintuitive:

(&&) :: Bool -> Bool -> Bool
True && y = y
_ && _ = False

The reason I found this definition odd is that the author chose to use a wildcard (the first underscore in the second line) instead of the explicit data False. Since Bool only has two choices, True and False, I think explicitly using False instead is more intuitive, since I had to think about the other values that the wildcard can take on besides False. Furthermore, the Haskell compiler, ghc, will validate whether all patterns are matched in the function definition.

Thus, I would rewrite the function as:

True && y = y
False && _ = False

*

Additional commentary:

Brian Hamrick likes when the wildcard is conceptually a catch-all, i.e.:

True && True = True
_ && _ = False

At first, I thought this best describes the logical truth table, where the only True result is from the inputs (True, True). However, this changes the laziness properties of the function in Haskell: the second argument is forced to evaluate when the first one is True since we do not have enough information to match (AN: this was not obvious to me at first). If the second argument is True, then we match the first line; otherwise, we match the second line, so the second argument gets reduced to weak head normal form (WHNF).

*

Thanks to Brian Hamrick for help with this expository post.

thank u, next

2018 was crazy. May 2019 kick it up another notch!