It's over. It has been five years from my first glance on computer programming and OI. It is really hard to admit, but I did have finished my trip in OI after my second but last GDOI and my first but last APIO. The first part of all, is about GDOI 2018.
Different from last year, I didn't abandon my lessons to prepare for GDOI because the mid-term exam is just at the week before it, just like NOIP is at the weekend before the mid-term exam last term too. However, I also spent a lot of homework time to learn about some other algorithm like KMP and ACAM. At 15:30, we left school in the fog in Guangzhou. After a-hour rolling up and down, we arrived at our hotel at almost 17:00. Can you imagine how a floor had 88 rooms? Some of them were lack of windows. The bed was smaller than usual ones. And there were even some rooms with circle beds (Luckily our bed was rectangular)! As Luo Yibin, a student in junior high school, and I lived in the room with a single bed, I decided to sleep on the sofa. As we got two rooms without windows, Mr. Liang Zexian and Mr. Yao Xiaohao decided to find another hotel to sleep in though it will be farther to reach the school. But that's the details. At 18:00, we went to the host school, Zhongshan No. 1 Middle School for dinner. In the school, Wen Jianwei introduced his friend, Huang Zheng from Zhongshan No. 1 Middle School, to me. He led us to visit the school. Boringly at night, Day 0 is over.
My mobile phone woke me up at a quarter after 6. The breakfast is not as good as it was last year and the food was once eaten up. Mao Hongxi overslept so we set off at 07:30. Because Mr. Yao and Mr. Liang stayed in a hotel which requires a taxi to go to the school, Ms. Yao Xiaohua led us to school. The competition started at half past 8. I was surprised that the first problem was much easier than I expected. You needed to divide an array into several part with equal sum. It could be easily solved by enumerating the division of the sum of the array. You can use the prefix sum to make it faster. The second problem was that you were given a lock that you could add 1 to all numbers in a range or subtract 1 from all numbers in a range. The question was how many operation you needed to take at least to unlock it (the password is all 0). Having no idea, a BF solution was provided. The third one was that there was a tree with apples that apple at the root of the tree would be picked in the morning, the apple would move to his father in the afternoon and a fairy would add some apples on the tree at night. You were given some questions that in the morning before picking. How many apples were there on a subtree? Having a MLE solution, I wrote the BF solution again. The last problem was about the expected value of the connected component on a graph, which I had no idea. At 12:30, the contest was over.
The canteen was full of competitors, so we decided to go outside for lunch. Wang Huaijie shared a solution with difference methods, which was the standard answer. On the solution seminar, the first problem and the second problem were solved as same as the way I mentioned. The third problem is solved by transforming it to counting points in a three-dimensional space and using matrix multiplication. The fourth problem was so complex that I didn't get it. From 15 to 16, the seminar completed in less than an hour. In total I got 125 points (100 for the first, 15 for the second, 10 for the third). It was so amazing that Wang got AK and he's the only one who got AK today, even Gao Jiaxuan, a genius from Sun Yat-sen Memorial Secondary School who got 380 today. Nothing special after that, we jumped to the next day.
It was an awful day. I got up at 6, arrived at the restaurant at 06:15 while the breakfast started at half past 6. The competition was the worst. Different from yesterday, it started 20 minutes earlier. The first problem was very... emm... political correct (It was about the Winnie the Pooh, the magical frog, a magical box with 12 functions one of which was "harmony" and GCD). You were given a graph and were able to reduce all the edge a number. The question was the minimum reduction that you could move from the starting point to the end point with the cost less than a specific value. The problem could be solved by binary searching the reduction. However, the problem is the cost of the edge is difficult to calculate. The second problem was counting the edges on a derived graph of a tree and print the sum of their powers. The powers made it difficult because you couldn't simply calculate the contribution of each edge. The third problem was about the maximum volume that two boards could make. Lacking knowledge and experience, I wrote the BF solution for the third time today. The last question was about patrolling. You were asked a Hamiltonian cycle on a graph which would dynamically close points or reopen points. But I didn't try to solve it.
At lunchtime, my parents came just like they did last year. We had a lunch in the downtown. During the seminar, the first problem was solved by binary searching and Möbius inversion. The second problem was solved by dp algorithm because you can process the sum of the k+1 times by the sums of 1~k times. The third problem, which used random data, was solved by a kind of improved BF, which only used two types of data structure: the array and the linked list. The last problem was solved by the shortest path tree. Wang got 350 today while Gao got AK. In addition, Yang Zhenwei and Zhang Muzi also got into GDSOI. Sadly Zhan Fangrong got a 0 today while I got 40 (30 for the first and 10 for the second). The seminar ended at 15:45, so I went back to the hotel and had dinner around.
There used to be an option of visiting the places of interest in Zhongshan, but as our school just have two preferred to visit, we were sent to listen Mr. Yan Zixi's speech of network flow. In the afternoon I stayed in the hotel. In the evening there was no party. I tried to do something, like solving some problems or learning a new algorithm. But I just couldn't, just like someone who try to drunk himself with soft drink. As we all know, Wang has become a member of the Guangdong Team A, which means Tsinghua University will matriculate him if he can reach the line of the first kind of college (top universities) in NCEE. However, we had to depend on ourselves.
Because I discussed with Yang about the solution of the problems these days last night, or this morning. I went to sleep at about 02:00. At seven I woke up. It seems that everybody got up very late because there were few people eating lunch when I arrived there 10 minutes later. The ceremony began at a quarter past 9. The two students from the junior, Lei Zhehan and my roommate Luo won the second prize of junior group. Huang also won the second prize. Zhou Yukai, the little genius from our school, won the first prize of junior group. Ma Yaohua from Guangzhou No. 2 High School, a junior high school member of the Guangdong Team, won himself the first prize too. At the same time, he also went up to take the prize for his schoolmates. So in total he received 5 silver medals and 2 gold medals (silver medal means the second prize, gold medal means the first prize). Mao and I won the third prize of the senior group. Zhang and Yang won the second prize. And Wang, of course he won the first prize. At the same time, because Wang was the second place of the whole GDOI, our school won the third place among all the schools and Guangzhou won the first place among all the cities. The ceremony ended at 10:30. After taking photos, we got to the canteen at 11:00. But we were so full that we didn't eat a lot. After taking a rest, we went back home at 14:30. However, because our minibus caught a flat tyre on the way back, we did not reach back to school until 17.
P. S. It was such a hot day that it rained cats and dogs after sunset. Can you imagine how we felt when our minibus broke down under the bright sunshine on the highway?