Greetings of peace, Codeforces!

I'd like to invite you to the mirror of the UP ACM Algolympics 2024 Final Round. Algolympics is an annual contest organized by the Association for Computing Machinery, University of the Philippines Diliman Chapter. It is open to teams consisting of undergraduate college students from the Philippines. This year's contest was held on April 4, 2024, and was the first on-site Algolympics since the pandemic. It was a lot of fun! And I hope the CF community has just as much fun with these problems.

Contest details: - There are 13 problems over 5 hours. - Every problem is worth 1 point. - Scoring is binary. There are no partial points. - The penalties are ICPC-style. - Click here to go to the gym contest

The problems range from easy to challenging. The problem setters are myself---Shisuko---PPTGamer, alltootechnical, and Josh Quinto (1NCID3R) and some of his colleagues in Samsung Research. Thanks to MikeMirzayanov for Codeforces and Polygon!

Perhaps I might be blind, but if this was some sort of flag, I can't find it on Polygon.

Specifically, I want something like this: https://codeforces.net/gym/373765/problem/B where the only allowed "language" is ZIP.

I also have other concerns like how to write the checker/do scoring for it. Does anyone have a guide for how to go about this?

Many thanks in advance.

Hello all! I have another contest to share with you all.

Abakoda was an initiative by NOI.PH (the Philippines' olympiad) to run a series of beginner-friendly weekly contests, which ultimately culminated in a long contest. Contestants were given a little under 10 days to solve 13 problems. We have decided to share these problems with the general Codeforces community.

I feel very strongly that good beginner contests are required in order to lower the barrier to competitive programming. And I'm quite proud of the set that I ended up writing! The problems should be approachable for beginners... but that said, I think there are a handful of problems that more experienced contestants might find interesting anyway :)

The contest link is here: https://codeforces.net/gym/104146

Enjoy!

Thanks to verngutz for helping me set one of the problems, and thanks to ongyiumark and lyreloi and cerebi for helping me with testing! Art, as usual, is by my amazing friend Saji Tan.

Hello! The problems from the 2022 ICPC Asia-Manila Regionals have been uploaded to the Codeforces Gym. I'm quite happy with this set, and would like to share the problems with anyone else who might be interested :))

https://codeforces.net/gym/104118

I hope you enjoy!

Title, basically. Some other details: Two different but important facets of problem solving are a) broadening your search space in the first place and b) knowing how to "prune" and abandon ideas that lead to nowhere.

If you could help me find this, I'd really appreciate it! I've been looking for this for so long

It has to do with something like the idea shown in this meme

I think it was actually a genuinely hard problem like an F or so. Does anyone remember? My Google-fu is failing me.

In an interactive problem that I plan on setting, the interactor will have to do some nontrivial amount of work (say ~500ms). This only happens once, at the start of the interaction. On the one hand, 500ms isn't that long, but on the other hand... it's not an insignificant amount either, and could feasibly make or break whether a solution is AC or TLE.

Does anyone know how the Time Limit of interactive problems is computed on Polygon/Codeforces?

Happy Holidays to the Codeforces community! I have a new contest to share with you all.

