A Trip of Konjac

This post is about my first GDOI which was held from April 28th to May 2nd. But you may consider the title confusing. Konjac is a kind of plant. The pronunciation of its Chinese name is similar to another Chinese phrase which means "extremely poor in academics". So most of us called ourselves konjac to show that we perform poorly in contests.

Day 0 (April 28th)

On the sunny Friday afternoon we got on the coach and left for Dongguan at 15:00. To my surprise, the representative team of Guangzhou Tieyi Middle School was also there. I had heard that they were facing a big problem, as the number of students interested in informatics declines rapidly. As a result, they sent only one contestant, Tan Jiawei, and the coach Mr. Lu Jianfeng to attend the contest this year. I had met Tan during the curriculum last winter holiday. He was silent, but very good at informatics. I knew little about his coach, so I chose to sit behind the two coaches. The other one is the coach of our junior high school students, Mr. Yao Xiaohao, the brother of the coach of Shantou Jinshan Middle School, Ms. Yao Xiaohua. The 1.5-hour journey was boring, so I spent the time listening to the talk between the two coaches. They had talked about the intense relationship between the computer lab managers and the informatics teachers, the embarrassing status of the informatics teachers, ways to teach the students informatics, etc. It was funny when they talked about some teachers treating the informatics teachers as a computer repairman. I joined their talk and shared my experience when I was in Guangzhou Wuyang Middle School. I needed to repair the computers and make slides for our class teacher while studying there. My words made a deep impression on them.

At about 16:30, we arrived at the hotel in which we were going to stay. My room was big, clean and comfortable, which I was very satisfied with. 30 minutes later, we took another coach for dinner to the TungWah Senior High School Songshan Lake (Ecological Park) Campus, the place where GDOI 2017 was held. The campus is so big. The teaching buildings, the office building, the dormitory buildings, even the canteen are all much larger than ours. The dinner was like buffet, but less dishes to choose. Since we spent some moments taking photos at the front gate, the queue was very long. Maybe I should get here earlier next time to avoid waiting long. After returning to the hotel, we just did some personal things and then went to bed.

Day 1 (April 29th)

It was about 05:50 when I almost rolled down to the floor. And then I found it 10 minutes before my alarm. So I decided to get up. And I also woke up another student in my room called He Junjie, a junior high school student of us At 06:30, we came to the 2nd floor for breakfast. The western buffet was good. The ham, bread and juice tasted yummy that I ate a lot. 30 minutes before the contest, I arrived at my computer room. It was very kind of the host that they had almost provided us with everything, even including some Snickers and a bottle of water. At 08:30, the Day 1 Contest began. The first problem was about substring replacing, and the key part is how to find the substring. I knew nothing about the string function of C++, so I used Pascal instead. There is a function called "pos" in Pascal. It can find the first appeared place of a specific substring in another string. So I used it to find the substring. The second one was a long problem. The description was over 2,000 characters long. In fact, there was even another document with the complete description with over 5,300 characters. I spent a long time going through the problem. Actually it asked me to find, for every node, the minimum natural number not in the set which includes the weights of all nodes, including itself, in the subtree. So I used BFS. The third problem required me to generate a set of strings, then inquired the longest common substring of them. However, I ignored the problem. The last one was a mathematical problem. It was about the number of the triangulation of a polygon. I spent the rest of time trying to derive the formula, but I failed.

After the lunch and the noon break, we went back to school for the solution seminar of the problems on Day 1. The first Problem required KMP. The second was more than a BFS, but I forgot whether the solution was a segment tree or decomposition on tree. By the way, Wang Huaijie, one of the best contestants in our school, came to the front to share his solution. However, he used my name! That led to another thing similar that Huang Kang'en used Wu Yuheng's name to share his solution too. The funniest is they said they come from the New World School of the Affiliated High School of Southern China Normal University, a campus of our school which has the same uniform. The third one was similar to the longest common substring. The last problem was much harder than I expected. It was related to Catalan Number, but I had no idea what it is. And it also required NTT and FFT, which I hadn't learned. Because of the wrong data of the second problem, the grades were delayed. I got only 20 points on the first problem. After dinner, we went to a store in the vicinity of the hotel on the way back and bought a lot of delicious snacks. We had a party that night.

Day 2 (April 30th)

