ICPC

ICPC AWF took place on 8 March 2026, and while official confirmation will take some time, my team should almost certainly qualify (based on the ranklist, previous year trends, and unofficial hearsay from the organizers).

I hate forgetting the details of "important" events of my life, and then later having to make do with vague recollections (aside: admitting that qualification to WF mattered enough to me to warrant the effort this blog will take to write is a bit embarrassing, but I've recently made a resolution to not hide behind self-deprecating irony as an emotional defense as frequently as I once did). In anticipation of this, I'll be dumping a lot of information about my experience with ICPC in general, along with most of what I can remember about AWF 2026 in particular. As such, this might not be the most pleasant reading experience for anyone except me.

Background

I am, in the most extreme sense of the word, a filthy tryhard at ICPC. I've been to the regionals seven times now, and to AWF thrice.

Unlike my performance in online contests, where I can clearly recognize periods where I've under/overperformed, it has always seemed like my team has, with the exception of this last contest, severely underperformed relative to other teams at an apparently similar level of strength. On the journey home after almost every ICPC contest, we would be plagued by a vague sense of disappointment and gloom - the mistakes we made would appear so infuriatingly simple and preventable in hindsight, the process of correcting trivial mistakes during the contest so glacial, the problem selection so unfortunate. The observations we made about our shortcomings in the aftermath of these contests were rather similar after every one of them, but we would fail similarly and draw similar conclusions time and time again. It didn't help that a lot of these shortcomings had no obvious remedies.

For instance, we were slow at everything except mindsolving problems. One could attribute it to a variety of micro-errors (like initially misinterpreting the problem statement, not reading the constraints carefully, being slow at implementation, etc), and we often laid these out explicitly, but at the end of the day, all of these seemingly disjoint errors would just coalesce into the simple, uncomfortable truth that we were too slow. This was a bit hard to stomach for me, as I tend to be very fast individually in online contests, and all of these novel micro-errors never seemed to appear in that environment.

The objective conclusion to draw here might have always been that we weren't inherently good enough at this format of competition. With that being said, I'm glad we never really accepted this reality, and instead distracted ourselves with all of the useful delusions mentioned previously, as we did finally make it through. To be clear, I don't think we improved all that much as a team despite having significantly improved individually, and this success is likely just a consequence of having shamelessly farmed $k$ to the point where $P(\text{success})$ being low for a single contest didn't matter all that much to $(1-P(\text{success}){)}^k$. But maintaining, and perhaps slightly increasing this $P(\text{success})$ across so many contests in the face of repeated failure would probably have not been possible if one acknowledged how low $P(\text{success})$ was at the very beginning.

But I digress, I promised not to drown myself in self-deprecating irony.

I should talk about the teams I've been a part of.

Note: The names of my teammates have been replaced with pseudonyms.

Year 1

For my first year at ICPC, my team was a ragtag group of novices that got together at the very last moment. I had been at college and had been doing CP for just about 4 months, and people were (understandably) not exactly enthusiastic about forming a team with me. It was a miracle that we qualified in the first place, as the team comprised two experts and an inactive newbie (I apologize for my casual ratism). We somehow managed to edge past way stronger teams, with one literally having a master and a CM.

Years 2-3

My team for the next two years was far more respectable. It consisted of me (a master on CF by this time) and two people from the year above me: GeometryDashAddict and WellGroomedHair (master and CM respectively). The structure of the team was promisingly coherent:

• I specialized in "difficult" problems in general, and was strong in knowledge-heavy areas like Data Structures, DP, Graphs/Trees, etc in particular. I was also notoriously unreliable at implementing my (mostly correct) solutions to these difficult problems, but let's not get into that.

• GeometryDashAddict was a sort of jack-of-all-trades, and the best amongst the three of us at "just getting the thing done". This included, but wasn't restricted to:

  • Simplifying and implementing problems that me and WellGroomedHair would have implemented long and buggy code for.
  • Helping debug our solutions, finding blind spots that we formed w.r.t. our solutions due to familiarity, constructing counter-examples to our conjectures, etc.
  • Solving weird ad-hoc problems that I would instinctively recoil at.

  He also had a penchant for solving geometry problems, which neither WellGroomedHair nor I seemed to have a chance in hell of solving (actually, WellGroomedHair could probably have solved some of them).

• WellGroomedHair was really good at what I will crudely describe as the more "mathy" problems. By this I mean problems that were "generally algebraic" (for instance, those requiring casework around floors and ceilings), involved number theory, combinatorics, etc. He was also good at weird ad-hoc problems (of a different kind than GeometryDashAddict, it's hard to explain this concretely without giving specific examples). GeometryDashAddict and I would quite frequently buckle under pressure but he seemed quite impervious to the same. He was also by far the most capable one of us in real-world matters, single-handedly managing all the logistics around our annual pilgrimages.

This description of the team probably belies our mixed and somewhat disappointing bag of results. We made it to AWF in both years, with our performance at regionals always leaving much to be desired. While our performance at some regionals was at least partially acceptable (most notably, some last-hour clutches), everything that could go wrong, did at AWF 2024 and 2025.

In our defense, the room we were assigned in the name of "accommodation" at the venue in 2024 literally had a hive of wasps on the window, with enough pathways through the broken frame for them to pay us a visit whenever we turned the light on. Thankfully, some students at the host university were sympathetic enough to allow us to sleep in a room that they had apparently illegally occupied (after concluding that the smoke produced by smoking cigarettes in our room wouldn't suffice to get rid of the wasps and the mosquitoes). We went to bed around 4 AM on that night, and only had 3 hours of uninterrupted sleep before the contest. Ah, Indian ICPC...

If I was forced to preserve just one memory from all of my experiences with this team, I would probably selfishly select the following:

This got way too long

Problem H from AWF 2024 reduced to the following:

You're given a permutation $p$ of integers from $1$ to $n$. You're required to perform $q$ queries of the following kind, online:

Given , swap $p_i$ and $p_j$ (updates persist).

Then, consider the cycles in the functional graph formed by this permutation (i.e. add an edge from node $i$ to $p_i$ for every $i$). Report the number of such cycles after every query.

Constraints: $1\le n,q\le {10}^5$

Even in the infancy of my (then ~1 year old) CP career, I had developed an addiction to DS-bashing and possessed an inappropriate amount of knowledge about data structures relative to my immaturity in other domains. I realized that this would be a trivial application of a Link-Cut Tree... if only we had bothered to include one in our team reference notebook. Funnily enough, despite the straightforward LCT solution, there weren't any solves on the problem in the first half of the contest.

While my teammates devoted themselves to problems that we had a way higher chance of solving, I turned to perhaps an even more potent addiction of mine - Square Root Decomposition. Looking back, this technique and I have always been a match made in heaven, as it often allows one to soothe his ego through the satisfaction of solving "hard" problems bashable by it, in exchange for the sweat and toil that the implementation and casework in overengineered solutions involving it require. This reminds me of a list of "hard" sqrt-bashable problems that I once maintained: link.

Returning to the problem - I devised a correct strategy using square root decomposition on the query sequence. The high-level idea was the following:

• Let's divide the query sequence into disjoint blocks of $B$ queries. We'll process each block independently.
• To process the $b$-th block, we do the following:
  • First, derive the state of the permutation after executing all queries in the $b-1$ blocks behind it.
  • Now, for all $i,j$ in queries in the $b$-th block, mark nodes $i$, $j$, $p_i$, $p_j$ ($p_i$ and $p_j$ are the values after executing the first $b-1$ blocks of queries) as "dirty". Note that a node may be marked "dirty" multiple times. There will be $O(B)$ dirty nodes.
  • We now have a set of permutation cycles as defined by the permutation state after $b-1$ blocks, and a set of dirty nodes as defined by block $b$.
  • The key observation is that throughout updates within block $b$, no edge that doesn't have a dirty node as an endpoint will be affected. As every node has an in-degree and out-degree of $1$ (self-loops being a special case), only $O(B)$ out of $n$ edges are affected.
  • We can therefore view the set of cycles as some static cycles (with no dirty edges) and a set of $O(B)$ directed chains, which are internally static, but can have the incoming/outgoing edge of their endpoints modified with updates.
  • So before processing updates for block $b$, we perform some ugly $O(n)$ preprocessing to compress these static chains into their endpoints (as their internal nodes don't matter at all), which then allows us to process queries in $O(\text{number of static chains})=O(B)$.

The idea is quite simple but I wasn't really mature enough to cleanly implement this under pressure at the time, and ended up implementing a horrendous mess I couldn't debug. The fact that online handling was enforced through encrypted input made manually debugging the code especially tedious.

On the other hand, the problem ended up being a "team notebook check", as only 5 teams managed to solve the problem during the contest, and all of them shamelessly bashed it with an LCT. I pettily consoled myself with the knowledge that I hadn't resorted to such brutish tactics as them. Upon returning home, I promptly added LCT to our team notebook. The ICPC gods never demanded it of me again.

What made this problem memorable is the process of debugging it after the contest. I don't remember why my laptop was inaccessible on the journey home (perhaps I didn't bring it), but it wasn't, and I borrowed WellGroomedHair's laptop. One must remember that this was back in medieval 2024, before we had access to LLMs that could take your code, prove/disprove its theoretical correctness with reasonable accuracy, and also stress-test it on a suite of self-designed tests to find concrete counter-examples. As such, I was left to fend for myself. Divorced from that indescribable obsession of the moment as I now am, it feels strange to not have just slept instead (remember, we only slept for 3 hours before the contest, and I was essentially pulling another all-nighter during travel). I was operating with a terrible headache and the working memory of a goldfish, while intermittently treating myself to sweet microsleep, as annoying babies on our coach wailed their hearts out.

A few hours later, while sitting on a bench at the airport, the judge slowly gave in to me, and the screen flashed green.

I later realized that a few characters of diffs sufficed to correct my original code.

Note: The site that originally hosted AWF 2024 seems to have been taken down, and I didn't find the problemset anywhere except an archive that may or may not persist, so I've stored a pdf of the same on my own cloud storage: link

Year 4

GeometryDashAddict (and to a lesser extent, WellGroomedHair) had stated before AWF 2025, that he was tired of ICPC and failing qualification to WF this year, would definitely quit ICPC and probably stop taking online contests too. I initially assumed that they were being sarcastic, but as the months after the contest dragged on, and the green connected components on their CF heatmaps receded into the past, I realized that they were being serious. In the meantime, another strong competitive programmer from their batch - GrokSponsoredPS5, asked me if I wanted to form a team with him. I agreed and we started searching for a third teammate. We had initially hoped to draft WellGroomedHair back into the mix, but he was non-committal and we were worried. GrokSponsoredPS5 was pretty enthusiastic about giving world-finals a serious shot, as it was his last year in university, but it didn't seem like the two of us alone would have a decent chance.

WellGroomedHair eventually confirmed that he didn't want to take part this year, and we were back to square one. I forget the exact events that transpired in the intervening period (from what I remember, GrokSponsoredPS5 asked some of his former teammates if they'd like to join, but they declined), but we eventually decided to try to convince GeometryDashAddict to join our team. He had been taking contests (and performing well in them), but inexplicably showed no interest in joining. We would shamelessly ask him to join, and he would decline, again and again.

However, GeometryDashAddict's resistance wasn't to be the "immovable object" in the face of the "unstoppable force" of our persistent, guilt-tripping requests. He eventually gave in, after GrokSponsoredPS5 just added him to "our" team's WhatsApp group without him having even said "Yes" yet.

Despite having acquired the final piece that we so desperately desired for our team, we still had reason to be a bit pessimistic, as this team had very little experience together. Further, our skillsets didn't diverge nearly as well as they did in the previous team, with me and GrokSponsoredPS5 having a large overlap in our strengths.

We tried to take as many practice contests as we could in the few months we had before regionals, but I was still generally uncomfortable with our consistency and teamwork. This unease was reinforced by a scare at the online prelims itself - we barely qualified to the regionals, because I couldn't debug my code for a problem that we mindsolved within a couple of minutes. I eventually gave up on my code, and GeometryDashAddict went ahead and implemented (a slightly different version of) the solution independently, only to be met with WAs like me. Reinspecting our code after the contest revealed that both implementations could be made to AC by just a couple characters worth of diffs, with GeometryDashAddict's version literally only requiring a 0 to be changed to a 1. In the aftermath, we set this horrific contest aside as a freak accident and did our best to forget it.

Returning to the regionals/AWF, we were working against another constraint - GeometryDashAddict and GrokSponsoredPS5 would begin their internships in the beginning of January, just after the second regional, and wouldn't be able to commit a non-trivial amount of time towards team practice for AWF, which was to take place in March. In this case, the silver lining was my eternal NEETdom ensuring that I remained unaffected (unemployed) and could practice a lot on my own to try to offset any rust the two of them might inadvertently acquire. This was still less than ideal in any case, so we were aiming to somehow win the regional at Chennai (it had lesser competition than Amritapuri) to secure a direct qualification to world-finals, without needing to risk everything upon our performance at AWF.

... well, it should be evident that we didn't win at Chennai. No more on that.

Our performance in the prelims also condemned us to the ignominy of having to take the Amritapuri regionals from a site that wasn't Bangalore or Amritapuri (sites are allocated based on one's rank in the prelims). In our case, the site was Coimbatore. The host university was nestled within a surprisingly scenic mountainous region. In retrospect, this only added to the whimsical nature of the disaster that followed. Unlike the-regional-that-shall-not-be-named, our performance here was irredeemable. The three of us sucked as a team, and as individuals. To add insult to injury, we were somehow ranked first within the Coimbatore site and while this would hardly have been noticed in isolation, the well-meaning director of the site painfully impressed this upon us by presenting us with an award for our "excellent performance" during the final ceremony.

We returned to Bangalore with the same unpleasant uncertainty around our chances of qualification to AWF that had previously plagued us after the prelims. With just around 60 days remaining, I decided that it would be optimal to assume that we had qualified, and solve as many problems as I could.

AWF 2026

In the weeks leading up to AWF, most of my fears materialized (losing momentum, my teammates not having enough time to practice, etc.). And yet, despite the stakes being as high as they always were, everything seemed to lack the sense of gravity it once possessed. I was practicing pretty hard, but there were also days when I'd just aimlessly study low-level programming, play video games, or read all day. To be more specific, I got into CRPGs during these few months, and also read a lot of science-fiction. My teammates were working really hard at their internships and setting aside entire days for 5-hour practice contests was out of the question for them. I did ask them to take individual contests at a reasonable pace, and their performance in these contests didn't really reveal any significant loss of form. Perhaps not all was lost, even as some part of us had pre-emptively accepted yet another failure as inevitable.

The days eventually trickled by, and as my playtime on DOS2 reached one hundred hours, the week of AWF had already arrived.

A recurrent pattern in my relationship with long-distance, inter-city travel has been that it tends to revolve around easily preventable sleep-deprivation. This has been true for both the journey(s) from our college to the venue (for some reason, I always find excuses to not sleep on the night before the day of travel), and the journey(s) back. The latter has led to some of the most hellish experiences of my life. I don't use the word "hellish" lightly here, these journeys have often involved me marinating in shame and sorrow over a disastrous performance with my aching, sleep-deprived brain, while my body and senses were subjected to the general overstimulation that overcrowded Indian railway stations and airports are infamous for.

The 2025 Chennai regional stands out to me in this regard. We had booked a train from Chennai to Bangalore that left around 10 PM, and after a particularly disappointing showing at the contest, I was eager to get back home and go through the familiar ritual of forgetting painful details. As the railway station didn't exactly offer a pleasant environment to pass time in, we spent time at a 24-hour restaurant until the time of departure was close. We reached the railway station on time, and waited for our train, which seemed to be running late, and hadn't arrived at the station yet. I casually acknowledged how funny it would be if the train right in front of us was the one we were waiting for. Well... yeah. As the train started moving out at the exact time ours was supposed to, WellGroomedHair began to share my growing suspicion about the train's identity. We frantically chased the train for a bit until we were alongside some coaches that confirmed our suspicions (through labels that weren't visible on the coaches we had previously seen). WellGroomedHair wanted to try and board the moving train, but there was no way I was risking death in such a humiliating manner. GeometryDashAddict wasn't on board (excuse the pun) with the idea either, so we just stood there and watched our ride rush by, as a ticket collector stuck his head out and screamed at us to not get on. After some discussion, we decided to take a train at 6 AM on the same day. Perhaps the funniest detail here is that we went right back to the same 24-hour restaurant until our second train arrived. We also spent time at this place when we were in Chennai the year before, so I suppose it deserves a mention by name: link.

