My First Competitive Programming Contest

I have heard of this website and its contests quite long ago, but I never was very into competitive programming, or thinking that it wasn’t very useful in product-based careers such as what I was targeting. After quitting a job that frankly, was completely different from the Job Description, I was promised Business Analyst-type of consultant, but it turned out to be telemarketing which was the thing I hated to do the most.

For more details on why I quit and what lessons I learned from just three days there, you can checkout this journal entry. But in short, I learned a few lessons that, to put in perspective, probably worth my three days sitting there:

Act 1. Testing the Waves

There was really no reason why I chose to do it. I just looked at the time, and the unrated Easy Daily Training contest was about to start, and thought, how bad could it be, and signed up. It was the AtCoder Daily Training, Easy on October 1st. Literally two days ever since I quit the aforementioned job. (I did it in Python, just to let you know how oblivious I was to competitive programming.)

There were only 30-ish signups, which was expected from a daily thing, let alone the easy division. I just didn’t want to head straight to the All division, just simply wanting to see what it is, since I only heard of LeetCode and the cult surrounding it.

This was a huge breath of fresh air. It felt very similar to what I felt when I discovered Advent of Code, while everyone else was grinding LeetCode. AoC was truly something special, doesn’t matter what tools you have, doesn’t matter what language you use, as long as given the input, you can find out the answer. The diversity of the puzzles is also hugely varied, numbers, operators to strings. I immediately dropped LeetCode ever since the first year of university.

I also have a repository dedicated to this event here, where each year I would be able to do something wildly different thanks to the nature of the event. For example, in 2023, I tried to do 25 different languages for 25 different puzzles. In 2016 (unfinished) and a redo of 2015 (finished), I did everything in Dyalog APL. And in the last 2 years, 2024 and 2025, I tried to do everything in Uiua (a stack-based array language that focuses on tacit programming), but had to get help from Python for certain puzzles, such as scipy.optimize. You can also read up how one problem in AoC, can be solved with OOP, Functional Programming, Procedural and Array Programming here from my writeup!

The problems are not difficult at all, fitting for the easy league:

1. Full House: Given 4 numbers, decide if adding another number would make a full house (that is a triplet and a pair). For example 1 1 1 3 would be possible, by adding a 3.
2. Generalized ABC: Given a number from 1 to 26, generate the letters of the capitalized alphabet. For example, 4 would generate ABCD.
3. Explore: Given a set of rooms with each room move having a time cost, arrivals into certain rooms might grant more time. Decide whether it’s possible to reach the end. This sounded like a pathfinder at first, but until you realize the set of rooms is essentially a singly linked list, then it’s just one iteration.
4. Hurdle Parsing: Given a string, find the sequence of numbers that generated it. Start with a |, then for each number, generate as many - and a | afterwards. This sounded like being worded oddly, but essentially it’s just splitting at | and counting -s.
5. Even Digits: Given a number $n$, print out the $n$-th “even digit number”. The sequence goes as followed: $0,2,4,6,8,20,22,24,28,40,...$ (where each digit in the number is a sequence).

I originally had some trouble with the 5th problem, but knowing the constraints of how $n$ can be, it’s safe to say that an exhaustive search will never work. So I started looking other ways, whether given $n$, we can reconstruct the number.

I wrote down the sequence on a notebook to the $20$th number, and started to notice that they come in groups of 5s, and the only meaningful boundary is at 8. My first intuition, given that, it means for the $n$-th number $A$ if it didn’t end in 8, then the $n+1$-th number is always $A+2$. I started prototyping a piece that generates numbers in chunks. Which, led to the next discovery.

These numbers appear in chunks of 5. $0$ to $8$, then $20$ to $28$, and so on. I noticed that doing $n \mod 5 - 1$ would get me the last digit. This gave way into another intuition that we could reconstruct the number directly piece by piece, rather than finding where it is like the first method I had.

Something else that I really liked about this kind of input and output that relies solely on stdin and stdout, is that it’s very easily testable, and doable in many types of languages. In fact, I had full intentions to go with Uiua for this contest, but because the Uiua Language Server was having an off day, so I went with Python (which was extremely popular in AoC, so I figured it applied here). The flexibility of stdin and stdout allowed you to do it in whatever IDE you fancy, instead of the weird editor LeetCode has. In fact, some may say that you can do LC in IDEs also, but it was so odd having to parse input properly just to pass into the function LC expected.

