Sprague-Grundy is defined as, search for "The Sprague-Grundy function of a
game" after reading how, $, $\mathbb{SG}(s')>0$, from the definition of the Sprague-Grundy function.
Thus, since $\mathbb{MT}(s'), The Sprague-Grundy function of a game ------------------------------------- ###
Definition Now, \}$ Theorem: $\mathbb{SG}( C(A,B))= \mathbb{SG}(A)\oplus \mathbb{SG}(B)$. Proof
omitted for brevity, but
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 145 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 135 |
| 7 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 132 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
A blog on the Sprague-Grundy Theorem So, I ended up making a talk on Sprague-Grundy as part of a club at my school, and thought that the denizens of codeforces would appreciate it. As follows is roughly what was on the handout, which goes over Sprague-Grundy along with the application of its theory to Nim. As this is my first blog post on Codeforces, please do let me know if there are any mistakes in formatting.
I hope you find this interesting, as writing and explaining this helped me understand how to apply it to problems. This handout was written as more math-oriented, so it may be a bit heavy. The exercises are left unsolved, as they are intended to be worked through by the reader.
If you just want to get to what the Sprague-Grundy is defined as, search for "The Sprague-Grundy function of a game" after reading how games were defined.
Way too much theory
=============================
A necessary definition of games
-------------------------------
For this talk, a game will be a two-player sequential game o...
2.
More on Sprague-Grundy: Code, Exercises, Solution outlines, Proof. This is a follow-up blog to [this talk](https://mirror.codeforces.com/blog/entry/63054)
Please let me know if there are any errors. I might not be able to reply rapidly as it is finals week for me.\
The previous post doesn't exactly explain how to actually work out the solutions to Sprague-Grundy problems, or how to code them. Within this follow-up blog, I shall attempt to explain some of my thought process on working through Sprague-Grundy and similar problems, as well as including some code.
First, some pseudo-code of calculating the Sprague-Grundy, and how to find the MEX.
<spoiler summary="Recursive Sprague-Grundy">
~~~~~
# g is defined as a game (set of games), MAX is the maximum possible Sprague-Grundy value.
define SG(g):
# Make a set of sprague-grundy values
seen = new boolean[MAX+1]
for x in g:
# It is important to also check if SG(x) fits inside of the bounds of the array,
# And to ignore it if it does not.
seen[SG(x)]=true
curr = 0
w...
someone brute forced the SG function for $k=4$, the first 20 values look like:, the function for some small values, and look for a pattern. Say someone brute
forced theSG function, Thus by the property of the MEX function that was proved, $\mathbb{SG
}(C(A,B))=M(\mathbb{SGE}(A
3.
Need Help in SG function (Game Theory) [user:nihal2001,2021-03-05] posted a [blog](https://mirror.codeforces.com/blog/entry/88374) for asking the following question:
There are $n$ stones, two players take turn to choose $x$ stones, such that $1 \leq x \leq n$ and $x \And n = 0$. The one who cannot make choose lose.
Determine who is the winner, The first one or the second?
I [proved](https://mirror.codeforces.com/blog/entry/88374?#comment-767851) that If $n$ belongs to https://oeis.org/A295897, the second player win(can be solved in $O(\log n)$).
My Question(Multiple piles version of above question):
There are $n_1, \cdots, n_m$ stones, two players take turn to choose an index $i$ and $x_i$ stones, such that $1 \leq i \leq m$, $1 \leq x_i \leq n_i$ and $x_i \And n_i = 0$. The one who cannot make choose lose.
Who will be the winner?
This turn out to compute Sprague-Grundy function for $n_1 \cdots, n_m$. The first player win if and only if $sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$
I know how to compute $sg(n)$...
Need Help in SG function (Game Theory), the winner? This turn out to compute Sprague-Grundy function for $n_1 \cdots,
n_m$. The first, I know how to compute $sg(n)$ in $O(n^2 \log n)$, but I can't give it a formula
or compute, This turn out to compute Sprague-Grundy function for $n_1 \cdots, n_m$. The
first player win if and
4.
[Tutorial] On ordinals *Acknowledgements: ChatGPT for Grammar fixing.*
In mathematics, ordinals extend the concept of counting beyond finite numbers and incorporate infinite sequences. From a graph theory perspective, you can think of ordinals as a hierarchy of "layers" or "levels" that represent different sizes and types of infinity.
## Basic Concepts
In this blog, we define ordinals as competitive graphs $\Gamma$, where a competitive graph is a directed graph in which exactly one of $(u, v)$ or $(v, u)$ is included in the edge set for every pair of distinct vertices $u$ and $v$. These graphs are characterized by the absence of loops and reversed rays, where a reversed ray refers to a sequence of vertices $v_0, v_1, v_2, \dots$ with edges $(v_1, v_0), (v_2, v_1), (v_3, v_2), \dots$.
Finite ordinals correspond to natural numbers. For instance, $0$ represents the empty graph, and $1$ denotes the graph with a single vertex. An example is provided below:
...
player has a winning strategy) if and only if its SG function is non-zero.
This completes the, ## Application in CP/OI Consider a directed graph $\Gamma$ and the SG
(Sprague-Grundy)function $f, - If $h_1 = 0$, then the SG function is $h_2$, which can be directly verified.
- If $h_1 = 1$ and, Continuing this pattern, for general values $h_1$ and $h_2$, we find that the SG
function is given, function $\sigma$ can be expressed in terms of ordinals. Specifically, the SG
function can be
5.
[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution **Edit**: I have realized that this blog has been sent quite a lot on discord servers, so I am adding a content page at the start to help organize this blog better.
## Prerequisites
Let us first define the classical knapsack, unbounded knapsack and subset sum problems.
#### Subset Sum
There are $N$ items. The $i$-th item has weight $w_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i = C$.
#### Knapsack
There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized.
#### Unbounded Knapsack
There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a **multiset** $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized.
You should know how to do both versions of knapsack in $O(NC)$ and subset sum in $O(\frac{NC}{32})$ before reading this blog.
In this blog post, I will just show some res...
$C$, remove something, otherwise add something. Let us define $can(total,l,r)$
as a dpfunction
6.
OMORI CONTEST Editorial Thank you for joining the [contest](https://mirror.codeforces.com/contestInvitation/fc8da6d6845e77adc452e754d3d84c1086148c59) 😊.
<spoiler summary="How did you find the contest?">
- Great
- Good
- Average
- Bad
- Trash
</spoiler>
<spoiler summary="Which problem is your favourite?">
- SUNNY
- AUBREY
- HERO
- KEL
- MARI
- BASIL
- OMORI
</spoiler>
#### [A. SUNNY](https://mirror.codeforces.com/gym/551481/problem/A)
<spoiler summary="Editorial">
<spoiler summary="Problem Tags">
`bijections` `dynamic-programming`
</spoiler>
<spoiler summary="Hint 1">
Try to find a bijection, meaning try to find another problem such that its solution is equivalent to the original problem but is easier to solve.
</spoiler>
<spoiler summary="Hint 2">
Try to notice what happens to the difference array of $a$ when Sunny plays a note.
</sp...
$\text{LCM}$ function. Try to find the
Tutorial of OMORI CONTEST
7.
Ask for the solution of CF1704F In the [Editorial](https://mirror.codeforces.com/blog/entry/105464), it didn't explain the SG function has a cyclic section of length $34$ **by strictly proof**. So I hope someone can help me.
And another problem : **Why the conclusion that problem-maker cannot prove can become a problem in the contest ?**
In the [Editorial](https://mirror.codeforces.com/blog/entry/105464), it didn't explain
theSG function has
8.
Codeforces Round 1010 (Div. 1, Div. 2, based on Zhili Cup 2025) Editorial Sorry for the late editorial. Our problem setters were so exhausted with the offline competition yesterday that they really need some good rest.
Despite the unexpected and unpleasant incidents that occurred, we are truly surprised and grateful that so many of you still participated in this competition! We sincerely hope you enjoyed it!
(Gratitude for all you guys from [user:Ecrade_,2025-03-16]: I felt so heartbroken when I heard about the unexpected issues, but seeing so many people in the comments comforting us, sharing thoughtful and positive messages that showed genuine empathy, and continuing to fully support our competition even after the wasted time, I was deeply moved. Thank you all! Codeforces truly embodies such a positive and uplifting community spirit!)
[problem:2082A]
<br>
Idea: [user:Ecrade_,2025-03-16]
<spoiler summary="Hint">
Do we really have to consider the problem on the whole matrix?
</spoiler>
<spoiler summary="Solution">
Let $r$ be the num...
]={0,0,0,1,1,2,2,3,3,6,8}; uint B,n4,top,pri[M],F0[M],F1[M],G0[M],G1[M],SF[M],SG
[M]; inline ull Div(const ull&n
Tutorial of Codeforces Round 1010 (Div. 1, Unrated)
Tutorial of Codeforces Round 1010 (Div. 2, Unrated)
9.
Editorial for CodeRed Prelims 2026 On behalf of the organizing team, we extend our deepest gratitude to everyone who participated in CodeRed Prelims 2026. Witnessing your dedication and fierce competitive spirit on the leaderboard validated the immense effort our team invested behind the scenes.
Our problem-setters spent countless hours crafting and balancing these challenges. We sincerely hope the problemset provided a rewarding and engaging experience for the IIIT Allahabad community and our global participants. Below, you will find the official hints, detailed editorials, and author solutions. Happy upsolving!
A: Ashutosh's Triad
----------------------
Author: [user:sigma__1,2026-04-16]
<spoiler summary="Hint 1">
The phrase "minimize the maximum salary" is a classic indicator that we should use Binary Search on the answer.
</spoiler>
<spoiler summary="Hint 2">
Since $X$ is square-free, the maximum number of distinct prime factors $m$ is very small ($m \le 15$). Think about representing each wizard's ...
"> For the `check(mid)` function in your Binary Search, you need to verify if
any $K \times K$ square
10.
Codeforces Trainings Season 2 Episode 8: Editorial [Complete problemset + tests + original presentation of solutions.](http://www.bapc.eu/problemset.zip)
[Official scoreboard](http://bapc.eu/scoreboards/bapc/), [public contest scoreboard](http://www.bapc.eu/scoreboards/public/), [used for training elsewhere](http://www.cs.ubc.ca/~acm-web/practice/2014-10-25/scores.php).
Short hints first, more detailed solutions afterwards.
### A. Avoiding the Apocalypse
(difficulty: medium-hard, [code](http://ideone.com/JQOMyq))
Maxflow in a suitably selected graph. Ford-Fulkerson is sufficient.
<hr>
The vertices of our graph need to correspond to states that one person can be in when traversing the original road network; the number of people moving in a group is then represented by flow along edges. Therefore, the most natural choice is to use vertices corresponding to states (location, time).
The rules from the problem statement say that at most $c$ people can move along an edge $e=(u->v)$ in the original at any time. That me...
maxflow), $V$ and $E$ are vertices and edges of our graph — in this case, it's
$O((N+M)SG)$. It
11.
Teamscode Spring 2023 Editorial This is the editorial for a recent contest [Teamscode](https://www.teamscode.org/). The problems are open for upsolving on [this gym](https://mirror.codeforces.com/gym/104287). Problems were prepared by [user:oursaco,2023-04-06], [user:dutin,2023-04-06], [user:thehunterjames,2023-04-06], [user:Bossologist,2023-04-06], [user:Esomer,2023-04-06], and me.
### [A. What do you do when the contest starts? Are you busy? Will you solve Bingo?](https://mirror.codeforces.com/gym/104287/problem/A)
<spoiler summary = "Editorial">
<spoiler summary = "Are you busy?">
1. WorldEnd/SukaSuka
2. Bocchi the Rock
</spoiler>
<spoiler summary = "No Sweep">
1. Thomas
</spoiler>
<spoiler summary = "Multiplication Table">
1. Lycoris Recoil
</spoiler>
<spoiler summary = "Greatest Common Multiple">
1. Bokuben
</spoiler>
<spoiler summary = "A Certain Scientific Tree Problem">
1. A Certain Scientific Railgun
</spoiler>
<spoiler summary = "Two and Three">
1. Quintessential Quintluplets...
$ from where we are. We can do this with sets and the function upper_bound(),
which has a complexity
Tutorial of Teamscode Spring 2023 Contest
12.
CodeNite 2025 Editorial Thanks for participating in the contest!
Link to access contest: [CodeNite 2025](https://mirror.codeforces.com/contestInvitation/faea095b1d894b75d7f176efbe96c6d3f5e09d7a)
[problem:644977A]
Author: [user:jay_jani_0011,2025-10-25]
<spoiler summary="Solution">
$101$
</spoiler>
<spoiler summary="Code - aryansanghi">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int a, b, c;
cin>>a>>b>>c;
cout<<101<<"\n";
}
}
~~~~~
</spoiler>
[problem:644977B]
Author: [user:aryansanghi,2025-10-25]
<spoiler summary="Hint 1">
Decompose $k$ into its prime factors, i.e. $k=p_1^{x_1}\cdot p_2^{x_2}\ldots p_r^{x_r}$. A subarray $a_l, a_{l+1},\ldots,a_r$ has $LCM$ equal to $k$ if and only if for each $i\in[1\ldots r]$, there exists $a_j, l\leq j\leq r$ such that $p_i^{x_i}$ divides $a_j$, and for no $j$ does $p_i^{x_i+1}$ divide $a_j$.
</spoiler>
<spoiler summary="Solution...
$i$? Try to write $E_{out}$ as a linear function of $E_{in}$.
13.
Invitation to Insomnia Qualifier 2022 Hello Codeforces!
Computer Club, MNNIT Allahabad, India is glad to invite you to the annual programming competition of MNNIT, INSOMNIA, which is an ACM-ICPC style team programming contest of 2.5 hours duration held on Codeforces during its annual technical fest Avishkar. The team can consist up to 3 members.
<b>Contest Details: </b>
<ol>
<li> Qualifiers: </li>
<ul>
<li> Start Time: Wednesday, November 9, 21:00 IST</li>
<li> Duration: 2.5 hours</li>
</ul>
<li> Finals: </li>
<ul>
<li> Start Time: Sunday, November 13, 12:00 IST</li>
<li> Duration: 2.5 hours</li>
</ul>
</ol>
**Top 25** global teams, and **Top 25** teams from MNNIT (based on the result of Qualifiers) will qualify to the Finals. The prize distribution for global teams is mentioned below: <br>
Teams consisting of MNNIT students only will be eligible for a seperate prize pool.
Register your team for the qualifiers here: https://forms.gle/BKsbKfoGzSxC394R8 <br>...
()); } /* Change this function for updating nodes */ int update(int f, int s
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/17/2026 12:23:58 (g1).
Desktop version, switch to mobile version.
Supported by
