The Backstory Behind UC Berkeley’s Performance at ICPC Regionals

Правка en11, от plourde27, 2023-02-27 07:28:25

As some of you may know, ICPC North America held its 13 regional contests this weekend, with top teams from each region advancing to the North American Championship in May. Our region, Pacific Northwest, ended up being one of the craziest and most fun competitions I’ve ever participated in, so I decided to write this blog to share our contest experience this weekend and some of the backstory behind our team selection process.

Our story begins in August 2021, when I was an incoming freshman at UC Berkeley eager to participate in ICPC after two years of grinding CP during COVID. As soon as I arrived at Berkeley, however, I was shocked to learn that despite being one of the highest-ranked schools in the country for CS, we had no active competitive programming club! Nonetheless, I still found several other competitive programming enthusiasts to practice with early on, including vkgainz and Badint, and I ended up formed a team with vkgainz and eyg for ICPC Regionals. We got third in the region and advanced to nationals, and even though we ended up underperforming a bit at nationals, nationals was still a truly amazing experience, and as soon as it ended we were already eagerly awaiting our next chance to go to nationals. eyg was graduating that year, but vkgainz was also a freshman at the time, so we were already scheming about who to add as a potential third member for the next year’s team, tentatively considering Bungmint, an incoming freshman for the next year who had reached International Master.

Meanwhile, over the summer after nationals, I decided to attempt to start an actual competitive programming club at Berkeley. We had sent 27 people to regionals last year, and we had over 80 people on the informal Discord server we had made the previous semester, so it seemed like the interest was there, and starting a successful club would be a matter of having good recruitment and enough club activities. After assembling an officer team and advertising the club during the first few weeks of the fall semester, we quickly exceeded expectations in terms of club membership, with over 200 people joining our Discord server within a span of a week or two. Berkeley’s notoriously busy classes ended up causing some challenges for club participation rates, but the first semester of the new competitive programming club was ultimately a success, and over winter break, we devised plans for how to select ICPC teams for this year’s regionals.

We decided to run a single selection contest of past ICPC problems on Kattis, and alum and former teammate of mine eyg volunteered to select the problems and make the contest. In hindsight, this contest structure really wasn’t a good idea; we should have either used the NAQ, like many other schools did, or run multiple contests to get a more complete picture of people’s ability levels. The single-contest structure ended up producing some funky results that would ultimately cause the chaos that ensued at last weekend’s regionals. Nonetheless, we moved forward with this single-contest structure, and I was personally really excited for it: I had done a fair amount of Codeforces rounds in the past several months, but outside of that, I hadn’t done a major one-time contest like ICPC since nationals last year. I was expecting to get 2nd or 3rd, maybe 1st if I had a good day. I got a good sleep the night before the contest, I did a lot of practice leading up to it, and I was ready to do my absolute best in the contest. The contest comes along and… I get 16th place. Out of only Berkeley competitors. I barely even made it onto one of the teams that we sent to regionals, even though I had gone to nationals the year before! I definitely had a bad contest, but it also showed that we had a lot of really strong competitors – we had 33 total competitors, so we unfortunately had to cut nearly half of the people interested in ICPC Regionals.

After the competition, we immediately went to select teams. Myself and several of the other club officers selected the teams based on selection contest results and other factors, such as Codeforces rating and past ICPC performance. Due to my disappointing selection contest performance, however, I knew I had no chance of being on the top team, and we ended up selecting vkgainz, Bungmint, and Badint for what we presumed would be the strongest team we would send to regionals, Berkeley Blue.

Since only one team per school is allowed advance to nationals, I knew at this point that my chance of going back to nationals would be incredibly unlikely, since whatever team I was on would have to beat this insanely strong team of one Grandmaster and two Masters. At this point, I decided the best move would be to form a team with myself (plourde27), yjp20 and voidcs, since the three of us were already friends outside of competitive programming, and I figured we would be able to practice a lot and work really well as a team during regionals. Since the three of us often went rock climbing together, we named our team “Burden of Dreams”, as a reference to the hardest boulder problem in the world. We began the month-long grind for ICPC regionals, doing many team practice contests every week.

On the day of the contest, we woke up bright and early to travel to Chico State for the contest. Since Berkeley Blue was such a strong team, we figured that if we were somehow able to upset them at regionals, that would almost certainly be enough to qualify for nationals, since it was extremely likely that they would both be in the top 5 in our region, and also be the highest-ranked Berkeley team. This created a weird situation where the other schools almost didn’t matter to us; it essentially felt like a 1v1 versus this one team. We begin the contest, expecting to battle it out with this team, and maybe, just maybe, if we had a really lucky day, beat them and go back to nationals.

