(Long blog ahead. Reader discretion advised.)

I feel we have a rather interesting WF story (note: we did the 47th finals, as the University of Maryland, as 2 people... explained below), so I figured I'd tell it.

Exposition

It actually starts way before WF, too. Our teams were decided on (some form of) merit based on an internal qualifier. My team for the regional and NAC (North America superregional) ended up as {me, Navick, mr.banana}. We did fairly well in those. However, for WF, my two teammates only had single-entry visas for the US, meaning that if they left, they couldn't come back into our country. So they couldn't really go with me...

Luckily, in such situations, ICPC lets you just replace your teammates. So we held another internal qualifier, and ended up with two new teammates — Sam (sam571128) and Ali (Kuzey). Great!

So then WF had its scheduling fiasco and was delayed until Apr 2024. This also meant that our co-coach — JeBeK — had a similar US visa issue (which wouldn't have been a problem with the original timing) and couldn't go with us. So we were down to 4 out of 5 (the 5 including our main coach) before it even began.

We did some individual practice and such far before the contest, but I suppose we weren't that motivated for the finals and didn't do that much as a team overall. However, the week or two before, we did do a more significant amount of practice and got our team dynamic ready for the contest.

That was pretty much all we could do. So now the travel begins...

Arrival

(Note: Ali has reviewed this part of the blog, and all seems fine)

Getting into Cairo was fine. The airport was a bit confusing, but on my end, I suppose it all worked out. However, when trying to get our (on arrival) visas, Ali was, for whatever reason, pulled out into a different room? That was strange, but at the time I figured it would just end up taking longer for him. For a sense of time, our arrival in Cairo was ~4:30am and our visa process started soon after that.

At this point I should note that Ali is Iranian (with a student/working/whatever visa in the US), and as you probably know, Iran and Egypt haven't necessarily had the best of relations (though, of course, students should not be blamed for the actions of their government). Supposedly the team from Sharif was explicitly warned not to come to WF (and indeed it seems they didn't), so if you know more about anything, feel free to weigh in. I should also note that he had to go through a special process with help from ICPC getting permission for the on-arrival visa, but he did eventually get a special letter explicitly allowing him to get one, so we had little reason to suspect that he would have trouble after that.

So as time passed, our Cairo -> Luxor flight drew near (Ali and I were on the same one). He kept giving us updates, but not much was happening and he didn't particularly know what was going on. It became clear that he wouldn't make our flight, so I opted to pick up his checked bag in Luxor and we'd reconvene at the airport or at the hotel if necessary.

So I got to Luxor, and waited for his bag, and... it never came out. I guess that in itself wasn't so unusual, because someone from Georgia Tech (WF47) had the same issue, and it turned out his bag just went through a customs check so it ended up somewhere else. But then the day went on and Ali seemingly got no closer to being done with that process.

Then, around 1:15pm, after some hours of silence and confusion, Ali messaged us saying he would be under lockdown. We (including him) did not know why, or for how long, or what would result from it, or anything. At that point I invited our coach into the group to talk to him, who was actively trying to get ICPC to help. There wasn't much else Sam or I could do, so we just had to let it play out.

4 hours later, Ali told us that the officers said he should go back to the US. That was quite a shame, but in our position there was nothing that any of us could do about it. ICPC did seemingly try, but probably didn't have the authority to help. At that point, he had been at the airport with them for over 12 hours, which could not have been a fun process to go through. However, we supposed that was it, and that he would be forced back to the US, and we would all have to make do.

But then the next day happened, and Sam noticed in the morning (about 10:30am) that Ali hadn't been "online" on Telegram since 6pm the previous day. That in isolation was maybe not strange, but given the rest of the circumstances, was a bit concerning. So we messaged then and didn't get anything back. Not much we could do, so we just went on with the scheduled ICPC events. We checked back again at 8pm after the day was over, and that time we heard from our co-coach that Ali was still under lockdown...

I'm not sure exactly what happened to him, and I don't think he was ever told why, but it turns out they had just kept him there for a day and a half. I'm not sure if it was because there was no immediate flight back, or what, but that seems very awful regardless.

