YoungForest's blog

This contest was not hard, but the code was not easy to implement. It was not easy to write bug-free in one pass. What it tested was using a programming language to handle complex logic and various unexpected cases. For example, in the third problem, when the previous dp is 0, the length should be updated to 2; otherwise it should be dp + 1. In the fourth problem, when looking for delimiters under various cases, how should it be handled if none is found?

For the fourth problem, I spent quite a lot of time debugging because of some boundary conditions. I analyzed why it took so long. It is still because I have not written enough code and am not sensitive enough to boundary conditions for variable updates. For example, when string::find does not find a result, how should the other coordinates be updated? I made the mistake that when nothing was found, it returned npos(-1), and current_find_index should have been equal to end, instead of continuing to add the delimiter length on top of -1.

The problem numbers in this contest startled me. LeetCode is really willful, directly starting problem numbers from 5000+. It looks like the room for growth in problem count has already exceeded my imagination.

Back to the point, this contest was also mainly about speed on simple problems.

While grinding problems today, I encountered an interesting one: given a number, repeatedly add the digits until the sum is less than 10. Link.
The problem itself is not hard; recursion or iteration can both solve it. But solving it in O(1) complexity is the real point.

The answer is simple: 1 + (num - 1) % 9.
If you are interested, you can read the proof and extension here: Wikipedia.

This contest was relatively easy. All four problems were routine, and without a Hard problem to separate the field, it came down to implementation speed. You had to finish within 50 minutes to get into the top 200.
I lost some time on the second problem, and for the last problem my first idea was muddled, so I took a bit of a detour.

1029. Binary Prefix Divisible By 5

Last weekend, because I was preparing for Google’s Kick Start Round A, I skipped one LeetCode weekly contest. But I still made up the LeetCode problems that evening. The four problems were not easy, but after thinking through them I solved them independently. It was a small comfort after Kick Start had beaten me into silence.

1020. Partition Array Into Three Parts With Equal Sum

Intuition:
One pass. Find the pivots at 1/3 and 2/3 of the total sum.

[Problem link]

This was my first time participating in Kick Start. Back in undergrad, I had joined its predecessor, Code Jam, with my roommate tls. This year I finally started preparing seriously for the Kick Start series. The reason is that it is one of Google’s channels for selecting software engineers, and Google is my dream company.
On May 22, I attended Google’s campus talk at Tsinghua. At the talk, the seniors also emphasized the importance of preparing for and participating in Kick Start. As a very left-leaning company, Google especially emphasizes fairness. Kick Start is a tool for making recruiting fairer. Compared with other companies’ excessive emphasis on referrals, Kick Start gives students from less advantaged schools an opportunity.

Because of a platform failure, submissions were unavailable for the last 25 minutes. I had already given up one hour early, but I received an email that evening explaining the bug. Without that bug, my rank might have fallen further.
My final rank was 600/3305.
My scores were:

Recently I have been learning how to use google-test and reading its source code. When I ran make install, I noticed that besides installing header files into /usr/local/ and a shared library into /usr/lib/, it also installed two .pc files into /usr/local/lib/pkgconfig/. So what exactly is pkg-config?

From this guide, we can find all the useful basic information about pkg-config.

Overview

The first three problems went smoothly and were solved within 30 minutes. For the last Hard problem, my thinking was quite messy, and even after one hour I still did not solve it.
This contest made me feel that it still comes down to familiarity.
Because I had done similar problems before for problems 2 and 3, I solved them quickly. The second problem even took only 2 minutes!!!

1012. Complement of Base 10 Integer

The scores for this week’s four problems were 4, 4, 5, and 6, so they should not be too hard. Keep going, Forest!

Because the problems were too simple, even though I finished 15 minutes early, my rank was still 912 / 4712. This contest was really easy, and it completely tested coding speed and familiarity. Whether you can get it bug-free on the first try matters a lot. If a corner case is wrong, debugging it takes a lot of time. I got one wrong answer on both problems 1 and 2, which cost me quite a bit of time.

Today I tried recording video while solving problems. Due to venue limitations, I could not use a microphone to explain, so the result was barely satisfactory. Although I could compensate a bit with text annotations, the biggest advantage of video communication was lost. In the future, I should still focus on blogging to spread my thoughts.
Especially since this time I only solved two problems. I attempted both of the last two problems, but failed on both. The video effect was too poor. If people watch videos on Bilibili, they are there to see the uploader show off. This time I did not manage to show off and instead met my Waterloo, which was quite embarrassing. But in the end I still plan to upload the video. I am just that thick-skinned: not afraid of embarrassment, and not afraid that future people will dig up my old shame.

My rank also directly flew beyond 1500. My ranking this week is probably going to drop.

Result: