Happy Semi-retirement (2)

May is a month full of contests. In the International Labour Day holiday we had GDOI. A week later, CTSC and APIO took place one by one. From May 9th to May 15th, Wang Huaijie, Zhan Fangrong, Yang Zhenwei and I, as well as Mr. Liang Zexian and another student named Qu Hengyi who comes from the TungWah Senior High School in Dongguan, came to the capital of the PRC, Beijing for APIO 2018.

Day -1 (May 9th)

In fact, there was no Day -1. It just meant that we set off at the day before Day 0. This was due to the transportation. First of all, we planned to take D-series EMU trains which depart at about 20:00 from Canton and arrive in Beijing at 6 next morning. However, this kind of trains only serve from Friday to Monday every week. But May 9th, 2018 was Wednesday, so it was not an available option. The second way was to fly to Beijing at May 10th. But the fare was not cheap, and we must hurry up all the way. A cheaper option was the Z-series Conventional Speed Rail trains which depart at 8 in the morning and arrive at about 06:00 the next day. But it takes too long that none of us accepted it. So the final plan was to take the G-series High-Speed Rail trains on May 9th and stay in a hotel until May 10th to check in.

So I went back home to prepare my luggage on May 8th. May 9th was such a rainy day. At 07:45 I left my home for the Guangzhou South Railway Station. At about a quarter past 9, everybody had arrived. At exactly 10:00, the train G66, which ran from Guangzhou South Railway Station to Beijing West Railway station departed. Then a little episode happened. There was a mother whose seat was at two rows behind her baby's. So when the baby cries she usually need to asked the woman beside her to let her get out to soothe the baby. But the woman was very impatient with it. She complained that she abandoned her sleep and asked the mother to exchange her seat with the old lady next to the baby loudly, which annoyed me. What an awful woman! Why can't she exchange her seat with the baby? Both of them sitted next to the aisle. But finally I calm myself down.

Soon it was time for lunch. The bento on the High-Speed Rail trains were really expensive. Luckily I took some bread so I needn't to buy them. But both Zhan and I caught a cold. Each of them cost 45 yuan. 8 hours later, we arrived at the station and got to the 7-day hotel in an hour. At 19:30, we found a Beijing cuisine restaurant for dinner. When we got back, it was over 21:00. We played poker cards in Zhan and Wang's room for a while and went back to sleep at about 00:15 the next day.

P. S. Today the codes of 85 competitors were lost on CTSC so that their ceremony was delayed because they have to have the contest of the second day again.

Day 0 (May 10th)

At half past 6 I got up for breakfast. After walking around, I bought some meat buns and a package of soy milk. However, the others didn't woke up until 08:30. At about 10, Mr. Liang took us to the Beijing Yulong International Hotel, which lies next to the Xidiaoyutai Station of Beijing Subway. Yesterday we slept beside the Huayuanqiao Station, so it took us about 40 minutes to get there (Maybe It would take less time if we took the subway but regrettably we didn't). Then we were told that the rooms hadn't been ready that we could go to the High School Attached to CNU for lunch first.

After lunch, we were told that the computer test had been available. So we went to the computer room for the test at about 13:30. Because it seemed my cold had turned worse, I went back to the hotel to check in about an hour later, while Wang and the others were still testing NOI Linux. As a result, it didn't take me much time to check in that I was assigned to the Room 51610. Later that afternoon, I met my roommate, Tan Tian from Shimen Middle School in Nanhai, Foshan, for the first time. We were going to live together in the next 3 days. As we did not realize the time for dinner, we ordered a takeaway. Later, I went to Zhan's room to play poker cards again. All of us five stayed in different rooms. After getting back at 21:00, I took a shower and got my devices charged. At about 23:45 we went to bed.

Day 1 (May 11th)

This was a day for some lessons. At 6 I got up and 15 minutes later Tan got up too. We leave for the school at ten to 7 and arrived at about ten past 7, which was the time the breakfast started. Unfortunately we were told that the breakfast had been delayed for 20 minutes. At exactly 08:20, the first lesson began. The first one was about algorithm and origami. The second one was about image processing with Poisson distribution and Gaming AI designs. The teacher taught us about the Monte Carlo method. Such an interesting lesson!

