YoungForest's blog

A post-contest write-up.
Problem link

The main references were Kuang Shen’s livestream solution and the official Analysis.

Wiggle Walk

A post-contest write-up.
Problem link

Building Palindromes

Given a string of length N and Q queries. Each query is a range, from which we can get a substring. Determine whether the substring can be rearranged into a palindrome. Since arbitrary rearrangement is allowed, the order of characters in the substring does not matter; what matters is the frequency of each character. If the number of characters with odd frequency is 0 or 1, the substring can be rearranged into a palindrome.
Because N and Q are large, 10^5, a quadratic algorithm will time out. Here we borrow the prefix sum idea to quickly compute character frequencies in a substring.
The time complexity is linear.

Today my high school classmate xl came to Beijing to chat with me. I had lunch and dinner with him and hcq, and we chatted for the whole afternoon. During the morning contest, I only hurriedly finished the warm-up problem. For the second problem, because of carelessness, I wrote the timing of the red change incorrectly and had no time to debug it. I did not even look at the last two problems.
After coming back at 9 p.m., I finally finished the problems, and also found the bug in the second problem.
But in terms of time, it should have been too late.
Rank 1800+.

Overall, although the problems in this contest were not hard, they required time and thinking to solve. These are also the kind of problems I like. Solving a problem that does not reveal its answer at first glance through my own thinking feels great. The thrill is better than godlike mode and triple kills.

5130. Number of Equivalent Domino Pairs

Unlike a blog, a book is relatively more complete and more systematic. Blogs, by comparison, are much more scattered. However, excellent blog series are often adapted into books.
If you want to share larger-scale, systematic knowledge, writing a small book is a good choice.
This article introduces a tool called GitBook, which lets you write a book in Markdown, put it on GitHub, and generate web and PDF versions of the book. Compared with traditional LaTeX, it is simpler and more convenient. It suits contemporary programmers.

The references for this article mainly come from the official website. By comparison, this article is more focused and can help you quickly initialize, write, and publish a book.

Install gitbook command line tool:

This year I still spent my 23rd birthday at school. In the afternoon, I went out with my roommates to watch the movie The Lion King. In the evening, we went to Chengnan Jiushi and ate “Beijing cuisine.” I suppose that counts as celebrating my birthday. Happy birthday to me.
Since I left home at 18 and came alone to the capital to study, birthdays have no longer been as lively and warm as they were at home. Drifting away from home, even though classmates or friends still wish you happy birthday, and closer friends may accompany me to celebrate, the warmth of family is gone. People come and go, and those around you can basically only accompany you for a period of time. At moments like this, I always miss childhood.

Beijing has been especially hot recently, and I cannot help feeling irritable. I keep drifting through life most of the time, then occasionally become full of ambition. I often think about so-called meaning of life, the value of effort, and my own goals.
I can say that I do not have grand ambitions. I read quite a few books from a young age, especially history books. I understood early that I had no connection with princes, generals, and ministers; I am only an ordinary person. What I want now is not much: a place to stand in a big city, and a warm home. This thought is probably also the goal of countless Beipiao people. It is also the motivation behind my hard study.
Recently I have been watching a very popular web drama, The Longest Day in Chang’an. One line in it resonates with me strongly: some people are born Chang’an people, while some people never become Chang’an people even until death. The lives of countless lower-class people in Chang’an in the drama are exactly an allegory for the lives of Beipiao people.

Time passes like a white colt flashing past a crack. In a hurry, half of 2019 has already passed. Looking back at the New Year wishes I wrote half a year ago, some easier ones have already been achieved, while the difficult ones can only be postponed to the second half of the year, or even to next year.

1122. Relative Sort Array

Custom sorting rule.

This morning I had to take the TOEFL exam, so I could not participate in the weekly contest as usual. I solved the problems after the contest.

1108. Defanging an IP Address

One pass. Just replace directly.

1103. Distribute Candies to People

Brute force. Simulate the entire distribution process.

The main mistake in this contest was that I wrote the cmp function in sort incorrectly for the second problem and did not guarantee strict ordering. It kept causing segmentation faults. That is, if a < b, then necessarily b !< a.

1093. Statistics from a Large Sample

I had a Natural Dialectics exam on Monday and a Matrix exam on Tuesday, but still forced myself to make time for the contest. My review itself was not sufficient, and my usual study was not very solid either. I was really taking things lightly.
To enter the top 200, the finish time had to be at least within 1:14:23.

1089. Duplicate Zeros