competitive – Writing

Removing Gacha: II, an expectation problem

This is a continuation of the last post. Let’s slightly modify the process: stop when the box becomes empty. And what is the expected number of steps for this process? The first ball This is trivial. Whichever other ball is chosen, we always put it back. So until the first ball is chosen (and dropped),… Continue reading Removing Gacha: II, an expectation problem

Removing Gacha: I, a probability problem

The actual problem is here on atcoder. I’ll build a solution from the bottom up. So here we go. Let’s say we have N balls (numbered 1 to N) from a box, and we do the following: And by the time the process is stopped, what’s the probability that the N-th ball has been taken… Continue reading Removing Gacha: I, a probability problem

Codeforces Hello 2022: Weighted Increasing Subsequences

Problem link: https://codeforces.com/contest/1621/problem/G I first started with a simpler subproblem: some properties of all increasing subsequences up until i, more specifically, the number of unique sequences and the sum of the length of them. It’s not hard to see we can solve this by some tree structure. (i.e., if before i, the number of unique… Continue reading Codeforces Hello 2022: Weighted Increasing Subsequences

GCJ 2021 R1A

I’ll recap my participation in Google Code Jam 2021 Round 1A here. The performance is not too impressive. If I weren’t able to fix a silly bug and submit in the last minute, I wouldn’t have advanced to the next round. At the beginning of the contest, I also wasted 20 minutes for the easiest… Continue reading GCJ 2021 R1A