Anyway, after a couple of weeks of excellent, regular sleep before AWF, I had the bright (and entirely novel) idea of not sleeping the day before we travelled to the venue. We were taking a plane from Bangalore to Delhi, and reached the airport with almost an hour to spare (before the boarding period for our flight ended). We decided to have some overpriced food before boarding, and as luck would have it, we picked the place with the slowest service in the entire airport. GrokSponsoredPS5 and GeometryDashAddict assured me that there was no way we could miss the plane, as we waited for the terrible Italian food we were to eventually be served. Apparently, airlines no longer have the good grace to make announcements for entitled passengers who show up fashionably late, as they refused to let us board after we showed up a minute or so after boarding officially ended. I was zoned out of my mind by this point, and can only vaguely recall GrokSponsoredPS5 somehow getting us tickets for a flight to Delhi that left an hour later.

Ever since the wasp fiasco at AWF 2024, we've been rather cautious about the "accommodation" provided at the host university (which has been the same for AWF over the last few years), and have opted to instead stay at a hotel the night before the contest. We did the same this year, and I had an excellent night of sleep after about 48 hours of deprivation.

On the next day (7 March), GeometryDashAddict wanted to take a 5-hour practice contest but we realized that there wasn't really enough time if we were to also go to the contest venue for team registration in the afternoon. We opted to take a 3-hour practice contest instead, and there was nothing notable in either direction about our performance.