The lunch was provided in the underground canteen. To be honest, the lunch was so-so. So I'm going to jump to the afternoon. The afternoon lessons were about binary searching and graph matching. It was very funny that the teacher used barrages for questioning and venting. In the end, the rules of APIO were also mentioned. After dinner, the letters with the usernames and passwords we would use in the next day were also given to us. Tomorrow would be the day for the contest, so I went to bed a little earlier.

Day 2 (May 12th)

Today is the day for APIO contest. Getting up at 6, Tan and I arrived at the canteen before 07:15. Having known that Wang and I would be in the same computer room, we arrived there at 08:15. APIO is a contest using the online judge and subtasks, which was the same as IOI. Competitors need to finish 3 problems in 5 hours, which just like the days in IOI too. Last year it was Australia that held the contest and this year it was Russia. Russians are famous for the fantastic ways to solve the problems. Different from Chinese data structure problems, which require segment tree, k-d tree and other this kind of advanced data structures, their problems usually just use some basic data structures like pointers and queues. However, everyone doubted that they were Chinese problems but not Russian ones because it was so obvious that they are all data structure problems.

The contest started at 9. The first problem was about a series of shops on the road which would open in specific periods of time. And there were some questions about the maximum value of the minimum value of the distance between a given position and a kind of shops at a specific time. Not having any good ideas except BF, I jumped to the second problem. The second problem was that there were 300,000 circles and we would pick the biggest one, delete it and the circles which had intersections with it. You were asked by which circle each circle was deleted (the biggest circle deleted itself). Obviously the time complexity should be in the square that for each circle, you need to scan the whole array to check which circles it could delete or by which it was deleted. So I got 7 points in my first submit. Then I found that there was a subtask that the centres of all circles were on the x-axis and a subtask that each circle would not have more than one circles that have an intersection with it. So I thought that a circle could only delete the circles that the distance between the centres were less than twice of the radius. So what about I sort them in the order of the x-coordinates and each time I find the biggest circle that hasn't been deleted and search the circles around it. That would be much more efficient. To my surprise, this solution not only passed the subtask I wanted, it passed all the subtasks except the last one so that I had got 87 points now. Then I handed in the BF solution of the first problem, which got me 5 points. The third problem was to ask the numbers of the tree tuples of a starting point, a passing point and an ending point on a graph which there was a path from the starting point, get through the passing point to the ending point. All the points could not be passed twice or more. So I tried DFS, which solve the subtask that there were 1000 nodes in the graph and there are no rounds, which means the graph was some trees. It earned 10 points. Then I found that it was over 13:00 now and I still had some time to solve the small data which there were only 50 nodes. But as the network was also in heavy traffic. I didn't get the feedback of my solutions until the contest was over.

After the lunch, I checked my last submits. Unfortunately, they got CE. Wang got 50 points as he only got 7 points the second problem (but he got 12 for the first one and 31 for the last one). Because of the same problem, Zhan only got 38 points (0 for the first, 7 for the second and 31 for the last). However, Yang got 128 points since he made some progress on the last problem, winning 36 points for him. The lesson in the afternoon was about the correct solutions of the problems. The first problem was solved by segment tree and scanning line. The third problem was solved by round square tree and point biconnected component (both of them are invented by Robert Tarjan). The second problem was solved by k-d tree and another data structure. All of them did require data structures to maintain. The seminar started at 15:30 and ended at 16:00. As we'd just haven the lunch. So most of us chose to go back to the hotel and order a takeaway later. So was I. Just Yang went out to visit Beijing instead. Nothing else to mention, the day was over.

Day 3 (May 13th)