There are two easy problems, C and J, that we spot right away. My teammates have me code both of them up, since I’m usually the fastest at coding up easy problems. We have a brief snag early on where VSCode takes literally 15 minutes to load and we have to use Vim for the first few problems (I’m embarrassingly bad at using Vim, and this made the start of the contest really stressful for me). Luckily, we push through the IDE issues, and get both of the easy problems after 14 minutes, which puts us in second place in the region, although this is way too early in the contest to read into results too much. Shortly after, I read F and realize that it’s also a fairly easy greedy, and we solve it 37 minutes in (and VSCode finally loaded! after a full 15 minutes of contest time!). Unfortunately, we run into a bit of trouble after this, as I coded up solutions for both A and B that both had minor WA bugs.

We go a good 2 hours without solving anything new, and our rank drops all the way from 3rd down to around 15th, which was pretty demoralizing. Despite this, around the halfway mark of the contest, we were shocked to see that even though we were behind 4 of the other Berkeley teams, we were somehow ahead of Berkeley Blue! This was truly shocking to us, but we tried to not let these weird results distract us, and we figured Berkeley Blue would no doubt catch up later in the contest.

After this rough 2-hour stretch, we suddenly have a flurry of good luck, where yjp20 comes up with a smart solution to D that passes first try, I fix a bug in my solution to K and manage to somehow get AC first try with a really sketchy bitmask DP solution, and I find a truly hilarious bug in my WA submission to A and get AC on it soon after debugging K. Just like that, we’re back in 3rd place, with the freeze period soon approaching. At this point, we took stock of the scoreboard, and realize that even though we’d focused everything on beating Berkeley Blue, there’s actually another Berkeley team, Golden State Geeks, consisting of linpaws, ss1237, and fatant, who was in 1st place by an entire problem going into the freeze period. Meanwhile, we’re still somehow a full problem ahead of Berkeley Blue.

We go into the freeze period knowing that we likely need to solve at least 2, and probably 3-4 problems in order to pass Golden State Geeks and advance to nationals. We have some good luck right at the start of the freeze period, however, where I add another case to my DP for B and get a truly unexpected AC, to bring us to 7 problems solved, as many as Golden State Geeks, although we’re still way behind on penalty. Meanwhile, voidcs has just come up with a really smart solution to H, and he gives it to yjp20 to code, since he’s good at solving tree problems. During the ~20 minutes it takes yjp20 to code H, I take a look at E, which was an interesting constructive problem. Normally, this is one of the types of problems I’m best at, but I’ve been stumped on this particular problem for the whole contest. Nonetheless, I come up with an idea with about 30 minutes left, but it involves a super gross implementation-heavy solution that I’m not sure we have time to code. Luckily, at this point yjp20 gets AC on H, so we’re now up to 8 problems solved, and we have a legitimate chance of advancing to nationals if we can solve E! I spend the next 25 minutes coding E at one of the fastest typing speeds I’ve ever coded a solution at, but unfortunately, it’s not quite enough. With just a few minutes left, I still have a bunch of tricky edge cases to work out, and it ends up not mattering, since Golden State Geeks solved two problems during the freeze period as well, and they would have beaten us on penalty even if we had managed to solve E.

We finish the contest, and see that we’re in either 2nd or 3rd place depending on how many problems the top Stanford team solved during the freeze period (we ended up getting 3rd). To our amazement, even though we didn’t end up making nationals, we still beat Berkeley Blue, who ended up coming in fourth place with 7 problems solved. What was even more exciting, however, were the results for Berkeley as a whole. Somehow, we ended up placing 4 teams in the top 6, and all 6 of our teams placed in the top 15. While we were obviously really happy with these results, we also wondered if it was in part caused by our questionable team selection contest format decisions, since it’s possible that many of the teams were uneven and could have been paired better.

Even though we didn’t make it to nationals, it was still honestly the most fun competitive programming contest I’ve ever participated in. I had a really great team, the problems were super high-quality (props to the problem writers and judges!), and we had a really fun almost-comeback at the end. I will be rooting for linpaws, ss1237, and fatant at nationals in May, and I’ll be training for next year’s regionals in the fall in the meantime, which will hopefully be just as fun as this one.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en12 Английский plourde27 2023-02-27 08:27:06 0 (published)
en11 Английский plourde27 2023-02-27 07:28:25 5 Tiny change: 'process.\n[cut]\nOur stor' -> 'process.\n\nOur stor'
en10 Английский plourde27 2023-02-27 07:28:08 4 Tiny change: 'process.\n\n[cut]\n\nOur stor' -> 'process.\n[cut]\nOur stor'
en9 Английский plourde27 2023-02-27 07:25:33 44
en8 Английский plourde27 2023-02-27 07:25:04 128
en7 Английский plourde27 2023-02-27 07:19:39 14
en6 Английский plourde27 2023-02-27 07:17:54 12 Tiny change: ' [user:yjp:20] comes ' -> ' [user:yjp20] comes '
en5 Английский plourde27 2023-02-27 07:17:31 437
en4 Английский plourde27 2023-02-27 07:14:38 169
en3 Английский plourde27 2023-02-27 02:29:08 24
en2 Английский plourde27 2023-02-27 02:27:39 276
en1 Английский plourde27 2023-02-26 23:42:57 11727 Initial revision (saved to drafts)