The rest of the day went pretty smoothly - we went to the venue and registered our team, peeked into one of the rooms allotted to us as "accommodation" to be greeted by the all-too-familiar sight of wasps menacingly pacing the window, and eventually returned to the hotel.

[attach pic]

At night, GeometryDashAddict and GrokSponsoredPS5 told me a bit about their experience at work and, well, perhaps I'm better off as a hikki. In an attempt to cast a sort of "anti-jinx", we discussed embarrassing/unpleasant tasks we would perform in the hypothetical scenario of qualifying to WF (one could think of these as "offerings" to the universe - as some negative experiences we would willingly put ourselves through, in exchange for just a little bit of good fortune the next day). My task was perhaps the hardest, as I promised to give up [REDACTED] and [REDACTED]. GeometryDashAddict said he was exhausted and would quit his internship. GrokSponsoredPS5 posed several less extreme tasks to himself, which was a sneaky strategy because he just chose to do the least embarrassing one after the contest.

For whatever reason, the next day's contest (and its result) wasn't demanding a lot of attention from me. After spending about an hour in the shower, I retired to bed and read some Chesterton before falling asleep around 11:30 PM.

The absence of anxious, jittery excitement that has been typical of me in the past persisted into the next morning. GeometryDashAddict told me to do my best to not get agitated during the contest, as it makes him nervous. I feel that looking outside the window on cab rides introduces a lot of unnecessary clutter to one's mind, so I did my best not to on the ride from the hotel to the venue. My teammates were quite hungry because we hadn't had breakfast at the hotel due to a lack of time, and decided to have the food provided at the venue. I'm used to going without food for long stretches, and didn't find the food there particularly appealing, so I just walked for a while, enjoying the pleasant weather.

GrokSponsoredPS5 didn't want to risk our luggage getting stolen from outside the contest hall, so we decided to stow it away in one of the rooms allotted to us. As GeometryDashAddict and I trudged towards the hostel, the venue made its surreality felt with the sight of dogs and monkeys viciously fighting. The weather was really quite excellent. Storing our bags in the room with the wasps didn't seem like a very good idea, so we put them in one of the other rooms allotted to us. This one happened to house lizards, but we didn't really mind, and I even find the little critters oddly cute. In fact, we later discussed at length how disgusting certain organisms are, and only GrokSponsoredPS5 found lizards disgusting (GeometryDashAddict going so far as to reverently refer to them as "mini-dinosaurs"). I don't know how GrokSponsoredPS5 was also the only one of us who didn't find cockroaches disgusting. Anyway, GeometryDashAddict and I made our way back after a few minutes.

The Contest

Some parts of the building that contained the contest hall seemed to be under renovation, and as we coughed our way through the dusty corridors in search of our destination, I wondered if the loud noises being made by power tools yesterday would trouble us during the contest. The dysfunction in this country would appear charming on paper if I didn't have to live in it. We eventually found the right room around 9:15 AM, and settled ourselves in for the next 6 hours or so (the contest was to take place from 10 AM to 3 PM).

Typing out templates in the allotted 15-30 minutes before the contest begins has always been one of those things that I imagine a layman would naively predict to matter a lot (even if only in the initial few hours), but doesn't quite seem to in practice. Nevertheless, I typed some boilerplate code to be used across all files, a fenwick tree, and a modular arithmetic template (I always ask GeometryDashAddict to type the modular inverse function for some reason). In previous editions, most of this time would have been spent typing some over-engineered debug helpers. It's hard to explain why I absolutely needed these without sounding like an obstinate asshole, so I won't.