After the contest, I had some chats and started reading up editorials, I learned one thing that surprised me greatly, is that it seems like C++ was much more favored in this scene. I always knew C++ was something verbose as I did use a wide range of features for my C++ game, and came into a lot of best practices. But turned out, competitive programming doesn’t need those best practices. You won’t get TLEs on high copy counts rather than moves most likely, but you get TLEs on bad solutions.

Act 2. Testing the Ships

The next day, I decided to go from the Easy League to the Open League, hence I signed up for the AtCoder Daily Training ALL. There are 9 problems, against 30 people who signed up. I finished 6 of the easier problems and got 1200/2550 points. Funnily, I was actually 30 minutes late to this, because I had something going on, and finished those 6 problems in 35 minutes. The others started to get too difficult for me.

I also started using C++, rather than just Python from now!

1. Happy New Year 2025: Given $A$ and $B$, output $(A+B)^2$. This is trivial.
2. Double Click: Given $N$ clicks and $T$ delay limit. For the next $N$ clicks, find out when the first double click happened, where a double click happens when two clicks are shorter than or equal to $T$. This is also trivial.
3. Typo: Given strings $S$ and $T$. Find out whether $S$ can be transformed into $T$ by swapping places of two adjacent characters. This is also trivial.
4. Racecar: Given $N$ strings named $S_1,...,S_n$. Find out if there are ANY combinations of $(i,j)$ where $i \ne j$ that $S_i + S_j$ is a palindromic. This starts to look odd and no longer trivial, but seeing that $N$ and $|S_i|$ is constrained under $100$, it’s safe to brute-force.
5. Change Schools: There are $K$ classes, with each having $A_i$ students, totaling $N$. If there is one transfer, which class should he be transferred into, so that after the transfer, there are no classes having a strictly greater number of students. Output all classes that make the criteria.
   • I assume that the naive approach would be to add to each class, then loop to find whether there is a class with a higher count? But I think anyone would be able to see that, it just means that any classes that have $C$ students where $C >= max(A_i) - 1$ would satisfy the condition. At most two loops.
6. Cards Query Problem: Given $N$ empty boxes. Given $Q$ queries, for each query, it can either be: type 1, writing a number $i$ onto a card and inserting it into box $j$; type 2, output all cards in box $i$ in ascending order; and type 3, output all boxes that have card $i$ in ascending order. For type 2 queries, all cards must be presented regardless of duplicates, but for type 3 queries, it must be deduplicated.
   • I think the intuition anyone is going to make here is that, we can’t really have a way to calculate all the way to the end without simulating the problem. So the problem turns into how to optimize lookups, rather than how to calculate the answer. From the two types of queries, we know we need a two-way map or two separate maps tracking boxes and cards. That should be all needed. C++‘s set and std::lower_bound helped tremendously.
7. Tail of Snake: Given tree number sequences $A$, $B$ and $C$ of length $N$. Select $(x,y)$ where $1 \leq x < y \leq N$, so that $\sum_{i=1}^{x}A_i + \sum_{i=x+1}^{y}B_i + \sum_{i=y+1}^{n}C_i$ is the snake length. What is the longest snake that can be created this way?
   • This problem, I couldn’t solve. I had some intuitions, such as it’s basically wording to be to maximize each subarray so that their sum is max. A brute-force won’t work, but since we have concrete $A$, $B$, and $C$, a cumulative sum of some kind may be helpful, but that’s as far as I got.
8. Sandwiches: Given a sequence $A=(A_1,A_2,...,A_N)$. Find out how many triplets $(i,j,k)$ that satisfy: $1\leq i < j < k \leq N$ and $A_i = A_k$ and $A_i \neq A_j$.
   • This problem, I couldn’t solve. I imagined it looked like some sort of symmetry, since the middle $A_j$ has to be different, and if there was a way to cut down pairs of same values $i,k$ or different values $i,j$, that might help solve the problem. But that’s as far as I got.