Day 2 was similar to Day 1. The first problem was to search the shortest path from point to point. Since I didn't know how to use struct node, I used DFS instead of BFS The second problem was to compare several 64-bit binary numbers. There was no doubt that the only way was to simulate and the time complexity must be in the square level. Thus I compared every pair of them bit by bit. The third problem was to sort a given sequence with fewest steps. I had no idea with the problem, so I searched the given string with the order of the target string. I knew there are some problems with it, but I wish it can earn me some points. In the seminar, the solution to first problem was the time-based BFS(I didn't think of the time order, but I thought the BFS) or SPFA. The solution to the second one was similar to my thought. But it can be optimized by cutting the 64 bits into several groups. The third one required an algorithm similar to finding LCS. The last problem was a fantastic persistent data structure. I got 30 on the first problem and 5 on the third problem. What's more, the contest committee changed the time limit of the first problem and the data of the second problem on Day 1, so I earned 20 more on the second problem. My parents came to visit me in the late afternoon and we had dinner in Shilong, Dongguan. In fact, I preferred to spend time with my friends, among whom may not have another chance to attend GDOI any more.

Day 3 (May 1st)

After two-day's contest, the top 70 students would be able to attend Day 3 which is called GDSOI. Wang Huaijie, and Ma Zailin in Senior Grade 2, as well as Tan had the chance to attend. The rest of the contestants would go to visit some places of interests. We visited an eco-friendly power station which burns rubbish to generate electricity with little smoke. Then we had a walk in the Ecological Park. What a boring trip it is! Mr. Yao said he was going to take the contestants to visit the Martyrs' Park during GDOI 2019 because of this. After the lunch, we spent a boring afternoon in the hotel. Huang Kang'en, whose home is in Zengcheng, a district beside Dongguan, went back home by bike. His parents sent him back by car in the late evening. Long Hanzhe had returned to Guangzhou in the evening of Day 2. Zhan Fangrong, Fang Decheng, Wu Yuheng and Bao Zhengheng all left in the afternoon. Mao Hongxi and Liu Che spent a whole day in their room playing computer games. Ma didn't attend the seminar of Day 3 and he also missed the coach to the school during supper time. So only Liang Jingcong and I and the junior high students went to the school for dinner. After that, I came to Ma's room and played computer games with him for a while. I helped him clear the Tomb Raider.

At about 23:00, Mr. Yao asked us to go downstairs to play the killer games, so we came to Room 515. When we got in, I was surprise to find that some students of our school, including three junior high school students and three senior high school students; Tan; some students from Shantou Jinshan Middle School, and the teacher of these three schools were all here. We had a good night there, playing until 02:30 the next day. It was funny that Mr. Yao took a photo of us and sent to the Moments of WeChat. Then he found one of his friends commenting that the photo was like the scene of polices catching prostitution because there was a girl sitting on the bed with quilt on her knees, and a boy lying on the bed! The teachers and junior high students went back at 01:00. Some others, including Huang and Liang, also left at about 01:30. After I went back to my room, I found He Ruijie fallen asleep deeply. So I also went to bed at 02:45.

Day 4 (May 2nd)

Here came the last day! At 06:00, I got up. After packing my bags, I came downstairs for breakfast at 06:30. It seemed that Mr. Yao had a bad sleep. So after finishing breakfast at about 08:00 he went back to sleep again. At 08:50, we came to the first floor and waited for him to go to the school for the awards ceremony. Had he not appeared until we met Ms. Yao. She went to his room and found him still sleeping! At 10:00, everything was ready and the ceremony began. This was the first time I had seen Professor Guo Songshan, the leader of GDOI for 32 years. He is not tall, just like an ordinary old man. Wang won the second prize, some others won the third prize, but I got nothing. We took photos together at the front door of the school. Then a bus came to take us back to the hotel for the closing lunch. On the way back, I thought of our last meeting. Some who played the killer game last night was already on Senior Grade 2, and this was their last GDOI. I might not meet them anymore. What a pity! But before the lunch was over, we can still enjoy the rest of the time. The lunch was delicious, but there were too many dishes that we did not finish them all, leaving over half.

After lunch, I took my bags and went back home at 13:00. I had asked Mr. Yao to leave on Day 3 because they planned to leave at 14:30, and that would be too late for me to go home. Therefore, I decided to go to the train station by bus and then take a train back. But as soon as I got out of the lift I found Tan standing in the lobby with his luggage. I asked him why he was there, and he explained that he was going back to Guangzhou with Mr. Lu. Just then Mr. Lu came. He recognized me and asked me why I was there and I explained to him. He was surprised to learn I was going back alone, so he asked me to go with them. So we got back together. 2 hours later, we arrived at Yuexiu Park and we took the metro home. That's end of my first GDOI.