The morning was the same as Day 1. But different from Day 1 and Day 2, the teachers today were from Peking University instead of Tsinghua University. The teacher talked about sieves for prime numbers and its use on number-theoretic functions. However, most of us found it so boring that a lot of us fell asleep in the last two hours. After lunch, we went to the Beijing No. 80 High School for the lesson in the afternoon and the ceremony in the evening by bus. The lesson in the afternoon was also provided by students from Peking University. But there were not many students here because some of them went to THUPC today. It was about FSA. We talked about the definition, some examples like Trie, ACAM and SAM and the use of it. After the lesson, we went for dinner. The canteen was the best one I've ever seen. There were so many kinds of food available here (though some of them are really expensive). There were Chinese food like rice, noodles, buns and cakes and Western food like pizza, pasta and steaks and some drinks like juice and milk. With the help of Ms. Yao Xiaohua, the coach of Shantou Jinshan Middle School, Mr. Liang succeeded in getting into the school and attending the ceremony with us.

The ceremony started at 19:00. The host were two girls and the famous Wang Yisong the King of Electronic Music. Firstly, some data was given. The average of all the competitors was 55 and the median was 43. There were 9 who got over 200 points and 89 who got over 100 points. Then it was the time for rewarding. As the result of the accident during CTSC, The release of the list of winners was delayed to the ceremony of APIO, but it was really boring for the ones who did not attend CTSC. What excited us came at the next moment. Zhan and Wang got the bronze medal. But we also found a lot of names like He Shengzhe, who all going to attend NOI. I got the rank 1 of the silver medal. At the same time, Zhang Sinuo, Wang Zhidong and Duan Yu were found in the list too. Yang, as well as Yuan Wuwei, Zheng Juntian, Gao Jiaxuan and Wang Xiuhan, got the gold medal. Then Some students from the High School Attached to CNU played some dancing programmes. In their last programme, red papers covered the stage. It must take the students of Beijing No. 80 High School a lot of time to clean up. At about 21 o'clock, the ceremony as well as APIO 2018 ended. Then we went back to the hotel and had a party in Qu's room. We ordered some fry chicken and play CS. Finally we left at 2 the next day.

Day 4 (May 14th)

I got up at 6 again that it seems like I set up alarms. At half past 8, Tan leave the room, going back to Guangdong. Boring in the morning, we checked out and put our barrages to the 7-day hotel. Then we went to the 2nd Ring Road North for lunch and visit the Drum Tower and Nanluoguxiang in the afternoon. After we walked through the Nanluoguxiang at 17, Qu and Wang suggested us to go back. But Yang consists of walking to Tiananmen. Finally, we solved the problem that Yang would walked to Tiananmen on his own and the others would go back to the hotel. As I knew Beijing best among all of us. Mr. Liang asked me to go with him, but I rejected. So we went back the hotel and played UNO and poker cards. We ordered some beef noodles as the dinner and played the cards until 24:00.

Day 5 (May 15th)

Today we went back to Guangzhou. At 08:30 we went to Beijing West Railway Station. I sat in the 10th carriage while the others sitting in the 15th because the system can only change 5 tickets for once. Just when I found my sit, I saw a little boy sat there. He and the children in the same clothes beside him told me that his seat was in the 11th carriage while his teacher's and classmates' seats were in the 10th next to mine. So he asked me whether he could exchange his seat with me. And I agreed. It was 10 when the train G79 from Beijing West to Futian left the station. It was the first time I took Fuxing Hao train. It was China Standardized EMU, providing Wi-Fi on the train. So I typed part of travel notes on the train. When the people next to me who saw I had connected my laptop to the Internet also asked me how to do that, I taught them patiently. That was much more peaceful than what when we were leaving for Beijing, isn't it? After all, at 18:00 we arrived at Guangzhou South Railway Station. Now the trip had ended and tomorrow would be the time we got back to school.

With the end of APIO, an old generation has gone to the end of their time, and a new generation has come up to the stage. Maybe the result is not good enough, but we've tried our best to fight. We have enjoyed the time learing the knowledges and solving the problems. We have got through the hard time when the pressure of the schoolwork and the competitions came at the same time. We have experienced the time we won awards and lost points. In a word, the meaning of the Olympiad is to enjoy the process as well as the result, isn't it?

Beijing At Night, China