Abakoda 2021 was an initiative by NOI.PH (the Philippines' olympiad) to run a series of beginner-friendly weekly contests, which ultimately culminated in a long contest. Contestants were given a little under 10 days to solve 15 problems. We have decided to share these problems with the general Codeforces community. We hope you find them useful and interesting!

The contest link is here: https://codeforces.net/gym/103496 EDIT: Problems are now live! Enjoy :D

The problems will be available starting 6:00 pm this Dec 27 (UTC+8), and will remain "live" in the Gym until 11:59 pm on Jan 5 (again, UTC+8). Most of the problems in the contest are standard, since the contest is targeted at beginners, but I think even experienced participants will find some of the problems interesting. As long-format, I think this contest would be educational for people up to Green or Cyan level. More experienced contestants could even treat these 15 problems as an easy ICPC set. I would even guess that an Orange could solo 93% to 100% of the problems within a 5 hour period.

Regardless, I think the problems should be relatively interesting, and I'm quite proud of my work, so please check it out :D It will be fun! I also guaranteed that all these problems are comfortably solvable using Python (though you might need to submit to PyPy or still use fast I/O for some of them). Furthermore, each problem contains custom art that I commissioned from a close friend of mine, so make sure to read all the problems to see them all!

The problem stories feature Alice, Bob, and Cindy, the same characters from my Dagitab 2021 long contest last year. Except now I'm not a broke college student, so I was able to afford art for all three of them this time!

Thank you to the wonderful testers of these problems:

• spacewalker
• Something_hacker
• verngutz

Thanks also to kevinsogo whose KompGen library was invaluable in creating the test data for all these problems. And of course, thanks to MikeMirzayanov for Codeforces and the Polygon platform.

We hope you enjoy the Abakoda 2021 Long Contest!

For almost a decade now, I've been told to avoid using += on strings in Java and Python. Because they are immutable, the += creates an entirely new string and has to copy over all the characters from the left-hand side. Thus, putting a += in a loop could have your program's complexity degrade into quadratic in some cases if you're not careful.

But then just last week, I learned that CPython actually hands string concatenation smartly! On the Custom Test tab here on Codeforces, the following code runs in just 280ms when submitted to Python 3.8.10.

s = ''
for _ in range(10**6):
    s += 'a'
print(len(s))

(In contrast, it badly TLEs when submitting to PyPy 3.7, so I suppose that's one thing Python has over PyPy, but it's not like join was too hard to do, though, anyway).

Was this a recent change? How long have I been living a lie?

Suppose I hypothetically had a problem which required, say, the periodic table of elements, or the Collins' dictionary for valid Scrabble words. Perhaps, "Given a word, determine if it can be expressed as a combination of symbols of elements," or "Given a word, determine the number of valid English words that can be formed using its letters"

So, there is still a standard input to be read. But it's certainly unreasonable to ask contestants to hard code the resources. Is it possible for me to set up the problem with these files, so that the contestants' submissions can read them using ifstream or FileReader or something?

Thanks in advance!

*EDIT: There is no edit. This is a shameless bump.

Happy New Year to the Codeforces community!

I would like to invite you all to join the mirror of the Ateneo Senior High School Programming Varsity's mid-year contest, Dagitab 2021. You will be given a little under 10 days to solve 13 problems. The problems will be available starting 9:00 am on Jan 2 (UTC+8), and the contest officially runs until 11:59 pm on Jan 11 (again, UTC+8).

EDIT: The problems are now available. Good luck!

The contest link is here: https://codeforces.net/contests/102911 *Edited this to be the correct link

Most of the problems in the contest are standard, since it is targeted at beginners, so as long-format, I think this contest would be educational for people up to Cyan level. More experienced contestants could even treat these 13 problems as an easy ICPC set, and a team of three Purples could possibly finish the entire set within the 5-hour period (I think).

I also guaranteed that all these problems are comfortably solvable using Python (though you might need to submit to PyPy or still use fast I/O for some of them).

Regardless, I think the problems should be relatively interesting, and I'm quite proud of my work, so please check it out :D It will be fun!

Thanks to my friends dsjong, jvafable, hexagonforce, daniddelrio, and csfromcs for testing the problems. Thanks also to verngutz and PPTGamer for helping me in the writing process and reading over the final problems. Thanks also to kevinsogo whose KompGen library was invaluable in creating the test data for all these problems. And of course, thanks to MikeMirzayanov for Codeforces and the Polygon platform.

The problem stories revolve around the various adventures of ProgVar students Alice, Bob, and Cindy. Here's some art of Alice that I commissioned my wonderful friend @saji_tan (https://twitter.com/saji_tan) to do for me. Three of the problems have some chibi art of Alice in them! Maybe next year I can afford art for Bob and Cindy...

We hope to see you in Dagitab 2021!

EDIT: Solution sketches are now up: https://drive.google.com/file/d/1SQ7t77s3R4A-sXJznBTT0O8zmJ0Z8SxO/view?usp=sharing

I wanted to write down a very short blog on this technique, since I've encountered it a few times but have not seen it formally discussed anywhere. Theoretically this technique shaves off a log factor from the complexity, but in practice the technique often only yields a constant factor speed-up, so it's more of a micro-optimization than anything. I think it's interesting enough to warrant discussion anyway, but that's probably the reason why this technique is niche.

Let's assume that all lowercase variables here are integers, all uppercase variables are matrices, and that computations are done modulo some large prime. We use $$$I$$$ to refer to the identity matrix and $$$0$$$ to refer to the zero matrix.

Warmup Problem: Given a square matrix $$$A$$$ and a positive integer $$$n$$$, evaluate $$$A^n$$$.

Matrices are the classic example of the fast exponentiation algorithm working not just with standard multiplication of integers, but on any object equipped with an associative binary operator.

This is usually one of the first divide-and-conquer algorithms people are taught. One way to approach this is to note that, if $$$n$$$ is even, then

So, we only need to compute $$$A^{\frac{n}{2}}$$$ once, save that value, and then square it. If $$$n$$$ is odd, then we can compute it as $$$A^n = A^{n-1}\times A$$$, since $$$n-1$$$ will be even.

Here is some pseudocode for fast exponentiation.

def fast_pow(A,n):
    if n==0:
        return I
    if n&1:
        return A*fast_pow(A,n-1)
    else:
        X = fast_pow(A,n/2)
        return X*X

This gives a runtime of $$$\mathcal{O}(\lg n)$$$ matrix multiplications needed.

Problem: Given a square matrix $$$A$$$ and a positive integer $$$n$$$, evaluate $$$I+A+A^2+\dots+A^{n-1}$$$.

We can't use the geometric formula here because $$$A-I$$$ is not necessarily going to be invertible.

However, we can also use divide-and-conquer to solve this problem. If $$$n$$$ is even, we can split the sum into two halves---the "small" half, with terms whose exponents are $$$< \frac{n}{2}$$$, and the "big" half, with terms whose exponents are $$$\geq \frac{n}{2}$$$. Then, we can factor out $$$A^{\frac{n}{2}}$$$ from the "big" terms, and notice a similarity...

To simplify things, let $$$f(n) = I+A+A^2+\dots+A^{n-1}$$$.

If $$$n$$$ is odd, then we can compute $$$f(n) = I+A(I+A+\dots+A^{n-2}) = I+A\times f(n-1)$$$, since $$$n-1$$$ will be even.

Here is some pseudocode for the fast summing.

def fast_sum(A,n):
    if n==0:
        return 0
    if n&1:
        return I+A*fast_sum(A,n-1)
    else:
        return (I+fast_pow(A,n/2))*fast_sum(A,n/2)

We just learned that we can compute $$$A^{\frac{n}{2}}$$$ in $$$\mathcal{O}(\lg n)$$$, therefore with Master Theorem (or similar analysis) we conclude that the above algorithm takes at most $$$\mathcal{O}(\lg^2 n)$$$ matrix multiplications.

Can we do better than $$$\mathcal{O}(\lg^2 n)$$$?

DP on Function Calls

Notice that fast_sum is $$$\mathcal{O}(\lg^2 n)$$$ because there are $$$\mathcal{O}(\lg n)$$$ function calls, and within each function call we need to perform an $$$\mathcal{O}(\lg n)$$$ operation (the fast exponentiation). Is it possible for us to perhaps get the value of $$$A^{\frac{n}{2}}$$$ in just $$$\mathcal{O}(1)$$$?

Try adding print(n) to the start of each function and observe which values of $$$n$$$ each function visits in each of its recursive calls. Do you notice something? If we start with the same initial $$$n$$$, then fast_pow(A,n) and fast_sum(A,n) will visit the exact same states in the exact same order! The reason why is simple---if you look at the recurrence relations derived, the transitions between states are exactly the same in both functions ($$$n \to n-1$$$ if $$$n$$$ is odd, and $$$n \to \frac{n}{2}$$$ if $$$n$$$ is even).

What does this mean? Well, in fast_sum(A,n), we need $$$A^{\frac{n}{2}}$$$ for various values of $$$n$$$. However, in fast_pow(A,n), we also need $$$A^{\frac{n}{2}}$$$ for those exact same values of $$$n$$$, and in fact we already compute all the values that we need when we call fast_pow(A,n) once.

So, instead of just discarding each $$$X = A^{\frac{n}{2}}$$$, we store those values into a lookup table. Before calling fast_sum(A,n), we first call fast_pow(A,n) in order to populate the lookup table. Then, fast_sum(A,n) now magically computes each $$$A^{\frac{n}{2}}$$$ that it needs in just $$$\mathcal{O}(1)$$$ since it is just an array lookup.

Since both functions visit the same states in the same order, it is sufficient for us to store $$$X$$$ into a simple array state, where state[s] equals $$$A^{\frac{n}{2}}$$$ in the sth recursive call.

Here is some pseudocode for this technique.

state = [None for i in range(60)]
def fast_pow(A,n,s=0):
    if n==0:
        return I
    if n&1:
        return A*fast_pow(A,n-1,s+1)
    else:
        X = fast_pow(A,n/2,s+1)
        state[s] = X
        return X*X
def fast_sum(A,n,s=0):
    if n==0:
        return 0
    if n&1:
        return I+A*fast_sum(A,n-1,s+1)
    else:
        return (I+state[s])*fast_sum(A,n/2,s+1)

fast_pow(A,n) # make sure to call fast_pow first to populate the table
print(fast_sum(A,n))

Here, fast_sum(A,n) is evaluated using only $$$\mathcal{O}(\lg n)$$$ matrix multiplications.

I am going to call the following technique "DP on Function Calls", since I can't seem to find a name for it anywhere else online, though I am sure that I am not the first one to have invented it. I also toyed with the name "Functional Cascading", to mirror the technique called "Fractional Cascading", which works on similar principles.

Sample Problems that use DP on Function Calls

Holy Smokes

I originally managed to come up with DP on Function Calls when making the model solution for this problem, which I wrote for the 2020 NOI.PH Eliminations Round. The problem can still be solved even without shaving off the extra log factor, but the time limit is tighter and you have to be much more careful with your constant factors.

Fififibobobobonacci Sequence

For this problem, my solution without DP on Function Calls takes 0.54 s, whereas with DP on Function Calls it takes 0.27 s. That seems to be a x2 constant factor speedup, which I think makes it interesting despite the technique not being strictly necessary to solve this problem :P

If you know any, please link more examples of problems that use DP on Function Calls in the comments! I am quite fond of this cute technique and I'd like to see more problems for which it is applicable.

P.S. The given "pseudocode" is (generally) valid Python, but you would want to do n>>1 or n//2 instead of n/2, so that we perform integer division. When I type n//2 in the block code, everything after the // gets highlighted red since it's being interpreted as a comment. If someone can help me fix that, it would be appreciated as well!

There are already many wonderful resources online for learning the basics to combinatorial game theory, but the intention I have for this guide in particular is to try to make them more intuitive. Why does XOR work for Nim? Why does mex produce the Grundy numbers? When it was taught to me, it was more or less just as 'magic' to memorize, but now I think I have a decent understanding of why they are true, so now that I have a grasp of the intuition behind it, I decided I should record my thoughts into a blog.

Nim games

Suppose we are playing a Nim game. As we know, Nim games usually follow this sort of template:

• There are $$$n$$$ piles of stones, and each pile contains $$$p_1, p_2, p_3, \cdots p_n$$$ stones, where each of the $$$p_i$$$ is some nonnegative integer. This collection of piles defines our game state.

• There are two players who take turns removing stones. The current turn player may remove as many stones as they wish, so long as all the stones come from the same pile. More formally, they choose a pile $$$i$$$ and a number of stones to remove $$$0 < s \leq p_i$$$, then replace $$$p_i$$$ with $$$p_i-s$$$. You cannot pass your turn doing nothing. Then, it is the other player's turn to remove stones, and so on.

• The game ends when there are no stones left on the board. The winner is the one who took the last stone; alternatively, the loser is the first one who cannot take a stone on their turn.

• The game state is called a winning state if there exists a winning strategy for it. That is, the current turn player has some series of moves such that they will always be able to win, no matter what the other player does---a checkmate, so to speak. Or, more specifically, think of when someone would say that white can mate in 5 moves. This means the game of chess will inevitably end in a checkmate in 5 moves; even if the board is not literally in a checkmate position yet, there is nothing that black can do to prevent it (assuming white plays optimally). Conversely, a game state is called a losing state if no matter what the current turn player does, their opponent has a winning strategy to eventually win.

The question then usually goes something like this: Given an initial game state $$$p_1, p_2, p_3, \cdots p_n$$$, is the first player going to win, or the second player, assuming both play perfectly? I.e., is the initial game state a winning or a losing state?

There exists a fairly standard $$$O(n)$$$ formula to solving the Nim game, though I'm not sure how many people actually know why it is true. While I am normally against memorization without proof, it is far, far easier to explain the actual strategy compared to the effort needed to prove that it works, and understanding why it works doesn't really add too much insight in the contest problems themselves, so I can see why most people don't bother with the proof. But, we are nerds, and we like knowing why the things we do work, and so here is my attempt to naturally and intuitively derive for ourselves what this magic formula is.

You can only take stones from one pile at a time, so it seems like a good idea to get some information from each pile, then find some way to compose that information together to describe the board state as a whole. It's rather mathy, but as an analogy, think about multiplicative functions---to evaluate a multiplicative function at $$$n$$$, we decompose $$$n$$$ into its prime powers, more easily evaluate the function at each prime power $$$p^k$$$, then compose the answers for each $$$p^k$$$ together to get the answer for $$$n$$$.

So, what we will do is:

• For each game state $$$g$$$, let us assign to it some integer "Nim-value" $$$G$$$ which tells us whether this is a winning state or a losing state.

• Given two game states $$$a$$$ and $$$b$$$, let $$$a+b$$$ be the game state that is simply the piles of $$$a$$$ together with the piles of $$$b$$$. If their Nim-values are $$$A$$$ and $$$B$$$ respectively, then define $$$A\oplus B$$$ to be the Nim value of the game state $$$a+b$$$. We are assuming (and hoping) that there does in fact exist some operator that allows us to compose together the Nim-values of different games together easily.

Now, let's tackle the simplest possible game---one that consists of a single pile with $$$p$$$ stones in it.

• Intuitively, since the only information that distinguishes the piles from one another is the number of stones in them, let's say that the Nim-value of a game that consists of only a single pile is $$$p$$$.

• We see that a single pile is a winning state if $$$p>0$$$, and is a losing state if $$$p=0$$$. That's something we'd like to see reflected in the Nim-values as well---a Nim-value $$$G$$$ corresponds to a winning game state when $$$G>0$$$, and corresponds to a losing game state when $$$G=0$$$.

Next step, let's find a way to compose Nim-values together with this operator $$$A \oplus B$$$. We should notice the following properties about it though:

• $$$(A \oplus B) \oplus C = A\oplus(B \oplus C)$$$, and $$$A \oplus B = B \oplus A$$$. That is to say, $$$\oplus$$$ is associative and commutative. Since we're just combining the piles together, order shouldn't really matter, so this should be apparent.

• $$$A \oplus 0 = A$$$. That is to say, the identity for this operator is 0. We obviously want this to be true since if you place an empty pile next to an existing game, you should still effectively have the same game after all.

• $$$A \oplus A = 0$$$. That is to say, the inverse of each game state is itself. Think about why this is true---suppose we have two piles that each have $$$p$$$ stones in them. The second player always has a winning strategy here, which is to just mirror the first player's move! For some generic game state $$$A$$$, note that the game state $$$A\oplus A$$$ guarantees a respective 'mirror image' for each pile; if the first player makes a move on some pile, the second player can always take the same number of stones from the 'mirror image' of that pile. Thus, the first player will always be the one to run out of moves first, therefore this is a losing state, and therefore $$$A \oplus A = 0$$$.

You'll notice that together, these properties define a commutative group over the nonnegative integers! In fact, take a look at that last property in particular, that $$$A \oplus A = 0$$$. The inverse of every element is itself, i.e. every non-zero element in the group has order 2. This is actually a huge hint because it turns out the only family of groups that have this property is the group with the set $$$\{0,1\}$$$ and the operation of addition modulo 2, or some ordered $$$n$$$-tuple of $$$\{0,1\}$$$ with the operation of addition modulo 2 done between each corresponding component (or some subset of it, up to isomorphism); aka, the logical XOR and the bitwise XOR. This claim is stated without proof.

Bingo! We have a winner. It seems our operator $$$A\oplus B$$$ is just the bitwise XOR of the two Nim-values. In fact, since XOR is just addition modulo 2, in literature, the Nim-values are usually called the Nim-sums of the game state. However most of what I gave consists of heuristics and intuitions---now that we have this operator as a candidate, let's try to formally prove that our magic formula works.

Given a game of Nim whose current game state consists of $$$n$$$ piles with $$$p_1, p_2, p_3, \cdots, p_n$$$, then the current game state is a winning state if the Nim-sum $$$p_1 \oplus p_2 \oplus p_3 \oplus \cdots \oplus p_n$$$ is non-zero, and a losing state if it is equal to zero, where $$$\oplus$$$ is the bitwise XOR operation.

1. The empty game is a losing state with Nim-sum 0. This follows from our observations earlier.

2. If the current Nim-sum is 0, then any move will make it non-zero. Recall that a move replaces $$$p_i$$$ with $$$p_i-s$$$. So, keeping in mind that the XOR-inverse of each integer is itself, that means the new Nim-sum after a move is made becomes $$$(p_1 \oplus p_2 \oplus p_3 \oplus \cdots \oplus p_n) \oplus p_i \oplus (p_i-s)$$$; we remove $$$p_i$$$ from the Nim-sum, then add in $$$p_i-s$$$. But, if the current Nim-sum was already 0, then this is just $$$p_i \oplus (p_i-s)$$$, and this is only equal to 0 when $$$p_i=p_i-s$$$. But, the rules state you have to always take at least one stone on your turn, so $$$s \neq 0$$$, and it is impossible for this new Nim-sum to still be 0.

3. If the current Nim-sum is non-zero, then there always exists a move to make it equal to 0. Suppose the current Nim-sum is $$$N>0$$$. We need to choose $$$p_i$$$ and $$$s$$$ such $$$p_i \oplus (p_i-s)=N$$$, subject to the constraint that $$$0 < s \leq p_i$$$. Consider the fact that $$$N$$$, since it is nonzero, must have a greatest significant bit, the $$$g$$$th bit. Furthermore, at least one of the piles $$$p_i$$$ will have the $$$g$$$th bit as a 1 as well; if all the piles had a 0 there, then it couldn't have been the greatest significant bit of their XORsum after all. So, we choose one such pile as our $$$p_i$$$, and we construct our $$$p_i-s$$$ as the following:

• All bits greater than the $$$g$$$th bit we keep the same as $$$p_i$$$.

• The $g$th bit is set to 0.

• All bits less than the $$$g$$$th bit we make match those of $$$N \oplus p_i$$$.

Notice that this construction is always less than $$$p_i$$$, since we know their first difference is at the $$$g$$$th bit, therefore this is a valid choice of $$$p_i-s$$$, from which we can easily recover what the $$$s$$$ should be. We can see that the $$$p_i \oplus (p_i-s) = N$$$ because

• All bits in $$$N$$$ greater than the $$$g$$$th bit were already 0 (since the $$$g$$$th bit was defined to be the greatest significant bit). Then, we know that all bits in $$$p_i \oplus (p_i-s)$$$ greater than the $g$th bit are also 0, since that was how we constructed it.

• The $$$g$$$th bit in $$$N$$$ is 1, by definition as the greatest significant bit, and the $$$g$$$th bit in $$$p_i \oplus (p_i-s)$$$ is also 1, since it is 1 in $$$p_i$$$ and 0 in $$$p_i-s$$$.

• All bits in $$$p_i \oplus (p_i-s)$$$ less than the $$$g$$$th bit are guaranteed to match that of $$$N$$$, since $$$p_i \oplus (p_i-s) = p_i \oplus (p_i \oplus N) = N$$$ in this range.

So, $$$N \oplus p_i \oplus (p_i-s) = 0$$$, and thus the new Nim-sum after the move has become 0.

The best way to convince yourself and see that this does in fact set the new Nim-sum to 0 is to write it out yourself and try it with some concrete values.

Now, with these tools in hand, we can see that:

• If the current turn player has a zero state, they have no choice but to 'disturb' it into a nonzero state.

• The next player then, given a nonzero state, always is able to 'restore' it back into a zero state.

• Thus, if the players know what they are doing, the first player is helpless if the Nim-sum is 0. The second player can always ensure that the Nim-sum is 0 if and only if it is the first player's turn. There are only a finite number of moves in a game of Nim (obvious, but you can prove it by induction, using the fact that pile sizes only get smaller). Eventually, the game ends when the last stone is taken, meaning the Nim-sum is 0. So, we know that it is the first player's turn when the game ends, thus the second player can ensure that the first player loses.

• Similarly, if the current turn player has a nonzero state, they can restore it to a zero state and pass the board over to the second player, who by our logic, must be the loser, thus the first player is the winner.

This proves our theorem, and what's nice is that it actually tells us how to construct the winning move (if one exists) for any given board state.

Extensions on NIM and Grundy Numbers

No self-respecting problem-setter would ever give just a vanilla Nim game, though, now that it has become well-known. Usually, there will be some variation on the rules somehow. Consider the following, for instance.

Say you are similarly given a game state of $$$n$$$ piles with stones $$$p_1, p_2, p_3, \cdots p_n$$$. The normal rules of Nim apply, except there is an extra move: instead of removing stones from a pile, the current turn player may choose to spend their turn adding any number of stones to a pile instead. They can add as many stones as they want, so long as, again, they are all added to the same pile. Assume this addition move may only be done a finite number of times per player.

It turns out that... this is exactly the same as normal Nim! Why? Assume that the current turn player is in a losing state, under the normal set of Nim rules. If they add $$$s$$$ stones to some pile, the other player can just spend their turn removing $$$s$$$ stones from that same pile, effectively undoing the last move, and then the losing player is back exactly where they started. A winning player, meanwhile, can just play the game like normal Nim, only deviating from the strategy to undo any additions the opposing player makes, as necessary. Since the game will still end after a finite number of moves (and this is important), the winning player can be determined the same way as with normal Nim.

Other games though are not quite as simple. A common tweak is putting a limitation on the number of stones you can get from a pile. What if there is a condition that you can only take a perfect square number of stones from a pile? What if you can take no more than half the stones in a pile?

Let us turn back to our original strategy---decompose the game state into several piles, find some property for each of the piles, then compose them again together to get the answer.

So, given only a single pile with $$$p$$$ stones, how do you know if it is a winning state or a losing state? Earlier, we simply operated on $$$p$$$, but we'll need something a bit more sophisticated here.

Let's reframe this as a directed graph. Let there be $$$p+1$$$ vertices in this graph, labelled $$$0$$$ to $$$p$$$. Each vertex corresponds to some game state, where its label indicates how many stones are in the pile at this state. Then, draw a directed edge from $$$u$$$ to $$$v$$$ if it is possible to transition from $$$u$$$ stones to $$$v$$$ with a valid move. For instance, if you may only take a square number of stones from the pile, then vertex 11 would have a directed edge to vertices 10, 7, and 2, since I could take 1, 4, or 9 stones from that pile. The terminal vertices---the ones with outdegree 0---are our loss states.

We could imagine solving this with DP then. Let the terminal vertices be, by definition, losing states. Then, if a vertex points to at least one losing state, it is a win (the current turn player takes that moves and puts the opposing player in a loss state). If a vertex only points to winning states, then it is a loss (the current turn player has no ways out). Assume there are no cycles in the graph, i.e. the game ends in a finite number of moves.

Let's take this a step further though and treat it like our Nim-values from earlier; instead of just assigning win/loss, let's assign some integer value to each vertex such that 0 is a loss and nonzero is a win. This is usually called the Grundy number, or more cutely, the Nimber of a pile. I will be using Grundy numbers because that's what I'm used to, but I think Nimber is an absolutely fantastic word.

Let $$$G(u)$$$ be the Grundy number of a pile with $$$u$$$ stones. The Grundy number of a terminal state is 0; otherwise, $$$G(u)$$$ is recursively defined as the minimum excludant of the Grundy numbers of all the states it points to. We usually write minimum excludant as mex, and it basically means "return the smallest nonnegative integer that is not in this set." Let's consider a basic example, such as the Nim game where you can only take a square number of stones from a pile. If there is a pile with 5 stones, then we can take $$$1^2=1$$$ stone and transition to a pile with 4 stones, or take $$$2^2=4$$$ stones and transition to a pile with 1 stone. So, $$$G(5)=mex(G(5-1),G(5-4))=mex(G(4),G(1))=mex(2,1)=0$$$. So, it turns out that a pile with 5 stones in it is a loss state (you can verify the values of $$$G(4)$$$ and $$$G(1)$$$ for yourself, but even without Grundy numbers, you should be able to see why 5 stones is a losing state).

How about when there are multiple piles though? Amazingly, we can apply the same strategy we did earlier for Nim, except on the Grundy numbers. The important Sprague-Grundy theorem states that these games are equivalent to playing Nim, but instead of getting the Nim-sum by taking the XOR of the piles, we take the XOR of their Grundy numbers.

Let's consider that square number Nim again. We see that the Grundy numbers for $$$0, 1, 2, 3, 4, 5, 6$$$ are $$$0, 1, 0, 1, 2, 0, 1$$$, respectively. You can verify this. Therefore, if we have a game state with piles of $$$1, 2, 3, 4, 6$$$ stones, the Nim-sum of this game is $$$G(1)\oplus G(2) \oplus G(3) \oplus G(4) \oplus G(6) = 1\oplus 0 \oplus 1 \oplus 2 \oplus 1 = 3$$$, which is non-zero, therefore the first player has a winning strategy.

Note that in our normal game of Nim, each state points to every state smaller than it (since taking any number of stones is a valid move). Therefore, $$$G(p)=p$$$, which is consistent with our results about the original Nim.

When I first learned this, I thought it was magic! But the helpful commenters over at the math subreddit helped give me this wonderful intuition. The mex function is so weird. What's that all about?

Basically, the mex function is a promise. The promise is that: if $$$G(p)=g$$$, then it means every integer from $$$0$$$ to $$$g-1$$$ is "accounted for" in the list of valid moves from $$$p$$$. Imagine that every pile in our game was transformed from having $$$p$$$ stones but with weird rules, to having $$$G(p)=g$$$ stones but with normal Nim rules. You can see that we can do this because in Nim, we can transition from a pile of size $$$p$$$ to any other pile of size less than $$$p$$$; in our transformed Grundy number world, the mex property guarantees that we can transition from our 'pile' of size $$$g$$$ to any 'pile' of size less than $$$g$$$. The mex encodes information about which states are available to us, and having access to every state from 0 to $$$g-1$$$ looks a lot like Nim. So, we use this transformed mex world to reframe our view of the directed graph---the list of states available to each state makes it analogous to a normal Nim pile, which we already know how to deal with.

However, unlike in Nim, it's possible to transition from a pile of size $$$g$$$ to a pile of size greater than $$$g$$$. Consider in the square number game earlier, if we have a pile of size 5 and we take away one stone, we end up with 4; in the transformed Grundy number world, we went from a pile of size 0 to one of size 2!

But not to worry, we already accounted for this! Remember we said that "Nim where you can add stones" is just the same as normal Nim. Suppose I started with a Grundy number of $$$g$$$, then after making a move I ended up with a larger Grundy number in the new pile. But, recall that the Grundy number of some state is the minimum excludant of all the states it can transition to; it's our promise from earlier. So, if we transition from $$$g$$$ to some larger number $$$h$$$, we have been promised that from $$$h$$$, we can visit any of the numbers from 0 to $$$h-1$$$. And, since $$$g<h$$$ we can always just transition back to $$$g$$$! Just like in our Nim-with-addition from earlier, we can always just undo any additions that the losing player might try.

Therefore, if we use Grundy numbers, Nim with any weird restrictions on the amount of stones we can take per pile can be reduced to Nim with addition, which itself can be reduced to normal Nim.

The complexity in these kinds of programming problems in contests usually then comes down to finding some efficient formula for the Grundy numbers. The Sprague-Grundy theorem is actually far more general, and says that any impartial combinatorial game is essentially Nim, due to the Grundy numbers. Why? Well, the argument in our proof would work with any graph, not just Nim-games with piles. Any game which can be represented as a DAG can also be formulated in terms of Grundy numbers, and thus Nim!

I hope this guide helped you understand where the XOR came from (the self-inverse property) and where the Grundy numbers being mex came from (mex is a promise). I was very fortunate to talk to people who gave me a better understanding of this, and I hope to share this knowledge with the community too :)

Edit: Here are some sample problems which use the idea of Nim and Grundy Numbers, in no particular order of difficulty. I know Project Euler don't like posting spoilers outside their discussion forums, but these problems are so blatantly about Game Theory that I hope it's okay.

(Non-comprehensive) Problems that use Nim and Sprague-Grundy:

https://projecteuler.net/problem=306

https://projecteuler.net/problem=310

https://projecteuler.net/problem=400

https://www.codechef.com/problems/FDIVGAME

https://onlinejudge.org/external/14/1482.pdf

https://atcoder.jp/contests/arc091/tasks/arc091_d

https://codingcompetitions.withgoogle.com/codejam/round/00000000000516b9/0000000000134cdf