bye, acm

There were two ACM selection contests at my school last weekend and this weekend. I missed the one last weekend because I went home. So, today I decided to give it a try to see whether I should pick up algorithmic competitions again—something I haven't touched in a year—while continuing to play CTF.

The contest was held from 1:30 PM to 5:00 PM on December 26, with a total of 10 problems. As is well known, ACM contests don't award partial points, and rankings are determined by the number of problems solved along with penalty time. This afternoon, I solved 4 problems and ranked 16th out of 35 participants. Unfortunately, only the top 14 advanced.

So, this was my first ACM contest in university, and it will probably be my last.

Travel Log Content

That Morning

Just wrote two templates: one for Dijkstra and one for a segment tree.

A few mistakes made in Dijkstra (it's been a year since I last wrote it, so it's normal to forget):

• The vis array should check u, not v.
• Forgot how to use make_pair, so the code wouldn't compile.

Mistakes made in the segment tree:

• Forgot to build the tree.
• Forgot how to write pushdown.

At least I didn't forget to make the array and lazy tag four times the size.

Before lunch, I found out that we're allowed to bring algorithm competition books and printed code. Too bad there's no time to prepare now.

Planning to take it easy this afternoon.

That Afternoon

Problem Link: https://vjudge.net/contest/474375

For Problem A, I initially considered using a precomputed table, but seeing many solve it instantly and looking at the sample cases, the pattern was obvious. I directly used $(n+1)/10$—no pitfalls here. (CF Rating: 800)

Next was Problem B. It looked like a math problem at first glance, but upon closer inspection, it turned out to be a knapsack problem. However, it had been a year since I last wrote a knapsack solution, and I had completely forgotten how to do it. I went to the restroom, thought about pulling out my phone to review, but decided against it—after all, I was just here to coast.

While I was still thinking about Problem B, the leaderboard showed many had already solved Problem C. I ignored it until, after 40 minutes of failing to come up with a time-efficient solution, I finally set Problem B aside temporarily.

Problem C was indeed a check-in problem—a simple greedy approach, nothing noteworthy. (CF Rating: 800)

Then, many were solving Problem G. I realized it was straightforward; it required Dijkstra, which I had just written that morning. I solved it in 20 minutes. (CF Rating: 1600)

The idea was to compute the single-source shortest paths from both s and t, then check whether $min(dis1[i]+1+dis2[j],dis1[j]+1+dis2[i])$ equals 1. If so, adding the edge would satisfy the condition.

At this point, I was ranked 12th.

I returned to Problem B. After an hour of struggle, I proved that my $O(m^2)$ approach was incorrect and came up with an $O(m^3)$ solution.

My previous $O(m^2)$ approach treated different multiples of the same number as a 0/1 knapsack. For example, with three 2s, the knapsack would be 2, 4, 6. However, this approach could lead to selecting more items than available—e.g., for m=12, it might select 2, 4, and 6, effectively choosing six 2s, which is wrong.

My improved method used a grouped 0/1 knapsack. The outermost loop iterated over groups, the middle loop enumerated different multiples of the same number, and the innermost loop iterated over the knapsack volume.

The only optimization I made was to break early if a zero-sum solution was found at the end of a group.

For m=1000, this was a theoretically inefficient approach, but it barely passed—1700ms/2000ms.

It turns out that constructing test data to break this inefficient solution isn't straightforward, so this approach is actually acceptable! The intended solution involved DP, data structures, combinatorics, and two pointers—completely beyond me. (CF Rating: 1900, which is relatively high.)

At this point, I was ranked 10th.

I checked the leaderboard again and noticed many had solved Problems F and J. Problem F reminded me of CSP's first problem this year, and Problem J was a constructive problem, so I decisively chose Problem J.

I spent half an hour writing the solution for Problem J, submitted it, and got WA on case 5. Frustrated, I couldn't find the error, so I decided to write a special judge (spj) program.

Since it had been a year since I last wrote a checker or spj, it took me an hour to finish. Unfortunately, my self-written spj had issues—the length of the second-longest edge always returned 0.

At this point, I was ranked 14th.

I realized I couldn't afford to waste more time on the spj, so I started generating test cases and checking manually. With 15 minutes left in the contest, I finally found a mistake, fixed it in 5 minutes, and resubmitted.

It still resulted in WA.

With 10 minutes left, I gave up. I watched my rank drop from 14th to 16th and resigned myself to the reality of retiring from competitive programming.

A miracle comeback like last time at Strong Net Cup probably wouldn't happen again—after all, ten people had already solved four problems.

Aftermath

It's a bit regrettable because Problem F was also a greedy problem with a CF rating of 1500, which is easier than Problem J's 1600. I feel like I lost out here.

The key issue was that in the special case I identified for Problem J (d=h), there was a sub-special case (d=h=1) where my fix from 10 minutes earlier didn't apply. What made it worse was that my original code correctly handled d=h=1, so I completely overlooked the possibility of failing there.

However—

According to acheing (ranked 2nd), those selected would have to make up previous algorithm assignments. I believe that even if I had luckily made it into the top 14, given that the school team only has a few spots and I was just there to make up the numbers, there was no real need for me to get involved with the ACM team.

So, was this luck or misfortune? Perhaps missing the team by a narrow margin was fate. What I should really focus on is mastering my major instead of trying to "ride two horses" and exhausting myself.

So—

Farewell, ACM.