At 11:30pm that day, we heard back from him and he said he was more free, but was still required to return to the US. I suppose he didn't have his phone that whole time, either.

We checked back at night the next day, and he had indeed safely made it back to the US. I supposed that was it for him, and that couldn't have been a fun process at all, especially since it all ended up being for nothing. But, Sam and I still had a contest in front of us, and we were now down to two members...

Pre-contest

Before going to Egypt, we did the odd-numbered WFs for practice, and placed 12th, 36th, and 14th in 2019, 2017, and 2015 respectively. Given that those finals were a while ago, that meant that our chances of getting a medal (top 12) were definitely not the best. Especially since we only had 2 people now, that was probably not reasonable to hope for.

However, in each of our practices, we were easily capable of getting a first solve on at least one of the problems we solved. Given that I was the speed powerhouse and we still had me, that was probably our best chance to win something. So we decided to aim specifically for a first solve. And that meant we had to go for a completely different strategy than teams aiming for medals would do.

Going for a first solve, penalty is completely irrelevant, and you no longer want to start with the easiest possible problems (since first solves on the easier problems have a lot more variance). Instead, we aimed to find a problem that would not be solved early, but would still be feasible to do in a reasonable amount of time (so that some top team couldn't beat us to it).

We went for the following strategy: Sam would start by setting up all the computer stuff (getting us into the system, preparing VSCode, typing out an initial template, setting up compilation, disabling that stupid middle click -> paste binding, etc.), and I would skim the whole problemset for a problem to commit to. I would look for a problem that seemed to be far from the easiest problems, but still feasible for me to solve. And while I solved that one, Sam would work on the easier ones to try to catch us up after the (potential) first solve.

I looked through the past WFs we did and practiced skimming to gain some intuition for when each problem would be expected to be solved. I'm not sure if that helped much, but probably at least a little. Some more practice with the skimming would have helped a lot probably, but we didn't have enough time to do it really well, given that we only knew we would need this strategy a couple of days before the contest.

The dress rehearsal was a decent test of this strategy. In that case it seemed not bad, since we got "first accept" on the dress rehearsal contest because I was able to skim and find a problem that was code-able in under a minute. But that contest was much easier, and not the real thing. And there was still some luck involved and such, so we could just hope it would go well...

The contest

Spoilers ahead. If you plan to VC either WF later, probably skip this part (to "General reflection").

So the contest day comes. I find it very cool that we spend an hour right before it just sitting in a room waiting for the other teams to come and to go to the contest venue. But I guess that's inevitable. When the clock timewarped down to a minute before start, we were very eager (perhaps hyperactive) to get going.

For reference, here is the problemset, if you want to see it.

Once the contest did start, we got right to our strategy. I looked through all the problems, eliminating the ones that "looked easy" and also the ones that looked completely unapproachable or seemed like other teams would have a lot easier time with it than me.

I won't go into detail about the process for each problem (since it was rather subjective and a lot of snap decisions were made), but that left me with B and K. B seemed like teams would rather try it first over K (which turned out to be true), and K definitely fit the mold of "far from the easiest problems" (being an "optimal strategy EV" problem), so I decided to commit to it. It also looked fairly doable but still heavy in implementation (though it turned out I initially had the wrong idea that made it seem more simple than it really was), so it seemed like a good choice.

Note that K was not present in the WF46 set. I will go into detail about our process with solving the problem for those that are curious. If you're not interested in this, just skip anything involving latex, I guess (the story makes a decent amount of sense even if you don't know what's going on with the problem; I would mostly recommend skimming this part). I'll give a brief summary of the problem too — you have $$$d$$$ $$$(d \leq 6)$$$ six-sided dice with a letter on each side, which are initially unrolled, and a set $$$S$$$ of $$$w$$$ words, each word of length $$$d$$$. In one turn, you can pick a subset of your dice and (re-)roll them, with each die landing on each side with equal chance. You win if you can arrange the letters on the top-facing sides of your dice (in any order) to form any word in $$$S$$$. Find the expected number of moves to win (as a decimal), given that you act optimally to minimize this EV.

So I got to coding it. My initial (mis)reading of the problem was simple — you would have $$$E[s]$$$, where $$$s$$$ is a "bitmask" representing the dice that have not yet been locked, and for the ones that were locked, also storing the side they landed on. Denote $$$s \subseteq t$$$ to mean that all the dice locked in $$$s$$$ are also locked in $$$t$$$, with maybe more being locked in $$$t$$$. For each possible roll $$$r$$$ of the unlocked dice in $$$s$$$ (with each possible $$$r$$$ having equal probability), you could move to any state $$$t$$$ where $$$s \subseteq t \subseteq r$$$, and your best choice for $$$r$$$ would be the minimum of these.

There are two tricky bits with this:
(1) $$$E[s]$$$ depends on $$$E[s]$$$. I did not initially realize this, and addressing it was more complicated.
(2) I initially thought that once you chose not to reroll a particular die, you could never roll it again (i.e. "locking it"). This was not implied anywhere and the statement even contradicted this assumption (though I wasn't reading it that carefully), so I'm not sure why I had this misconception. It turns out it's sometimes optimal to lock in a die $$$a$$$, but then if you get a particular roll on a different die $$$b$$$, you may want to roll $$$a$$$ again to better fit the roll you got from $$$b$$$.

Before I finished coding the initial idea, I realized (1) and had to work on it (still not realizing (2)). This took some time thinking it through, so Sam started to implement A while I was off the computer. I should note — this whole process throughout was incredibly nerve-wracking. Early into the contest, A/D/G/H/I were all solved quickly, leaving 5 problems for the top teams to chew on, so it seemed my initial guess about going for K was correct. However, I had no idea if some other team would also commit to a harder problem like K, and throughout, we were anxiously checking the scoreboard to see if anyone else ever attempted it.

It turns out (1) is not that bad to address — for each roll $$$r$$$, you have $$$E[s] = 1 + \min(E[s], f_r)$$$ where $$$f_r$$$ is the best $$$E[t]$$$ from $$$s \subseteq t \subseteq r$$$ (ignoring $$$t = s$$$ for the time being). Then, if you sort the $$$f_r$$$'s, your strategy will be to take $$$f_r$$$ for some prefix of the $$$f_r$$$'s and stick with $$$s$$$ for the remaining suffix. This strategy gives you an equation of the form $$$E[s] = 1 + pE[s] + (1 - p)x$$$ for some $$$x$$$ (the average of the chosen $$$f_r$$$'s). So if you iterate over this prefix, you can find the strategy minimizing $$$E[s]$$$.

Given that, I coded out my fix for (1), and some debugging later, it worked on all the samples but the first (which was by far the largest sample, with $$$d = 5$$$ and many words in $$$w$$$). After some confusion and a lot of staring at the code, I realized I was wrong about (2) (and luckily, the first sample did catch this, so I wasn't stuck in WA hell). This seemed very hard to fix, since with (2), $$$E[s]$$$ depends on almost every other state, creating a massive cycle of dependencies.

Near this point, A/D/G/H/I were being mowed down by the top teams, and some other problems were getting submissions (but not accepted yet), including B and J, which ended up being two of the hardest. However, there were no submissions to K at the time.

For a while, I wasn't sure what to do about (2). The fact that no team even dared to try it was a bit terrifying — did this tricky part of the problem that I didn't notice initially, make it unsolvable? Had all this time been burned for nothing?

While I was thinking about this and weathering my existential crisis, Sam took the computer and submitted A, getting a WA, which is why we had that failed submission in the middle of our K solve. At some point, I resigned to testing out some bullshit for K. Let $$$A_1$$$ be the algorithm that computes the EV's of each state only taking (1) into account, and $$$A_2$$$ being the algorithm incorporating both (1) and (2) (where if you cyclically reach a state not yet computed, you take its value from $$$A_1$$$). What I had hoped would work was to run $$$A_1$$$ as an "approximation" for the EV's, then run $$$A_2$$$ in order of $$$A_1$$$'s EV's with the idea that the cyclicity would matter less with that ordering. This did help — the answer to the sample was ~$$$9.6$$$, $$$A_1$$$'s answer was ~$$$10.1$$$, and $$$A_1 + A_2$$$ got around $$$9.7$$$. This was good, but not enough.

After that, I wasn't sure what to do for a few minutes... long, terrifying minutes. But later on, I formalized the idea of $$$A_1 + A_2$$$ doing better — if you process the states in increasing order of EV's, since you'll never jump to a state with higher EV (you would just rather stay at your current state), the whole cyclicity thing doesn't matter (you can assume that any state not computed yet is worse), and you can run an instance of $$$A_2$$$ fairly easily. And then I also realized — $$$A_1 + A_2$$$ is a better approximation than $$$A_1$$$. So if we run $$$A_1 + A_2$$$, then $$$A_2$$$ again in the order of $$$A_1 + A_2$$$'s EV's, we would get an even better answer. And thus came a new algorithm — $$$A_1 + kA_2$$$, for some number of iterations $$$k$$$ of running $$$A_2$$$.

Initially, I set $$$k = 5$$$, and that gave exactly the right answer for the first sample. Great! But the TL was 10 seconds, and $$$k = 5$$$ ran close to that despite the first sample having $$$d = 5$$$ and not $$$6$$$. So I extended the first sample to a case with $$$d = 6$$$, ran it again, and it took... over a minute. Great...

(Note that the judge machines are claimed to be identical to the local machines. So the runtime on our computer was probably close to the runtime on their system, too.)

It also took a higher $$$k$$$ ($$$11$$$, I believe) to converge to the right answer for the $$$d = 6$$$ case. So this wasn't even close. But there was a lot of constant optimization that was possible to do. At this point, the top teams were close to being done with the 5 easiest problems, and C and F were first-solved close to this time, giving more of a distraction for the top teams before trying to lock onto K. In some sense, this was all very lucky that the choice I made happened to be perfect. We were still very nervous that someone would snatch the first-solve on K before we could, though.

I decided I would try to make $$$k = 15$$$ fit in the time limit, since that was a few more iterations than what worked for our sample. After a bit of work reducing a factor of $$$32$$$ in the worst part, I got the runtime down to 30 seconds (note again: the target was 10). This was better, but still not enough. After a bit more work, it was down to 25. Then 20. Then 17. I changed the types from long double to double (maybe even float would have been fine), and that got it down to 15. After that, there wasn't much I could do — pretty much the entirety of the remaining runtime came from the "sort the $$$f_r$$$'s" step from the $$$A_1$$$ part.

I tried adding a "sort only if something has changed" heuristic, but that ended up making the runtime worse (in retrospect, I did that part suboptimally and it may have actually been faster had I done it perfectly), so I quickly got rid of it. I wasn't sure what to do at that point. It was close, but just not good enough.

But then Sam realized that he hadn't added -O2 to our compilation command, meaning it may have been running a lot slower than expected. That also made us remember that pragmas existed, so we added those, too. After that...

...1.5 seconds?!? I didn't believe that number, so I ran it a couple more times to be sure. And sure enough, that was a 10x speedup. So I guess that just worked... really well. I boosted the number of iterations up by 5x and just submitted it. And the first submission...

...TLE. Fine. I didn't question it at the time. So I halved the number of iterations and sent it in again (remember, penalty is not relevant, so I was allowed to be stupid like this). And that second attempt...

...well, ICPC posted a video of our desk's camera at the moment of getting AC. I think that reaction speaks for itself.

Contest reflection

At that point, nobody had even submitted K before us. So our TLE was the first attempt on the problem, and our AC was definitely the first AC (the next AC came 64 minutes after ours). So in many senses, the decision to go for K was perfect — if not for us, it would have been the 9th problem to be solved (only before E and J, where J got two solves across both 46 and 47 and E was unsolved entirely), and yet, it was still feasible for me to solve. It was definitely lucky too — I had no confidence that $$$A_1 + kA_2$$$ would actually pan out into an AC solution, but with the speedup from the pragmas, it was more than enough.

(Side note — it's not hard to prove that $$$A_1 + kA_2$$$ will be correct as $$$k \to \infty$$$: for each $$$A_2$$$ iteration, at the very least, the incorrect value with the smallest true EV will be correctly computed each iteration. However, I have no justification for the fact that $$$k = 40$$$ (our final choice for $$$k$$$) was enough. The official solution claims that this process is provably fast enough, but also offers a certainly fast enough Dijkstra-like idea that also uses the idea that you never jump to a larger EV and makes a lot more sense lol)

(Side note 2 — I did think about doing something like Dijkstra, but it didn't seem in my head like it would work out that well [though, given the formula I had, it would have actually been very easy to compute], which is a shame. That idea plays kinda similar to 1693C - Keshi ищет AmShZ, which I solved in 22 minutes, so I'm not sure why I didn't think it through more. I guess, if $$$A_1 + kA_2$$$ had no chance of working, I probably would have eventually converged to that idea, since it is something I've thought of before. But we still got the first solve by far anyway, so, whatever, not a big deal.)

After that, not much really happened. I took a few minutes away from the desk to unwind from that adrenaline, but I think I was worrying about this contest a lot more than I should have been, and after "accomplishing our goal", my brain kinda felt done and stopped contributing anything meaningful. So after that point, I was still trying to solve stuff, but kinda on autopilot and my brain had sorta given up already (especially since our medal chances were basically zero at that point). So poor Sam was basically alone after that. And thus, the rest of our performance was not that good.

If I had known that I would be in that state for the whole rest of the contest, I would have just gone for one of the other unsolved problems (B/E/J at the time). But I didn't know that, so I didn't try doing that either. Oh well. So that was our WF experience.

Here's the scoreboard — you'll find us very far at the bottom with a dark green lol

General reflection

I should note, ICPC offers $1200 per team per first solve. Obviously, that will be split three ways, as originally intended.

It's a serious shame that Ali couldn't make it in, and especially so that he had such an experience just trying to get into the country. If ICPC had warned Sharif to not come, and they knew Ali would have some issues (because he got their help with the visa on arrival), I'm not sure why they didn't warn Ali in the same way. I'm not particularly concerned about the factor of our "losing a team member for WF", as his personal experience was much much worse than that. Though, at least we all get some money out of it :/

I don't think I'll say much about the rest of the WF experience. For very specific me-related reasons, the environment was very not enjoyable for me. However, meeting many people who were previously just online friends/acquaintances was rather cool. I won't list out names, but you know who you are :)

Many people also wanted pictures. If you got one and wanted to share it with me, I'd be happy to see them too. As for the future — our team for WF24 is {me, Sam, Shayan}. We still have NAC to get through, but hopefully that'll be fine. I may or may not also be a (co-)coach for ICPC 2025 and maybe longer, so if you wanted to see me somehow, there would maybe still be a few more years to do so.

And here are some extra photos:

(me with the first-solve balloon)

(and with the plaque)

(and an extra video of the balloon in a half-deflated state dancing on the bed [which it did for hours])

Our coach mentioned as a joke that we may have had the worst rank out of any team with a first solve. I looked more into this — this was true for all the years after 2016. But in the 2016 finals, the team that got the first accept (out of the whole contest) ended up solving only one problem (though they did attempt 4 others). Statistics are funny...

Another poetic thing — at NAC, I tried for a first solve on K but lost by 2 minutes. And this time, we did get it on K (which I didn't even think about when choosing that problem). But, NAC would have actually paid more for it >:(

As a final note, I'm curious if our shenanigans with K ended up increasing its solve count among the top teams. I figure, since we did so incredibly bad after getting K, there could have been thoughts like "if these guys, with two solves at the 4 hour mark, can solve this problem, surely we can too". If anyone from the top teams wants to weigh in on that, feel free to :)