YoungForest's blog

This round was the second-to-last round of the year, and also a relatively easy one.

I solved the third problem and the small data sets for problems 1 and 2. My algorithm for the second problem was correct in itself, but I did not correctly estimate the maximum number of bits in k or prevent overflow, so I got WA on the large data set. The first problem was not hard either, but I was not sensitive enough to divisors, so I missed the better solution. Overall, this was the closest I got to AC in a round. My luck was relatively good, and I finished the contest one hour early. Later, because I really could not think of more solutions or details to watch out for, I gave up.

Book Reading

1221. Split a String in Balanced Strings

Understand the definition of balanced, and you will find that we only need to find positions where the counts of L and R are equal.

Time complexity: O(N),
Space complexity: O(1).

Solved the problems after the contest.

1207. Unique Number of Occurrences

Record the number of occurrences of each value by unordered_map.
Check the unique using unordered_set.

Last Friday happened to be September 27, the holiday for the French-speaking region of Belgium. The school was closed, and with the weekend we had exactly three days off. On the train back from Amsterdam the previous week, we decided on this trip to Paris. The members of this trip were: me, zfn, lsd, and wyd.

Overall feeling: I like Paris so much. I love Paris.
Here, I deeply felt France’s cultural confidence.

In the first week after arriving in Europe and settling down, we went to beautiful Amsterdam in the Netherlands and two surrounding villages.
Because it was our first trip out, many parts of the itinerary were poorly arranged, and the cost was relatively high. It was about 450 euros per person. By comparison, the Paris trip a week later only cost 300 euros, and the experience was even better.
I think the Netherlands is absolutely the best place to enjoy Northern European countryside scenery.

The people on this trip were: zfn, lxf, lsd, zjz (Director Zhang), and me.

Day One: Settling in Giethoorn

Last weekend I was in Belgium, and the contest time was from 4:30 a.m. to 6:00 a.m. The timing was unsuitable, so I did not participate. I found that only the biweekly contest time, Saturday from 4:30 p.m. to 6:00 p.m., is somewhat suitable. My goal of ranking 2000 this year is probably going to be postponed. Even in the best case, the number of contests I can participate in is only one-third of what it would be in China.

1189. Maximum Number of Balloons

Just count the frequency of each letter. Note that l and o each need to appear twice to form one balloon.

In the second half of this year, I was fortunate to have the opportunity to come to Belgium for an exchange semester, about five months.
This is my first time going abroad for such a long period. Previously I also participated in a school program and went to the United Kingdom for a half-month study tour. For details, you can read Thoughts and Observations from My Study Tour in Britain, which I wrote three years ago.
Next, I will summarize my exchange program from four aspects: city, life, study, and travel.

City

Liege is in the southeast of Belgium. It is also the capital of Liege Province, borders Luxembourg, the Netherlands, and Germany, and is the third largest city in the French-speaking region of Belgium. Many students who go to Europe for study worry a lot about local public safety and their own safety. However, Liege is a very safe city. In Europe, the smaller the city, the safer it tends to be. In places like Paris and Brussels, the probability of encountering danger may be higher by comparison. I once almost had my bag stolen in Brussels. In a small city like Liege, cars on the street will actively yield to pedestrians. Sometimes an entire bus waits for me to cross the road, and I feel a little embarrassed, so I speed up my steps. Although aging in Europe is very serious, Liege is a university city, so that feeling is not obvious. There are still many young people, and the whole city is full of vitality.

This was my last contest while still in China. Because of the time difference in Belgium, the weekly contest there is from 4:30 a.m. to 6:00 a.m. every Sunday. So I do not really have the conditions to participate, and can only get up on Sunday mornings to solve the problems afterward.

1184. Distance Between Bus Stops

Overall, the experience was very happy and I gained a lot.

I was very lucky to attend this year’s Byte Camp. I think this one-week event was the most meaningful activity I attended this year. This year’s summer camp was divided into three tracks: Engineering, Algorithm, and Product. I participated in the Engineering track.

Selection for the Engineering and Algorithm tracks was completed through a written test and interview. The written test questions were also the same, completed online through the Nowcoder platform. There were two opportunities for the written test; if you participated in both, the higher score was used. The written test was divided into basic questions (Operating Systems, Computer Organization, Computer Networks) and programming questions. There were four programming questions, with increasing difficulty. I participated in the first session and ACed the first three. The difficulty was roughly equivalent to LeetCode Medium. The difficulty of the last problem directly jumped to ICPC World Finals level, requiring knowledge of min-cost flow. I had never done ACM, and it was my first time hearing about min-cost flow, so I could not solve it. Because my written test was okay, I did not attend the interview and directly got camp admission. However, according to classmates who attended the interview, the interview was also quite easy and low in difficulty.

Problem description

This problem was one I encountered in my Google intern phone interview in February. At that time I solved it in a very messy way and failed the first round directly. Today, after seeing a classmate’s explanation, I decided to try this problem again. After all, in the past half year I have solved 500+ problems, and my algorithm ability has grown somewhat. I only saw the problem title in the explanation, not the content, so I guess I was able to solve this problem independently half a year later. After AC, I actually cried, sad about how insufficient my ability was back then. I do not know whether I will have such a good opportunity again.
In these six months I also participated in Kick Start three times. Except for receiving a resume notification in Round A the first time, I failed in both Round D and Round E.
As I have said repeatedly before, I really want to go to foreign companies like Google and Microsoft, and I have also put half a year of effort into it. I hope hard work will pay off. If I can get a Google or Microsoft summer internship next year, I will reward myself with a self-guided trip to South Korea during the Dragon Boat Festival holiday. A childhood friend is there, so I can go visit her.

The idea of this problem is as follows: