UCPC 2025

Here’s a brief AI summary of what UCPC is:

• UCPC stands for the Union of Clubs for Programming Contests. It is one of the most prestigious collegiate algorithmic programming competitions in South Korea, hosted and organised by a coalition of university coding clubs. It is an annual summer team competition where students team up, usually in groups of three, to solve complex algorithmic and data structure problems within a set time limit. It serves as an excellent warm-up for students preparing for the regional rounds of the ICPC, and is a competition that typically consists of an online preliminary round and an on-site final round.

It was a pleasure to write a problem for this amazing contest. Although it has been almost a year, I have a little thing to talk about. But before that, let's see what my problem was like.

XOR Graph

An XOR graph with \(N\) vertices is defined as follows.

• The graph has \(N\) vertices numbered from \(0\) to \(N-1\).
• For each vertex \(i\), there are directed edges from vertex \(i\) to vertex \(i \oplus t\) and vertex \((i \oplus t)+1\).
• However, if the destination vertex exceeds \(N−1\), the edge does not exist.

Here, \(\oplus\) denotes the bitwise XOR operation.

Given the number of vertices \(N\), the starting vertex \(x\), the destination vertex \(y\), and a non-negative integer \(t\), find the minimum number of edges needed to move from vertex \(x\) to vertex \(y\).

Input

The first line of input contains four space-separated integers \(N\), \(x\), \(y\), and \(t\). (\(2 \leq N \leq 10^{18}\); \(0 \leq x, y < N\); \(x \neq y\); \(0 \leq t < 2^{20}\))

Output

Print the minimum number of edges needed to move from vertex \(x\) to vertex \(y\). If no such path exists, print \(−1\) instead.

Author's Note

So basically, this problem was originally for my personal competition rather than an official competition run by an actual, formal institution. I thought of this problem because of someone I knew; he was really obsessed with the Bitwise XOR operation and created multiple problems solely about it. I found the obsession interesting and, not lying, a little funny, which led me to create this problem.

How did I create this problem? First, I had the idea of merging Graphs and XOR operation, leading to the first edge of this problem — \(i \to i \oplus t\). Pretty straightforward, right? However, if that was the only operation, the problem would have been easy because it’s 1 iff \(y = x \oplus t\), so I added the edge \(i \to \left(i \oplus t\right) + 1\).

And for the main part, that’s it! The solution to this problem was also a complete coincidence, since I just never realised that the operations only affect a few of the least significant bits until I actually started solving that. Well, coincidences make better problems, I guess; they’re merely random ideas just merged together, and you have an interesting problem.

Also, one thing more — initially, I limited the problem to \(N = 2^{63}\) because I was reluctant to explore non–power-of-2 cases. But when I realised the problem was actually good and (therefore) submitted it to UCPC, I thought it would be more challenging to add additional cases, and intimidate them with constraints like \(10^{18}\). So, I proposed this change to the UCPC president, and fortunately, he accepted.

Behind the Scenes

Anyway, almost a year has passed, and there is one thing I wanted to mention: the figure for the first sample was wrong. There should have been an edge from \(2 \to 3\), but it was missing. Fortunately, the actual statement and judge data were correct, so it did not affect solving. The diagram was fixed for the Open Contest, but I apologise to participants in the preliminary round.

Aside from that, writing for UCPC was genuinely fun.

I still remember getting the email that the problem was selected. At first, I was mostly surprised because this problem started from an extremely unserious idea. Not exactly the type of thought that would be in a serious competition like this.

Then, at some point, I heard that a Codeforces international grandmaster, who was our tester, apparently had no idea what was going on with the problem. That was admittedly a memorable moment, as he predicted the problem would be one of the hardest in the contest (and he was indeed correct to some extent). I felt especially proud of myself because the actual solution came from almost the opposite direction. The graph looks huge, with \(N \leq 10^{18}\), which caused massive psychological damage to the contestants, but the important observation is that only a surprisingly small portion of the state space actually matters.

And apparently, the intimidation worked! One of my favourite reactions after the contest was someone saying, “J was predicted to be only P4?” (which is very easy compared to the rest of the problems). To be fair, the solve count ended up being much lower than expected. I guess people saw \(10^{18}\) and Bitwise XOR and decided life had more to offer.

Personally, the best thing about this problem is that it managed to trick so many people while staying extremely small in setup. The entire input is literally four integers. It was really easy to set this thing up.

If I had to say something I regret, honestly, not much. Maybe fixing the figure before publishing would've been a good idea.

Anyway, thanks to everyone who read, tested, solved, discussed, got baited by, or suffered through XOR Graph. And who knows, maybe there will be another interesting problem somewhere next year.