9. Sum Sum Max: I don’t even understand the problem statement. But, it seems that you are given elements that make up sequence $C$. Then you find sequence $B$ which is defined as the cumulative sum of $C$. Then do it again for $A$ with the cumulative sums of $B$. Print out the max value of $A$. There are $k$ test cases, print out the values for all test cases.
   • This sounds probably deceptively simple. Since $B$ and $A$ can be trivially calculated. It just seems like the problem of how to properly construct $C$ according to the statement while heeding TLEs and MLEs (arrays can be as big as size $10^9$), and calculating cumsums based on whatever structure you used to keep $C$ and $B$.
   • I tried doing this problem, but of course I couldn’t solve. I tried to keep $C$ as a vector of pairs $(a,b)$ where $a$ is the value, and $b$ is the repeat count. Then tried to construct $B$ naively and $A$ naively, which was the problem. I guess we also still need a way to keep a cumsum array under the time limit, that is still possible for $A$ to be calculated to get maximum element.

I finished 20th out of 30 people. Bottom half, exactly where I expected I would be, since I have no experience in competitive programming, and frankly, haven’t done any programming for a few months. This feels the need to reiterate, that if I stayed in that telemarketing job, this kind of skills that I already don’t have much, will start to deteriorate and close all any doors to more senior developer positions.

Act 3. Sharpening the Blades

Knowing that the next day would be the actual Weekly Contest, I started to look over some solutions, editorials, and even trying to upsolve a few problems in those virtual contests I had.

I did a lot of virtual contests, adhering to all the rules to see how far I can usually take before I break, and which types of problems would cause that. I learned a few small things during those 24 hours before the Weekly Contest:

1. There are helpers and extensions that can streamline the running and testing process. Which admittedly took a bit of time typing clang++, and pasting in the correct inputs.
2. Including bits/stdc++.h and namespace std allows a lot to be truncated, much faster than including one by one.
3. Apparently cumulative sums are very useful in a lot of problem types.

Act 4. The Grand Line

Is it obvious I have been watching One Piece Live Action? Can you guess which character is my favorite?

To put it short, I was humbled.

7 problems, and I solved only 2, stuck on 3rd and 4th. With 2 submission errors, I got penalized by 10 minutes, leaving position #6500 out of 9300 participants. Again, bottom half, what I totally expected. I thought I saw what made the 3rd problem solvable, but I wasn’t able to implement it, and it didn’t seem correct according to the editorial. I actually still don’t understand the editorial for the 3rd problem. It just seemed difficult to imagine why that would be the case.

Problem 7th and 6th, I don’t even know what it was talking about, some convex points in 2D space, or finding the number of trees that satisfy a condition. I saw that the latter required the answer to modulo some constant, that’s literally a flag to tell me to not try this problem for now.

What I got annoyed at, was the 3rd and 4th.

• Sort Subarray: Given a sequence $A=(A_1,A_2,...,A_N)$ and $K$ where $K< N$. Are there any continuous subarrays of length $K$, so that when that subarray is sorted, the sequence itself is in a sorted state also?
  • It’s obvious to anyone that brute-force and simulation is dead on arrival. I noticed that, whatever subarray start you pick, you always split the sequence into exactly three parts, namely $B,C,D$. As long as $B$ and $D$ is already in a sorted state, and that $\max(B)\leq \min(C) \land \max(C) \leq \min(D)$. Sorting isn’t actually necessary.
  • I tried to optimize it, by precomputing mins and maxs, as well as noticing that if you run from the start to $i$ where $1 \rightarrow i$ is sorted, and vice versa with $j$ from the end. If $i$ and $j$ are further from each other than $K$, it’s never possible. But I could never reach the end.
• Range Set Insertion Query: Given $N$ empty sets $S_1,S_2,...,S_n$. Given $Q$ queries, where each query, $(i,j,x)$ will adds $x$ to all $S_i$ to $S_j$. After all queries, output the number of elements within each set.
  • Again, super obvious that simulation will fail. I tried to do range-based calculations, and merging ranges afterwards, then counting how many ranges fall into the correct set. But it ended up being TLE still. I gave up on this problem.

Epilogue

Of course, this is only the start. I feel great being humbled. It makes you feel like you have lots to learn more.

At the last telemarketing job, I was ashamed when amongst peers. The boss said that it was because I was not good at the talk, so that’s why I was withdrawn, and also why I never felt withdrawn before in other technical activities because I was always the best. Now that I see it, I think the answer was much simpler than he and I thought. It was that, I never liked it in the first place. But this? Getting humbled by people who have been finalists at crazy competitions that write code akin to mathematicians’ notes? It feels great.