A Unique Summer Camp (2)

Day 6 (July 17th)

Today we got some new equipment to start the next project, a brick building robot. We are Group 14, including Wang Kaibo, Tang Haoyun, Tang Zhiyao, Han Yuxuan, Liu Yipeng, Lu and me. The class was still boring for who was in charge of algorithm. I got another ThinkPad Laptop and installed the environment. In the evening, Lu and I built the chassis of the robot. Mecanum wheels was so fantastic that the car with them could move in any direction. Besides, I also found some bugs of my program. Maybe code refactoring would be required. But today I was enough.

Day 7 & Day 8 (July 18th & July 19th)

We spent two days arguing which algorithm should be used in the first stage. On July 18th, You Peixin and I made two algorithms together. They were a DFS and a plug dp. As you know, the time complexity of the DFS was so huge that was unacceptable. You could build a set of data which would cost it a large amount of time which might come up to 12 hours. But as Mr. He Dongliu said the data would be completely random, the expectation time of the algorithm was much lower than the extreme data. It would probably solve the problem in less than 30 seconds. Different from DFS, the time of plug dp was much more stable. But the problem was we had too many plugs that the number was 24. According to the time complexity, the time plug dp spent would not be large than 9000 seconds, which was about 2.5 hours. However, the problem was that it was still unacceptable. And the time plug dp spent would always be similar so that it was almost impossible to solve any cases in 2 minutes. The branch cutting of the DFS was also thought a way to solve the problem. However, it didn't make sense though we tried many different kinds of ways like the analysis of connectivity and using the solving ideas of human brains. When we finally got back to the dormitory, I heard that there was a student called Lian Shixi who used to win the bronze model in NOI WC. He made a program that was able to solve the problem in 2 seconds. But You and I supposed that he or his teammates didn't try the extreme data.

On the next day, we still tried to optimize the DFS. But we didn't make any progress. The only thing we can do was to update the UI. So we turned to our coaches and friends. Mr. Liang Zexian was in Changsha, with Wang Huaijie, attending NOI, so he was busy. You asked Yan Shuyi, a NOI gold medal winner. With Yan's help, we found that the plug was unnecessary and we only need to record the plugs on the contour line. It was a great optimization that we could probably solve the problem in 2 seconds. But the coming problem was that dp was used to count the number of answers. How could we output them? So the code refactoring would be probably delayed.

Field Example
The example which let me find the problem

Day 9 & Day 10 & Day 11 (July 20th & July 21st & July 22nd)

In the three days, I finished the plug dp. But as soon as I finished it, I found that the algorithm was wrong. (QwQ)

As we mentioned, we found an algorithm using plug dp that could solve the problem. So on July 20th we finished some details like how we keep the field (We recorded the last state which transformed to each state so that we could go back later). At the same time, You and I met two tutors which were in charge of machinery and algorithm and explained our algorithm to him. I also help another student from Changjun High School of Changsha named Fang Yanzhe, a retired OIer, write the DFS algorithm.

When I came back to the classroom (or we should call it R&D room), it was 09:00 the next day. In the next 2 hours, I completed the first stage of the algorithm, which counted the number of solutions. To be honest, the mistake had already appeared when I tested it. There was a data which was like the picture on the right. The program told me that there were 85591561275 kinds of solutions. That was very odd. You also alerted me that the answer might be too big. But I was certain that the number was large, so I paid no attention. After lunch, I added the last state part and updated the I/O. But just before I left the R&D Room, I found a serious problem that there might be some loops which was not allowed to appear. That can also explain why the answer was so huge like that. That was why my excitement became disappointment when I went back to the dormitory.

When I was taking a shower, an idea came up in my mind. I could use a union-find set to find the loops. According to the plugs, I could divide the map into several connected blocks. The connected blocks with fortress points would be valid routes. And the ones without any fortress points must be loops. And the loops could also be put into routes. So on Day 11, I modified the code and left the loops blank, which meant humans were required to give it a colour. However, the semi-automatic was really not satisfying.

P. S. The time passed so quickly that half the summer camp had passed and the summer holiday had begun.

Day 12 (July 23rd)

Today You and I made some progress. We made the algorithm automatic again. We removed the last state part and used a dfs to find the valid solutions instead. Another algorithm, which contented connectivity in states was provided by You. The key is a data structure called map. It can create points dynamically so that the space was reduced. But You didn't keep the number of valid solutions. So I also tried to rebuild the code in the evening. But I didn't make it. Maybe tomorrow I can complete the work. At the same time, Liu Yipeng had built a mobile application

By the way, Mr. He came to the dormitory to look for someone in the afternoon before the rain at 15 o'clock when I was playing video games in my room. We talked about some ideas and algorithms in OI and the situation of the college entrance examination. But Duan Quangeng didn't know that Mr. He slept on his bed while waiting the rain stop.

Day 13 (July 24th)

Today I spent a whole day debugging the algorithm. But the bug remained. Tutors came to find You and I and asked us to build a program to make a timetable of the warm-up matches tomorrow. On the other side, after building and testing for three days, our deep♂dark robot got online. We have been ready for the matches tomorrow!

Maybe because of the typhoon, it was still rainy until the afternoon.

Day 14 (July 25th)

Today we had the warm-up matches. We did a great job in the first round, scoring over 200 points. We were the only team succeeded in doing that. In the second round after lunch, we teamed up with Group 15, which is formed by Hu Kaijie, Wang Runxuan, Fan Jiaming, Wang Leran, Su Juyuan, Fu Jingya and You, scoring more than 250 points, which was the highest in the warm-up matches. After the second round, we found that Group 18 with a robot with green wheels also did a good work. So we tried to communicate with him about picking up them as our ally by making their score not high enough to be a seed group. But their performance stayed high and became the first place after all the 4 rounds. On the third round we worked with Group 1, another potential seed group with a tiny blue car, testing our block storing structure. Though our performance was not so good as the last two rounds, but we still scored about 160 points.

As we'd scored over 600 points, I planned to stay in the classroom to continue debugging my program and Lu Sheng'an was going to prepare the report about our robot. However, Ms. Lu Yi asked us go to the stadium to watch the matches in the evening. Stopped by Lu, I didn't argue with her. However, I was very angry. Our robot broke down in the last round, but we still won the second place. However, the groups with which we want to ally, including Group 1, Group 15 and Group 18, were all the top 5. So we could not pick them up as our ally.

Mars 2020