Day 0
I participated in CodeCraft 2021 last year, but it conflicted with other contests and personal matters, so I didn’t even submit anything in the preliminary round and it ended there. This year, I thought I’d at least get a wristband, but who would’ve thought~~~ I got absolutely nothing.
About the team name, I found it quite interesting. The name baseline was banned by the organizers. Last year, I used --baseline--. This year, having learned about many Unicode characters compared to last year, I thought I’d find a character to replace one, but who would’ve thought it only supports ASCII? I tried baseIine, but in the sans-serif font on that list, the letter ‘I’ has no horizontal bar on top or bottom, making it look exactly like baseline. I guess the organizers never expected someone to name their team like this, hhhhh.
Practice Contest
The entire problem was relatively simple. There were some servers (edge nodes) and clients (client nodes). At each moment (abstracting a time period into a time node), clients had demands, and servers needed to allocate bandwidth to clients to meet those demands. However, the links between servers and clients had to satisfy latency requirements. Finally, the cost was calculated using the 95th percentile billing of the bandwidth sequence.
At first, I didn’t understand the 95th percentile billing correctly and thought it was the 95th percentile billing for each moment. I casually wrote a greedy algorithm and submitted it, surprisingly getting some points. The opening score was 1.34 million. I only realized my mistake when I wrote my own judger.
Additionally, when writing the greedy algorithm, I used pandas and finished it in under 20 minutes. After submitting, it kept running with errors. Later, I realized pandas wasn’t even available. I switched to numpy to read the txt file directly, splitting by commas. However, all the pandas indices I used in the code were completely broken, so I had no choice but to rewrite part of the code.
Another pitfall was that data reading had to start from the root directory. Ugh.
Then, I thought it was just a load balancing problem, so I wrote an averaging method, which actually performed worse than the greedy approach? Then I thought it was an issue of selection order, so I tweaked several sorting methods, but they even performed worse than my first greedy submission (the first greedy submission was also sorted, by bandwidth and the number of client nodes it could handle, prioritizing servers with higher bandwidth and fewer client nodes).
In between, I considered binary search on the answer, setting a maximum threshold to see if it was feasible, and then trying to wrap it with a network flow algorithm.
This might not have been a load balancing problem at all. Then, I started from the 95th percentile billing and tried to ‘freeload’ that 5%, and sure enough, the performance improved dramatically. I only needed to consider the order of demands, handling the 5% demand for each edge node separately. After some random tweaks, I got around 60w, and after adjusting some parameters, I reached 40w. Then, I just lay flat and submitted, ranking 2nd. I thought that would be enough to advance to the semi-finals, but in the last few days, my rank dropped from 2nd all the way to 20th. At that time, I hadn’t yet realized the severity of the problem - -.
Preliminary Round
I missed the first day of the preliminary round due to some matters. When I came back and submitted my previous best result, I found that the order of client nodes was no longer guaranteed. Ugh. After some adjustments and resubmitting, I only got around 40th place. I then tried a few of my own ideas, but the improvement was minimal. Ultimately, it was an algorithmic issue. I had already written network flow and minimum cost flow algorithms during the practice contest, but Python was too slow, and I really couldn’t compete. I felt that the approach of binary search combined with network flow was quite scientific.
I gave up and focused on my graduation project instead, wasting time.
Final Thoughts
To be honest, although I was lazy, the overall experience of participating was quite poor. During the practice contest, it was fine; everyone was asking normal questions about submissions. But later, people started exchanging ideas, acting like they were dividing apples among themselves? In the last few days of the practice contest, everyone suddenly became smart, hehe. In the preliminary round, even more smart people appeared, hehe. Many people I had never seen before in the practice contest showed up, hehe. Truly impressive.
Postscript
I made it to the top 64 in the Guangdong-Hong Kong-Macao Greater Bay Area and got a certificate, hhhh.
I won’t participate next year.
