A reflection on ICPC 2024
Preface
ICPC 2024 regional has ended, and our team ranked #20 and #38 in Jakarta and Hanoi sites, respectively. As a final year for participating in ICPC as a contestant, I felt quite disappointed and pitiful for the results. Nevertheless, I enjoy the process for training and learning with all NTU contestants. I also want to express my sincere gratitude to my teammates, Zong Yu and Min-Jen.
Pre-contest preparations
In general, I am satisfied with our pre-contest preparations. We had 3 months of training, and each Saturday we virtually participated in a 5-hour contest. I have to admit that the individual capability of our team was not good compared with other NTU teams: our Codeforces rating could not reach 2000 (which is a “candidate master”), while for other teams, they had at least a person reaching “master” rating. This means other teams could clearly have at least one person to “carry” the team to secure the “solvable” problems, and their focus was just to improve cooperation and the speed and accuracy for submissions. However, we were struggling to upsolve the problems that other teams could do, and for the training contests, other teams often surpassed us for 1 or 2 problems. The reason is that we were often stuck at some problem. Under such cases, none of us could take ourselves out to find the killing point and most likely we wasted all our time on this problem.
As for me, although my coding was okay for the individual contests, I quickly found that I was not suitable for coding in the team working. My coding style was quite different from my teammates, which means whenever I got lost in my codes, others could not debug for me and they had to rewrite the codes. Also, Codeforces problems usually required only a main idea while ICPC problems usually had much more corner cases. When I used Codeforces experience to code in ICPC, even if I was confident before coding, I still often found that I left some cases during coding, and then I got stressed and messed. This also results in my later inconfidence about my ideas in the contest. Luckily, Zong Yu had a much more precise coding style, and he could usually get a clear mind during coding. For example, sometimes I came up with an idea and I thought the coding would be complicated, but he could implement it in a precise way. As a result, we decided to let him implemement even when the idea was proposed by me, except when the problem is very easy. Although this required some extra time for conveying my ideas to him, we could further ensure the correctness of the ideas during the process.
Freed from the coding work, I can calm down to analyze the in-contest status and manage the time and targeted problems for my teammates. I also practiced many number theory problems and combinatorial problems, since this required less coding skills and I was the most familiar person with the related knowledge. These types of problems occurred a lot in our UCUP training, however, were not occurring in the regional contests. Min-Jen was good at coding data structures and had strong observations, but sometimes may be stuck on some wrong idea alone. As Zong Yu needed to code and may not have the time to pull him out, I became the person to discuss with him when I noticed that he was in trouble. In summary, Zong Yu and Min-Jen were coders, while I needed to supervise them especially when they were stuck on some ideas and problems. When such cases occurred, I needed to discuss with them, remind them or debug with them.
Generally, this cooperation manner is good. I still remembered that for our first training contest, we used three computers and all of us were focusing on our own problem but failed to solve it. And we only solved three problems in that contest. However, as we cooperated better, we could solve 6 to 7 problems in a contest with a single computer. From this time to look back, I think we should reduce the frequency for UCUP training since the end of October. At that time our cooperation has been quite good, but our individual capabilities were still limited, and we should spend more efforts on practicing special topics and individual training. This is even more important to me, as I spent less time in problem solving during the contest compared with my teammates and improved less in team training. Unfortunately, we did not realize this and even put efforts on more training contests.
In-contest performance
The problem style in Jakarta was quite different from what we were training on. It only had problem C as a very easy problem, and all other problems were kind of tricky. At the very beginning of the contest (first 1 or 2 mins), I opened problem A and found it was easy, so I described the problem and rough idea to Zong Yu and let him code, but then he found that I left an important statement of the problem. Though, he thought he could handle it. Not much later I opened problem C and came up with the solution, but I decided to let Zong Yu code first, until I found that Zong Yu became very stressed and got stuck. So I told Zong Yu to hand over to me to solve C first. I was not confident about my idea so I asked Min-Jen for verification of my codes, and then we submitted it and got accepted. Zong Yu also found out the bug of his idea of problem A and got accepted right after my submission. This was the time that the contest had run for 50 mins, and it was unusual to solve the first problem for that late. Later I spent most of my time on problem B, while Min-Jen and Zong Yu spent their time on problems I and M, and we had discussions on each other’s problem during the process. Although we slowly caught up with others by solving these 3 problems, I thought I should finish problem B more quickly, as it was not that difficult. Again, it was caused by my limited capabilities. The rest of the contest was about Min-Jen stuck at problem G and Zong Yu stuck at H. The decision that Zong Yu coded H first was because Zong Yu and I already had an idea on H, and when we opened H there were more teams passing H instead of G. When I told Zong Yu my idea on H, I also reminded him to be careful about the time complexity, and the implementation would be very difficult. But Zong Yu was confident: he had practiced string problems before the contest and he thought he already knew how to handle it. Although I was still kind of suspecious, I trusted him and let him code (in training, sometimes I spent a lot of time verifying his codes and ideas and found he was correct; so when he was confident I just trusted him). I also put some time on G to think with Min-Jen, but for most time I was helping with Zong Yu because he was debugging painfully (in fact, I did not offer effective help). I should have realized that Zong Yu was upset debugging his codes, and he should calm down and rethink about his ideas (and our ideas were proved wrong after the contest). However, I did not pull him out and instead I came to him, so we two both got stuck on H. I also noticed that Min-Jen got stuck on G, so I reminded him to have a look at F instead, which is a combinatorial game and he might have some good motivations. Min-Jen read F but had no ideas, so went back to G. For the last 30 minutes, we finally came together for H, but it was too late. As a coordinator, I thought I should not get too involved in debugging with Zong Yu. Instead, I should watch their time and pull them out when necessary. In fact, none of us noticed that we had already spent too much time on our problems. And after Zong Yu calmed down after the contest, he figured out the solution of problem G quickly. As a matter of fact, no one should spend too much time on a single problem. So at that time, it would be better to stop for a while for discussion, and exchange our problems to each other.
After Jakarta, Zong Yu realized that he may get stuck on some problems and be upset, so we did extra training on past year’s Vietnam regionals. I found that Vietnam site had several easy problems and the rest were very hard (means few medium-level problems). Therefore, it would be crucial to solve the easy ones quickly. Moreover, we should be careful about the constant factor in the time complexity, as Vietnam problems were tricky about this. In the contest of Hanoi, we performed really well in the first hour: we solved 5 problems and ranked #5. My teammates performed really well, but I thought I still made some mistakes. For problem C, I made a stupid mistake for the combinatorial formulae, resulting in one unaccepted submission. For problem F which was a case study problem, I realized I did not exhaust all possible cases during coding so I wasted some time. Luckily I calmed down and discussed with Min-Jen, and cleared my mind before the final submission and got accepted. Anyway, if my capability was stronger, I should pass these two problems more accurately and quickly without occupying my teammate’s time. I also verified the ideas of problem L proposed by Min-Jen, but overall my teammates did the most parts for the rest 3 problems and they did very well. However, the situation turned bad when Min-Jen and Zong Yu were stuck on problem M. At that time I was thinking about problem E, which was a case-study game. I thought for a while and realized that it was difficult, and no teams had passed the problem so I gave up. And then I found that my teammates had been debugging on problem M for a while, so I asked Zong Yu to think about problem K instead. I was skeptical about whether we went into a wrong direction on M, since many teams passed the problem easily, but we debugged for a long time. So I discussed with my teammates to know about their ideas, which was a randomized algorithm, but their ideas sounded so correct and I proved it could pass a test case with high probability (until the last hour, we realized that the probability shrunk when the number of test cases increased). Then I still let Zong Yu help Min-Jen to debug, and I thought about problem K instead. Almost an hour later we finally solved problem K, and then I told Zong Yu to write a stress test for problem M (actually, this should be done earlier). I already knew that we were spending too much time on M, but I had no ideas on other problems. After the stress test was finished, I thought I should not put two people on M, which had become a time-eating problem. So Zong Yu and I started to think about problem B but we both had no idea. Later, I exchange Min-Jen and Zong Yu, to let Zong Yu debug on M and Min-Jen think about B. Min-Jen figured out the idea of B quickly, which was a sum-of-subset dynamic programming, but it was just an hour left. We decided to take the computer in turns for problems B and M, and only used the computer when our minds were clear. With such strategy we finished the program of problem B and finalized M, but then we found our ideas for M were wrong, and there were still some cases to handle for problem B but we were not familiar with such kinds of DP so we put extra time. In the last 5 minutes, we finally figured out the cases and solutions for B, but we had no time to finish them. In summary, I think our strategy is okay, and it is a bad luck that we did not observe a simple fact on M and ask Min-Jen to do B earlier. If I asked Min-Jen to read B first instead of asking Zong Yu, things may get changed, but this was not foreseeable. The fundamental thing is that we did not have enough individual capabilities, especially for me, and I did not contribute to many ideas in the Hanoi site.
Post-contest thoughts
Up to now, I still sometimes dreamed back to the contest when I fell asleep. Indeed, I need to spend most of my efforts on research and could not exert myself in ICPC contests. But I think even with limited time for preparation, I could do better than what I did. For example, I should do more individual trainings to improve my capabilities. Then I may contribute more ideas during the contests apart from the management. Although I upsolved many problems after each team training, that was quite different from what you felt during contests. Upsolving problems are like research, and you can think about it in a slower pace, so that your mind gets much more clear. However, during the contests, I need to spare some efforts to my teammates, and would get stressed under the time limit. So thinking back to preparation, I should do specific topics one by one instead of randomly upsolving problems, and take more individual contests. But overall, although the results are disappointing, I do not regret participating this year’s ICPC.