template<typename T> 
void __print(const T& x) {
    if constexpr (is_arithmetic_v<T> or is_same_v<T, string>) cerr << x;
    else {
        cerr << '{';
        if constexpr (requires {x.first;})
            __print(x.first), cerr << ", ", __print(x.second);
        else {
            int f = 0; for(auto i : x) cerr << (f ++ ? ", " : ""), __print(i);}
        cerr << '}';
    }
}
template <typename... A>
void _print(const A&... a) {((__print(a), cerr << ", "), ...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__); cerr << "]\n";

Previously, I've tried to avoid spending time at the keyboard for as long as possible (out of a belief that it exhausted me and degraded my mindsolving ability), and instead preferred to delegate the implementation of mindsolved solutions to my teammates. This had always seemed pretty irrational to my teammates as I was the fastest amongst us in individual contests, but as you might be beginning to understand - I'm a pretty stubborn person. Anyway, I had been gradually made to see reason over the practice contests we took in the last few months, and was going into the contest with the knowledge that I would be implementing the bulk of the code we submitted.

A few minutes before 10:00 AM, it was announced that the contest was to be delayed by 15 minutes, so I typed as much of our lazy segment tree as I could before the contest started.

Note: I will be referring to problems by their letter codes going forward. The problemset can be found here and also on CodeChef here.

10:15 eventually arrived and we were upon the problemset like a rash. Having previously been burned due to a lack of attention at the start of contests, we gave every problem a cursory glance while constantly refreshing the solve counts. There weren't any solves for the first few minutes, so I looked for problems with reasonably simple setups (a decent proxy for difficulty).

Amongst the problems I had seen, G and L seemed to be the most promising candidates.

L was the following:

Given integers $n\in \{8,{10}^6\}$ and $k$, find any permutation $p$ of integers in $[1,n]$ such that $\sum _{i=1}^{i=n-1}gcd(p_i,p_{i+1})=k$.

I didn't like the look of the problem, and handed it over to GeometryDashAddict, who tends to enjoy problems like these.

G on the other hand, seemed rather straightforward, and the outline of an implementation-heavy solution with a trie was materializing in my head. As I showed the problem to GrokSponsoredPS5, some part of me warned me to not fixate upon non-trivial problems at the beginning of the contest (which had been my most reliable strategy for ruining our performances in the past).

In the midst of this, E got its first solve, drawing the attention of me and GrokSponsoredPS5. I don't know how this problem managed to slip through our initial sweep of the problemset, as it was quite unimpressive in both appearance and actual difficulty:

An array of integers $a$ is said to be good if for every pair of subarrays (of this $a$) $x$ and $y$:

Given some $n$ $(1\le n\le 500)$, find any good permutation of integers in $[1,n]$ if one exists. Otherwise, report that none exist.

This is the sort of problem for which you find some plausible construction(s) from a couple of observations, and then pray to your deity of choice while frantically implementing code that outputs said construction. In this case, I observed that no two elements with value could be adjacent in a good permutation, as the 2-length subarray containing them would have a strictly smaller sum than the 1-length subarray containing value $n$. I told this to GrokSponsoredPS5, and we both agreed that the construction 1 n 2 (n-1) 3 (n-2) ... seemed reasonable. It seemed like this construction would work for all $n$, but with the level of uncertainty these guesses involve, it would be foolish not to implement a check. I spent a couple of minutes writing code that computed the maximum/minimum sum for each subarray length, and then compared these for all lengths with an absolute difference of 1. This turned out to be a waste of time, as the construction did work for all $n$. I wonder if the sole reason for having $n\le 500$ instead of typical linear-time constraints was to troll participants into implementing the $O(n^2)$ check. I submitted our code at 10:30 AM, and we got our first solve of the day.

While I had been implementing E, A had also received a few solves, and upon noticing this, GeometryDashAddict and GrokSponsoredPS5 mindsolved it within a couple of minutes. I promptly gave up the PC to them and began going through the printed copy of the problemset. They discussed the solution for a few minutes and one of them implemented a few lines of code (I didn't remember which one of them implemented it, as I wasn't observing them at the time. Looking at our submission now, it was obviously GrokSponsoredPS5, as the code follows the objectively inferior convention of not putting a newline before opening braces). They submitted the code at 10:38 AM, and we were pleasantly greeted with another AC.

In the past, GeometryDashAddict and I have been wary of "exposing" ourselves to the ranklist during the contest. For me, this goes beyond just ICPC - I hate having information about how I'm performing relative to other participants in any competitive activity, during the period of participation. Imposing this restriction upon me is simple enough during online contests, as a browser extension can easily block specific HTML on troublesome webpages, but such luxuries as uBlock Origin aren't made available during ICPC. This had been especially annoying because CodeChef shows your current rank on the same page that displays invaluable information about solve counts, and not visiting this page was out of the question. In previous editions, we had tried some (admittedly insane) workarounds at my behest, with the most effective being increasing the zoom of the webpage to 200% to make the site serve the mobile version of the webpage. None of these worked well though (in particular, the zoom trick didn't work because it would also increase the zoom of the problem statement pages), and I was forced to learn to not freak out upon being made aware of our exceptionally good/bad pace. Funnily enough, neither of our third teammates (previously WellGroomedHair, and now GrokSponsoredPS5) faced this problem. Many of these thoughts rushed through my mind as we saw our rank jump to 6 after the AC on A.

Throughout my ICPC career, good starts have been scarce, with the best we've had ending in disaster at the-regional-that-shall-not-be-named. Knowing this, I kept my expectations in check. As we enthusiastically resumed our perusal of the problemset, D received its first solve about a minute after our solve on A.

D reduced to the following:

You are given a simple, connected, undirected graph with $n$ vertices and $m$ edges ($n,m,\le 2000$). The $i$-th edge in the input has a weight of $2^i$. You are also given an integer $k$, such that $\lceil n/2\rceil \le k\le n$.

Find the minimum possible total weight of a spanning tree of this graph, such that no vertex in the spanning tree has a degree greater than $k$. If no such spanning tree exists, report so.

I'm decent at trees and combinatorics, so I gladly took up this problem.

At first glance, it seemed fairly plausible that the high-level strategy would be the following:

• As , it's beneficial to remove an edge from our spanning tree even if it means having to include all edges with smaller weights to preserve validity.
• This leads to a straightforward selection algorithm:
  • Define a procedure check(i, S), which checks if it's possible to select some subset $P$ of edges with indices in $[1,i)$ such that $S\cup P$ is a valid spanning tree.
  • Start with an empty edge-set $S$. We will add edges that belong to the final spanning tree to this $S$.
  • Iterate over edge $i$ in decreasing order of weight, and on every iteration, add $i$ to $S$ iff check(i, S) returns false.
  • Finally, $S$ will constitute an optimal spanning tree if one exists, and will otherwise contain an invalid one (violating connectivity or degree constraints).

Now, only one question remained: how to implement check(i, S) efficiently?

I decided to think about what could "go wrong" if one tried a naive strategy - iterate over the edges in $[1,i)$ in increasing order of $i$, and simply add edges to the spanning tree if they: (i) unite two disconnected components (ii) do not lead to a violation of the degree constraints.

Well, the only way it would go wrong was if there were multiple connected components at the end. We're only interested in false negatives here, as there is no possibility of a false positive. In the case of a false negative, some subset from $[1,i)$ would be valid, but our naively chosen one wouldn't.

I was only a few minutes into the problem at this point, and all of this seemed rather abstract, so I asked GeometryDashAddict to just construct some concrete examples that showcased the failure of the naive strategy. As he worked on this, I pre-emptively wrote some code that we would almost certainly use, no matter our final solution - I/O and a DSU. A few minutes later, he showed me the following, with $n=7$ and $k=3$:

The issue here was that the only valid selection of edges is $\{1,2,3,4,6,7\}$, but naive selection (in increasing order of edge labels) would include edge $5$, disallowing the inclusion of $6$ and $7$ later. However, this counter-example doesn't conform to problem's constraints, as . Nevertheless, it gave us reason to pause.

$k\ge \lceil n/2\rceil$ had seemed obviously important from the very beginning and we knew that our strategy wasn't exploiting it at all. I suddenly realized that it was impossible for more than one node to have a degree greater than or equal to $k$ in any spanning tree, as it was guaranteed that $k\ge \lceil n/2\rceil$. This meant that in the case of a false-negative, the forest induced by the naively chosen edge-set took on a very specific structure:

• We're referring to the internal execution of a call to check(i, s) here. Let's call edges in $S$ "static edges", edges in $[1,i)$ that we include within $P$ - "taken edges", and edges from $[1,i)$ that we don't include - "ghost edges".
• There would be more than one connected component in the forest defined by $S\cup P$.
• There would be exactly one node with degree equal to $k$, and all other nodes would have a strictly smaller degree. Let's call this node "heavy", the connected component contained it "big", and the other connected components "small".
• There would obviously be no static or taken edges between different connected components, but the key observation is that all the inter-component ghost edges take the form $(\text{heavy node},\text{some node in a small component})$.

As I explained this to GeometryDashAddict, the team sitting in front of us audibly celebrated getting the first solve on B. I hope such a physical reminder of how we were throwing away our excellent start and falling behind, was reason enough to justify the way I threw caution to the wind in response. Or well, it would have been if my recklessness had worked out.

Wanting to be done with D as soon as possible, I offered GeometryDashAddict a hand-wavy justification for why $k\ge \lceil n/2\rceil$ was indeed enough for the naive strategy to be correct. He agreed with me, and the rapidly growing number of solves on the problem also seemed to indicate that the solution was simple. After telling GrokSponsoredPS5 to work on B, I began finishing the half-complete code for D. The code was ready in about 10 minutes and I submitted it at 11:19 AM with bated breath. WA.

I still believe that the Codeforces UI has the highest ratio of $\frac{\text{rage induced through annoying visual indicators for a WA}}{\text{satisfaction induced through pleasant visual indicators for an AC}}$, but the urge to flip the PC over that ran through me at this moment probably makes a strong case for CodeChef.

After taking a few deep breaths, I tried to calmly go through my code once again. It's hard to explain why, but in situations like these, I don't look for actual mistakes so much as I do excuses to submit incorrect code again. Deep down, I know that making more submissions with trivial modifications will lead to more WAs, which will further frustrate me, but it's hard to keep myself from scratching the itch. Perhaps it's self-sabotage, or perhaps it's me needing the weight of the additional WAs as motivation to actually do the work of examining the incorrect solution beyond just a superficial look-over. Continuing this trend, I invented a plausible-sounding story about how we might be failing to detect the violation of validity constraints upon adding edge $i$ to $S$ when check(i, S) returned false. GeometryDashAddict wasn't very convinced that this was the actual issue, but I convinced him that adding a few more checks was worth a try. It wasn't, and I added another WA on D to our tally at 11:33 AM.

While I had been busy making meaningless changes to our code for D, the team in front of us also solved C, claiming their spot at the top of the ranklist. Talk about contrast.

GeometryDashAddict noticed that I was getting agitated and told me that it would probably be for the better if we just switched to another problem for some time. He started working on C, and I asked GrokSponsoredPS5 what he had been doing with B.

B cleanly reduced to a problem on a DAG, and GrokSponsoredPS5 told me about this reduction. I confirmed the reduction by reading the problem statement from the source to be safe. The reduction was the following:

You are given a DAG with $n$ nodes and $m$ edges ($n,m\le 500$).

In one operation, you are allowed to choose some node $u$ and do one of the following:

• Delete all of its incoming edges
• Delete all of its outgoing edges

What is the minimum number of operations in which one can delete all edges from the DAG?

I tried to think about B for a few minutes, but it was apparent that I wouldn't be able to focus on it until I solved D. GrokSponsoredPS5 wanted to try some weird greedy strategy, but even after the limited time I had spent on the problem, I was sure that wouldn't work. The problem reeked of flows, and I told him to try and remodel it, but he said that he hadn't solved very many flow problems before.

After a few unproductive minutes, I just went back to D. I pestered GeometryDashAddict until he also agreed to work on it for some more time, and asked him to find a concrete counter-example for our strategy that conformed to the constraint on $k$.

While he worked on this, I pretended to think about D for some time. If one could peek into my mind and sample random phrases from my internal monologue at this point in time, a fair few of them would seem vaguely related to D, but what I was really thinking about, even if I couldn't recognize it at the time, was the undecided manner in which I was going to cope with yet another failure at AWF. Would I spend the entire summer rewatching Welcome To the NHK over and over like in 2024? Or perhaps play video games for 12 hours a day, every day like in 2025? With my teammates graduating this year, this was realistically my last chance at qualification, and I was blowing it away in real-time. Worse yet, I knew that I was blowing it away, and couldn't escape the ensuing paralysis. As I whiled away some precious tens of minutes, the team in front of us got YET ANOTHER solve. To add to my misery, it was D.

GeometryDashAddict shook me out of this spiral with a constraint-conforming example where our naive strategy failed. I do not remember the exact graph he drew, but this was the relevant subgraph, with $n=5$ and $k=3$:

Of course it was an embarrassingly trivial oversight that either one of us could have easily resolved in a couple of minutes, if this had happened in an online contest. Instead, I had spent the last two hours idly watching our rank plummet to the late twenties as I daydreamed of increasingly novel methods of self-sabotage at my disposal.

As I write this, I feel the urge to replace this detailed exposition on how thoroughly I fucked up on D with something vaguer. Something like a short paragraph that sarcastically plays these mistakes off as a "cute" scare which never posed any real threat. Something that while technically true, allows me to cower behind plausible deniability and allude to some more respectable explanations, instead of having the workings of my imperfect mind laid out bare.

As some consolation, GeometryDashAddict told me that C had been mindsolved. After some discussion with GrokSponsoredPS5, the two of them took control of the PC, and I resumed the unenviable task of wrestling D into submission.

The problem was that check(i, S) was still producing false-negatives. Say we run the naive strategy and end up with an incomplete spanning tree (ie. disconnection). I feel physically uncomfortable as I admit this, but for the last two hours, I had failed to realize the fact that in some situations, one can recover from this state by doing the following:

• Remove some "taken" edge of the form $(\text{heavy node},c)$ from $P$.
• Add a ghost edge from some node in the now-disconnected component containing $c$ to any node in the big component except the heavy one.
• This reduces the degree of the heavy node by 1 while maintaining the same connectivity relations. We can now add a ghost-edge from the heavy node to a small component, which was previously not possible.

After some more unpleasant analysis, I realized that performing these "rebalancing" operations was indeed enough to always produce a valid spanning tree in check(i, S) if one existed. However, a concrete solution still wasn't in sight, as a naive implementation of this strategy would run in cubic time. By this point, my dread for this problem had turned into an impatient annoyance. I knew that I had all but solved the problem. The problem knew that I had all but solved it. And yet, it continued to teasingly dart out of reach whenever I made an advance.

In what was to be a successful attempt to calm down, I excused myself to the bathroom. Strolling through the corridors at a leisurely pace, I was reminded of something from the distant past of 4 hours ago - my concerns about noise from the power tools had been pleasingly unfounded.

As I returned to the contest hall, the solution came to me in that inexplicable and annoyingly natural way that solutions to problems like these do, making the prior drought of ideas seem so utterly pointless. Perhaps the problem felt that my miserable devotion over the last few hours had proved me worthy, or perhaps it was made jealous by me wondering if I would return to an unexpected AC on C.

Progress required considering $k$ once again. When the naive strategy ended with multiple components in the case of a false negative, the heavy node had exactly $k$ children. This allowed the following (simple) strategy to work:

• Run a naive first pass like before to get an edge set $P$.
• Then, remove all the static edges incident to the heavy node from $P$. Run a second pass where you add edges with the exact same logic as the first, but instead of doing it for all ghost edges in $[1,i)$, do it only for the ghost edges in this range that aren't incident to the heavy node.
• Then, run a final third pass where you consider all the remaining ghost edges.

I settled back into our booth, cheerfully informed my teammates that I could begin implementing D (again), and was met with an understandable lack of enthusiasm. GeometryDashAddict asked me if I was sure that the solution was correct, and if this time wouldn't be better spent with me just going to another problem. I justified implementing the solution with the fact that they had stepped away from the PC due to some logical problem with their solution for C, and I might as well use keyboard-time now. Thankfully, it took me only about 10 minutes to code the additional two passes and verify the absence of simple bugs.

Even after testing the code against a few hand-crafted samples, I wasn't quite sure that I had implemented it correctly. After a sufficient amount of iterative modifications, one transitions from marvelling at code behaving correctly because of its structure, to marvelling at its ostensible correctness in spite of its structure. With this uneasy admiration, I pasted my code into the CodeChef IDE, and hit "Submit" at 1:03 PM.

AC.

The change in the atmosphere was immediate. At least we weren't going to end the contest with a humiliating total of 2 solves. I heaved a sigh of relief, and was suddenly all too aware of a sensation I had been inured to over the last few hours - my head was painfully throbbing. My teammates, appearing somewhat hopeful after the suffocating monotony of the last few hours, immediately took back the keyboard to implement C. While this solve had mattered a lot to our emotional state, it barely registered on the scoreboard. We had simply gone from being amongst the teams with 2 solves and really low penalty, to having 3 solves with really high penalty, and still remained in the late twenties.

In hindsight, it's quite unusual that I didn't just give up at this point (even if in a passive, unspoken manner). With little more than 100 minutes remaining, we were languishing in the midwit's zone of the scoreboard with 3 solves, and several teams already had >= 5. It's not really the case that I was consciously making some sort of conscientious decision to do my best till the very end, I was probably just too emotionally exhausted to even be able to care any more.

Whatever the reason, I suddenly found myself able, and in fact compelled, to calmly and unconditionally devote myself to the unsolved problems that remained. At this point in time, B, C, and D all had about 20 solves. G, J, L, and H appeared to represent a sharp jump in difficulty, with all of them having <5 solves. Since we almost necessarily needed to get B if we were to stand any real chance of qualifying, I turned to it once again.

In graph problems with as simple, and general reductions as this one, it's hard to get any "handholds" of specificity that you can use to put said problem into a chokehold that would make it tractable. There's always this suspicion that you might have missed a few details that would prevent you from needing to solve the fully general version of the reduction. This anxiety combined with some unpleasant associations I had built between B and D from my brief encounter with the former during the painful process of solving the latter, and led to me setting aside the problem once again.

As I went through the set of "hard" problems with non-zero solves, my teammates made more progress on C. At 1:15 PM, they made our first submission for the problem, and were promptly met with a WA. Unlike our previous submissions, where every WA felt like a punch to the gut, our response was more calibrated to the actual banality of a single WA - mild displeasure, and an eagerness to resolve it. They began examining the code for bugs, and I returned to my own search for a problem to solve.

G called once again. I knew that I would almost certainly mindsolve it quickly, but I hesitated in committing to it. It was clear that the solution would involve DFS over a trie in some capacity, and I have had an unpleasant relationship with tries throughout my entire career. We simply didn't have the time for me to write long and buggy code that I then spent tens of minutes laboriously debugging. I turned to the other hard problems - I had already seen L at the beginning of the contest and it had seemed cancerous even then, so the only real choice was between J and H. Both of them had just one solve till that point. Scarier yet, the only solve on both of them was from what was by far the strongest team in the entire continental region - a team being carried by India's only LGM.

I pettily reminded myself of the fact that I had technically AKed a div-2 before him once and read H.

The statement was as follows:

You are given a string $s$ of length $n$ ($1\le n\le 400$) consisting of lowercase Latin letters.

You need to partition $s$ into two disjoint subsequences $x$ and $y$ such that each character of $s$ belongs to exactly one of the two subsequences.

Without loss of generality, assume $|x|\ge |y|$ (otherwise, swap $x$ and $y$). Append character 'a' to the end of $y$ until $|x|=|y|$.

Now define a string $z$ of length $|x|$ such that $z_i=max(x_i,y_i)$ for every $1\le i\le |x|$.

Find the lexicographically smallest possible string $z$.

$n\le 400$ immediately made my ears perk up. I love problems with cubic solutions (despite this filter being so wide and ambiguous) in a stupid and superficial manner, like a dog loves bones whether they be real or made from rubber. Problems with low constraints feel more approachable to me at the outset, because it's more natural to think of naive solutions for them first, and then gradually climb the optimizational ladder.

I considered a naive strategy: let's build $x$ and $y$ by iterating over $s$ from left to right. At every $i$, we choose to add $s_i$ to either $x$ or $y$.

When adding $s_i$, what decisions of the past matter? WLOG assume before adding this character (in the case where the two lengths are equal, we can add the character to either of the two strings without worsening our state). We notice that the first $|y|$ characters of $z$ have already been fixed by now, and we have two options:

• Add $s_i$ to $x$, further increasing the "overhang" of $x$ over $y$.
• Add $s_i$ to $y$, fixing the $|y|$-character of $z$.

I now considered the simplest DP I could think of: define $f(a,b)$ (assume $a\ge b$) to be the lexicographically smallest possible $z$ we can obtain from partitioning the first $a+b$ characters of $s$ into subsequences of length $a$ and $b$.

Somewhere in the background, my teammates got another WA on C.

How do we perform transitions? From $f(a,b-1)$ and $f(a-1,b)$ to $f(a,b)$?... wait, what? This had just $O(n^2)$ transitions, with each one taking $O(n)$ time, making the DP already fast enough. Surely, the problem was gaslighting me? There's no way something that easy could have just one solve 3.5 hours into the contest... right? I looked at my states and transitions more carefully with some unease. The $f(a-1,b)\to f(a,b)$ transition was straightforward enough, and so was the... oh wait. $f(a,b-1)\to f(a,b)$ was strange.

When placing $s_i$ into $y$, the $b$-th character of $z$ would get fixed to $max(x_b,s_i)$. Let's say we have $s_i=$ 'z'. We would have previously (for the state $f(a,b-1)$) made some decisions that minimized $z$. In other words, we would have minimized the suffix $x[b,a]$ after minimizing the fixed prefix of $z$ of length $b-1$. This implied that we would previously have accepted any "sacrifices" in minimizing $x[b+1,a]$ to be able to minimize $x_b$. But if $z_b$ was now being fixed to $max(x_b,s_i)=max(x_b,\text{'z'})=\text{'z'}$, $x_b$ was irrelevant, and we could have "made sacrifices" w.r.t. $x_b$ in $f(a,b-1)$ to be able to further minimize $x[b+1,a]$. All of a sudden, my previous assumptions felt comically untrue.

This was confirmed by considering the string "aabaab". Here, the state $f(4,1)$ should be "aaba" with $x=$ "aaba" and y = "a". However, transitioning from this $(x,y)$ isn't optimal when going to $f(4,2)$, as it would result in $x=$ "aaba" and $y=$ "ab", leading to $z=$ "abba". Instead, if we had stored information for the state $x=$ "abaa" and $y=$ "a", it would have led to a suboptimal $z=$ "abaa" for $f(4,1)$, but would allow us to have $x=$ "abaa" and $y=$ "ab", leading to a more optimal $z$ = "abaa". However, I noticed that even the true values for these incorrectly computed states seemed to lead to strictly less optimal states than the true optimum (for the examples I worked out on paper)... Could it be possible that this was always true?

The conjecture was true after all!

Feeling slightly giddy with excitement, I informed my teammates that I might have solved H, in as modestly unoptimistic a manner as I could. I did not want to get their hopes up, in the likely case that something had gone terribly wrong in the last 25 minutes of breathless analysis. This caution was probably unwarranted, as they didn't exactly respond in the most enthusiastic manner (my antics in the past have conditioned them to not get their hopes up at me claiming to have solved a hard problem, better than any effort on my part could).

The issues in GeometryDashAddict's solution to C still hadn't been resolved, and it increasingly seemed like it had a logical mistake, so I took over the PC. 5 minutes and 20 lines of code later, I was... done? Despite being almost certain that the DP was correct, I took pause. The problem still remained at a single solve. This was surely a grand, elaborate ruse to gaslight me, with all the organizers and participants involved, right? Perhaps my teammates were in on it too? HOW THE FUCK WAS H STILL AT ONE SOLVE?

My teammates had been almost entirely unaware of what I had been up to for the last 30 minutes, with C taking up all of their attention. I had similarly been oblivious to their presence, and consequently forgot to inform them of my upcoming submission for H. At 1:40 PM, I pasted my code into the IDE, glared at it with suspicion for a few seconds, and hit "Submit". The first thought that rushed through my mind as the screen went green almost anti-climactically fast, was the fact that I had just made it possible for us to finish the contest without a solve on B and C, but with one on the ostensibly harder H.

In what GrokSponsoredPS5 later described as a stereotypical scene depicting a twist in the plot of a movie, I tapped him on the back, and just pointed at the screen. For a moment, he seemed to think that I was showing him an AC on one of the three problems we had previously solved. As I pointed to the title of the page, a bewildered smile formed on his face. Where there had previously been vague, intangible delusions about qualification, there was now a terribly real path forward, and very little time to traverse it. In the potential aftermath of failing to do so, there would also be an abundance of a previously unknown flavour of self-hatred to flagellate myself with.

Once again, our rank barely changed due to several teams having solves on A, E, and 2 of {B, C, D}. Feeling a bit frustrated with the delay on C, I asked my teammates if they wanted me to examine their solution, with the hope that I wouldn't also be led astray by any blind spots they may have developed out of familiarity. GeometryDashAddict agreed, so I quickly read the problem again.

The statement was as follows:

There are $n$ $(1\le n\le 2\cdot {10}^5)$ hidden operation variables $o{p}_1,o{p}_2,\dots ,o{p}_n$.

Each of them is one of three bitwise operators: , $|$, or $\oplus$, representing bitwise AND, OR, and XOR, respectively.

You are also given $m$ $(1\le m\le 2\cdot {10}^5)$ equations. The $i$-th equation is: $$a_{i}o{p}_{l_i}{b}_i=c_{i}o{p}_{r_i}{d}_i$$ where all values $a_i,b_i,c_i,d_i$ are bits (each is either $0$ or $1$).

Determine whether it is possible to assign an operator to every $o{p}_i$ so that all $m$ equations are satisfied. If there are multiple valid assignments, output any of them.

GeometryDashAddict's solution, as I imagine every solution for this problem to be, involved casework that enforced pairwise constraints between $o{p}_{l_i}$ and $o{p}_{r_i}$ for some $i$ and just fixed the values of $o{p}_{l_i}$ and $o{p}_{r_i}$ for others. Once these constraints were in place, he used BFS to propagate values without ambiguity.

The only part of the solution with any potential for errors seemed to be the casework for enforcing pairwise constraints.

We first normalized every equation by sorting the operands on each side lexicographically (bitwise operators are commutative), and then swapped the sides and operators themselves if it made the equation lexicographically smaller. After this, we initialized all operators with value $|$ and then did the following casework for every equation:

• If the operand set on the LHS and the RHS are equal, then do not enforce any constraints.
• Otherwise, do the following

• Any operand that isn't touched after we propagate changes from the fixed values can be safely left with value $|$.

An observant reader will immediately protest after having read this, and so did I to GeometryDashAddict. They had indeed developed a blind spot out of familiarity. The casework for unequal operand sets was fine, but one couldn't just ignore the equations for all equal operand sets!

It seemed like $\{0,0\}$ had poisoned the well here, as it's the first set of operands one considers when going in lexicographical order, and when the LHS and RHS were both equal to this set, one could indeed ignore the equation. However, this wasn't the case for $\{0,1\}$ and $\{1,1\}$.

I quickly explained the case where both LHS and RHS had operands $\{1,1\}$. Here, we could not have $o{p}_{l_i}=\oplus$ and $o{p}_{r_i}=|$, so there were some structural restrictions after all. After some discussion, we reduced the restrictions to the following constraints:

Suddenly, the problem felt far uglier than the impression their previous solution, with its simple propagation logic, had given us. These new constraints were of a different kind than the previous ones. GeometryDashAddict wondered if we could just patch his solution by handling these new constraints in the same way as the previous ones, but for some reason, I felt that this would introduce ambiguity to the previously deterministic propagation logic. GeometryDashAddict asked why I felt this way, and I gave the example of constraint . If we arrived at $o{p}_{l_i}$ with , there was ambiguity in whether it was optimal to set $o{p}_{r_i}$ to $|$ or $\oplus$.

It was clear that the problem was provably (one could say trivially) solvable through 2-sat, but implementing this from scratch seemed like a grossly indulgent misuse of the little time that remained. I thought about alternatives that would bypass the need for fully general 2-sat, but came up with nothing. With my hopeful excitement after the solve on H suddenly deflating at the realization that we were going to spend the last hour on C alone, I asked GrokSponsoredPS5 to implement code for finding SCCs as quickly as he could.

Just as he was about to begin, GeometryDashAddict interrupted us. The operator $|$ was special. All of our constraints were of the form $(a=o{p}_1⟺b=o{p}_2)$ with $o{p}_1,o{p}_2\ne |$, and ambiguity only arose when $a\ne o{p}_1$. But in such cases, we could always leave $o{p}_2=|$ as (a) it didn't set up further implications ($o{p}_1\ne |$) and (b) it could be overwritten further down the line by another implication. This was in fact the reason that propagation in the initial solution had worked, and I had overlooked this detail in the heat of the moment.

GeometryDashAddict began frantically patching his old code as the timer ticked down to 60 minutes. When the scoreboard froze, we were at the 22nd position with 4 solves. 6 teams had solved 6 problems by now, but more importantly, 16 teams had >= 5 solves. Even if we were to solve C the very next second, our egregious penalty would ensure that we landed outside the top-15 (which was where the cutoff for qualification had been in the previous years).

B coyly beckoned to me. It was the 4th most solved problem by now, was this of all problems going to be the nail in the coffin of my ICPC career? The one that would engender a traumatized hatred for all graph problems for the rest of my life?

While I pondered upon this, some blessed part of me was hard at work in the background, pattern-matching onto previously seen problems, and suddenly presented me with this one.

In particular, it involved the following subproblem:

Given a DAG $G(V,E)$, find the smallest number of vertex-disjoint paths one can decompose $G$ into, such that every vertex is a part of some path.

Being rather weak at flows, I had been pleasantly surprised when I realized the admittedly simple solution to this problem: build a bipartite graph with partitions $L,R$ where $L=\{v_{out}:v\in V\}$, $R=\{v_{in}:v\in V\}$ and edges $\{(u_{out},v_{in}):(u,v)\in E\}$. The answer is equal to the size of the maximum matching on this bipartite graph.

WHAT. THE. FUCK.

The pain barely registered as I slapped myself across the face hard.

Even as my heartbeat rose with the knowledge of what this meant, I hesitated in allowing myself to admit that I had solved the problem, as it would require me to admit the embarrassing simplicity of the solution, and the fact that I had made no progress for so long.

We first build the exact auxiliary bipartite graph defined earlier from our DAG. And then we just... find the minimum vertex cover.

Performing an operation on $u$ that deletes outgoing edges is equivalent to selecting the vertex $u_{out}$ in the bipartite graph, and performing one that deletes incoming edges is equivalent to selecting $u_{in}$. The objective in the problem (deleting edges) is clearly equivalent to that of vertex cover.

I pulled GrokSponsoredPS5 over and explained the solution to him. His eyes lit up as he nodded along. There was no way this was actually happening. Where was the caveat? The one thing that went wrong at the very last moment?

I wondered if it would be C, as GeometryDashAddict submitted his code at 2:15 PM, to be met with a... why was the spinner in the UI still spinning? As a few seconds passed, our disappointed expectation of a TLE turned into a more hopeful annoyance. We had encountered a CodeChef bug at the-regional-that-shall-not-be-named where the spinner kept spinning regardless of the result. The actual result could be confirmed by looking at the top left of the scre- GrokSponsoredPS5 exclaimed with joy a little too loudly. AC. The PC was quickly freed for me.

I began typing out Hopcroft-Karp from our team notebook with shaking hands. Suddenly, it was our contest to somehow throw away in the hour that remained. In what was a comical overcorrection to ensure the absence of any more fuck-ups, I asked GrokSponsoredPS5 to explain the solution to GeometryDashAddict and have him mentally verify it too, and for GrokSponsoredPS5 to then examine my code line-by-line as I typed.

With my body occupied with the trivial task of copying the code, my mind began to think of creative ways in which things could still go wrong.

We had made very few changes to the team notebook since last year, and the flows code hadn't been touched at all. This was mostly because of the fact that WellGroomedHair had laboriously reduced the size of all our code by formatting it manually, and I had been too lazy to do the same for the templates I had updated since then.

For instance, he had reduced my code for bipartite flows from this:

class bipartite_chan
{
    /*
        tc: O(E sqrt(V))
        mc: O(V + E)

        vars:
            n, m: size of left and right partitions
            adj: left to right edges ONLY
        info:
            Both partitions are individually 0 indexed
            After calling max_matching():
                - matching = size of max matching
                - l[u] = matched right node for u (l[u] = -1 => unmatched)
                - r[u] = matched left node for u (r[u] = -1 => unmatched)
            MVC is found by:
                - orienting matched edges from right to left, unmatched opposite
                - running dfs from all unmatched left side nodes
                - (unvis nodes on the left) + (visited nodes on right) = mvc
            MIS is complement of MVC
    */
public:
    int n, m;
    int matching = 0;
    vector<vector<int>> adj;
    vector<int> l, r, lvl;
    bipartite_chan(int n, int m, const vector<vector<int>> &adj) : 
        n(n), m(m), l(n, -1), r(m, -1), adj(adj) {};

    // void Add(int u, int v)  { adj[u].push_back(v); }
    bool dfs(int u)
    {
        int t = exchange(lvl[u], -1) + 1;
        for (int v : adj[u])
            if (r[v] == -1 or (lvl[r[v]] == t and dfs(r[v])))
                return l[u] = v, r[v] = u, 1;
        return 0;
    }

    int max_matching()
    {
        matching = 0;   
        vector<int> q(n);
        for (int s = 0, t = 0;; s = t = 0)
        {
            lvl = vector<int>(n);   bool f = 0;
            for(int i = 0; i < n; i ++) 
                if (l[i] == -1) 
                    lvl[i] = 1, q[t ++] = i;

            while (s < t)
            {
                int u = q[ s++];
                for (int v : adj[u])
                {
                    int x = r[v];
                    if (x == -1)
                        f = 1;
                    else if (!lvl[x])
                        lvl[x] = lvl[u] + 1, q[t++] = x;
                }
            }

            if (!f)
                break;

            for(int i = 0; i < n; i ++) 
                if (l[i] == -1) 
                    matching += dfs(i);
        }
        return matching;
    }

    vector<pair<int, int>> max_matching_edges()
    {
        vector<pair<int, int>> mme;
        for(int u = 0; u < n; u ++)
            if(l[u] != -1)
                mme.push_back(make_pair(u, l[u]));
        return mme;
    }

    pair<vector<int>, vector<int>> min_vertex_cover()
    {
        vector<bool> lv(n, false), rv(m, false);

        auto dfs = [&](int u, auto &&dfs) -> void
        {
            lv[u] = true;
            for(auto v : adj[u])
                if(r[v] != u and !rv[v])
                {
                    rv[v] = true;
                    if(r[v] != -1 and !lv[r[v]])
                        dfs(r[v], dfs);
                }
        };
        for(int u = 0; u < n; u ++)
            if(l[u] == -1 and !lv[u])
                dfs(u, dfs);

        vector<int> lc, rc;
        for(int u = 0; u < n; u ++)
            if(!lv[u])
                lc.push_back(u);
        for(int u = 0; u < m; u ++)
            if(rv[u])
                rc.push_back(u);

        assert(matching == (int)lc.size() + (int)rc.size());
        return {lc, rc};
    }
};

to the far more compact (and less readable) form that I was currently typing:

class bipartite_chan {
/*tc: O(E sqrt(V))
  mc: O(V + E)
  vars:
    n, m: size of left and right partitions
    adj: left to right edges ONLY
  info:
    Both partitions are individually 1 indexed
    After calling max_matching():
      - matching = size of max matching
      - l[u] = matched right node for u (l[u] = -1 => unmatched)
      - r[u] = matched left node for u (r[u] = -1 => unmatched)
    MVC is found by:
      - orienting matched edges from right to left, unmatched opposite
      - running dfs from all unmatched left side nodes
      - (unvis nodes on the left) + (visited nodes on right) = mvc
    MIS is complement of MVC
*/
public:
  int n, m, matching = 0;
  vector<vector<int>> adj;
  vector<int> l, r, lvl;
  bipartite_chan(int n, int m, const vector<vector<int>> &adj) :
      n(n), m(m), l(n, -1), r(m, -1), adj(adj) {};
  // void Add(int u, int v)  { adj[u].push_back(v); }
  bool dfs(int u) {
    int t = exchange(lvl[u], -1) + 1;
    for (int v : adj[u])
      if (r[v] == -1 or (lvl[r[v]] == t and dfs(r[v])))
        return l[u] = v, r[v] = u, 1;
    return 0;
  }
  int max_matching() {
    matching = 0; vector<int> q(n);
    for (int s = 0, t = 0;; s = t = 0) {
      lvl = vector<int>(n);   bool f = 0;
      for(int i = 0; i < n; i ++)
        if (l[i] == -1)
          lvl[i] = 1, q[t ++] = i;
      while (s < t) {
        int u = q[ s++];
        for (int v : adj[u]) {
          int x = r[v];
          if (x == -1) f = 1;
          else if (!lvl[x])
            lvl[x] = lvl[u] + 1, q[t++] = x;
        }
      }
      if (!f) break;
      for(int i = 0; i < n; i ++)
        if (l[i] == -1) matching += dfs(i);
    }
    return matching;
  }
  vector<pair<int, int>> max_matching_edges() {
    vector<pair<int, int>> mme;
    for(int u = 0; u < n; u ++)
      if(l[u] != -1) mme.push_back(make_pair(u, l[u]));
    return mme;
  }
  pair<vector<int>, vector<int>> min_vertex_cover() {
    vector<bool> lv(n, false), rv(m, false);
    auto dfs = [&](int u, auto &&dfs) -> void {
      lv[u] = true;
      for(auto v : adj[u])
        if(r[v] != u and !rv[v]) {
          rv[v] = true;
          if(r[v] != -1 and !lv[r[v]]) dfs(r[v], dfs);
        }
    };
    for(int u = 0; u < n; u ++)
      if(l[u] == -1 and !lv[u]) dfs(u, dfs);
    vector<int> lc, rc;
    for(int u = 0; u < n; u ++)
      if(!lv[u]) lc.push_back(u);
    for(int u = 0; u < m; u ++)
      if(rv[u]) rc.push_back(u);
    assert(matching == (int)lc.size() + (int)rc.size ());
    return {lc, rc};
  }
};

I had already made a few typos, and subsequently corrected them as I typed the dense code out. I shuddered with dread. What if WellGroomedHair had accidentally deleted a character while formatting the code last year? All it would have taken was an accidental backspace to convert a -1 into a 1.

Some part of me hoped against hope that this had actually happened, even as another annoyingly rational part reminded me that it was highly unlikely, and in the case that it had happened, I could easily find the error in the time that remained.

My heartbeat had been doing its best to mimic the Shepard Tone as I finished implementing the code and ran it against the samples. Why was the output nonsensical? Was this the caveat from earlier? Surely, we had collectively hallucinated a laughably invalid solution in the style of an LLM?

No. There was just a stupid mistake in how I had constructed the initial DAG. I fixed this in a few seconds and ran the code against the samples, daring the outputs to be nonsensical again. They weren't. I consoled myself with the fact that the samples were trivial, and we would surely be greeted with an unresolvable WA that dashed our hopes into the ground once I actually made the submission. With all six of our eyes riveted to the screen, I pasted the code into the IDE and hit "Submit", hoping, no, praying that something had gone wrong.

AC.

The 40 minutes that remained passed by like a blur while simultaneously being the longest of my life. If these had been the first 40 minutes of the contest, we might have acquired another AC (G), but most of my attention was now captured by the awareness that with every minute that passed, other teams could rise above us by getting 6 solves with better penalty.

I idly observed the team in front of us hastily typing and debugging code in the meantime. They had also solved 6 problems, and were to remain at this tally till the end of the contest.

Time eventually ran out. As we exited the hall, I remarked that this was the first time I wasn't leaving an ICPC contest feeling depressed, and GeometryDashAddict agreed.