Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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:

In fact, the set of natural numbers $$$\mathbb{Z}_{\ge 0}$$$, often denoted as $$$\omega$$$, can be interpreted as an ordinal: $$$\Gamma_\omega = (V, E)$$$, where $$$V = \mathbb{Z}_{\ge 0}$$$ and $$$E = \{(i, j) : i < j\}$$$. However, $$$\mathbb{Z}$$$ cannot be considered an ordinal in a similar manner, due to the presence of a reversed ray, as exemplified by the sequence of vertices $$$v_i = -i$$$.

We define $$$\alpha \le \beta$$$ if $$$\beta$$$ can be viewed as a subgraph of $$$\alpha$$$. Similarly, $$$\alpha = \beta$$$ if and only if $$$\alpha \le \beta$$$ and $$$\beta \le \alpha$$$. As is familiar, the relationship between ordinals is either $$$\alpha < \beta$$$, $$$\alpha = \beta$$$, or $$$\alpha > \beta$$$.

Proof (Maybe Mathy)

In fact, for every set $$$A$$$ of ordinals, there exists an ordinal $$$\min A$$$ in the set $$$A$$$. The proof is straightforward: one can obtain $$$\min A$$$ by taking the union of all the $$$S_\alpha$$$, where $$$\alpha \in A$$$ and $$$S$$$ is the set defined previously.

The successor of an ordinal $$$\alpha$$$ is a new graph $$$G$$$ where the vertices include all the vertices of $$$\alpha$$$ along with an additional vertex $$$v$$$. All edges $$$(w, v)$$$, where $$$w$$$ is a vertex in $$$\alpha$$$, are added. The successor of $$$\alpha$$$ is denoted as $$$\alpha^+$$$. It is evident that $$$\alpha < \alpha^+$$$. Consequently, we can define the $$$n$$$-th successor of $$$\alpha$$$, denoted as $$$\alpha + n$$$.

To understand how addition and multiplication of ordinals work, consider the following definitions: For ordinals $$$\alpha$$$ and $$$\beta$$$, $$$\alpha + \beta$$$ is the ordinal with vertices formed by the disjoint union $$$\alpha \sqcup \beta$$$ (where $$$\sqcup$$$ denotes the disjoint union of sets) and edges of three types: the edges from $$$\alpha$$$ itself, the edges from $$$\beta$$$ itself, and new edges $$$(u, v)$$$ where $$$u$$$ is a vertex of $$$\alpha$$$ and $$$v$$$ is a vertex of $$$\beta$$$. Similarly, $$$\alpha \times \beta$$$ is the ordinal with vertices formed by pairs $$$(u, v)$$$, and edges formed by pairs $$$((u, v), (u', v'))$$$, where either $$$(u, u') \in E_\alpha$$$ or $$$u = u'$$$ and $$$(v, v') \in E_\beta$$$.

It is important to note that commutativity does not hold for ordinals: $$$1 + \omega = \omega \ne \omega + 1$$$, and $$$2 \omega = \omega \ne \omega 2$$$. However, associativity does hold.

Here are some properties of ordinals:

If $$$\beta < \gamma$$$, then $$$\alpha + \beta < \alpha + \gamma$$$.
If $$$\alpha < \beta$$$, there exists a unique $$$\gamma$$$ such that $$$\alpha + \gamma = \beta$$$.
For ordinals $$$\gamma$$$ and $$$\alpha$$$, there exists a unique pair of ordinals $$$\beta$$$ and $$$\delta$$$ such that $$$\gamma = \alpha \beta + \delta$$$.
For $$$\gamma > 0$$$, there exists a unique Cantor normal form $$$\gamma = \omega^{\alpha_1} k_1 + \dots + \omega^{\alpha_n} k_n$$$, where $$$n \ge 1$$$, $$$\alpha_1 > \alpha_2 > \dots > \alpha_n$$$ are ordinals, and $$$k_1, k_2, \dots, k_n \in \mathbb{Z}_{> 0}$$$.

Application in CP/OI

Consider a directed graph $$$\Gamma$$$ and the SG (Sprague-Grundy) function $$$f$$$ defined on it. If $$$\Gamma$$$ is finite, $$$f$$$ can be easily represented as a natural number-valued function. However, when we extend the SG function to handle infinite graphs, we need to incorporate ordinals.

For instance, in problem 1149E - Election Promises, we observe that a state can have infinitely many successors. To illustrate this, consider the special case where the graph is $$$1 \to 2$$$.

If $$$h_1 = 0$$$, then the SG function is $$$h_2$$$, which can be directly verified.
If $$$h_1 = 1$$$ and $$$h_2 = 0$$$, the successors are every state $$$0 \to n$$$, where $$$n$$$ is a natural number. Consequently, the SG function for the state $$$h_1 = 1$$$ and $$$h_2 = 0$$$ is $$$\omega$$$, as $$$\omega$$$ is the smallest ordinal not included in $$$\mathbb{N}$$$.

Continuing this pattern, for general values $$$h_1$$$ and $$$h_2$$$, we find that the SG function is given by $$$\omega h_1 + h_2$$$.

More generally, for any directed graph $$$\Gamma$$$ considered as a normal directed graph game, the SG function $$$\sigma$$$ can be expressed in terms of ordinals. Specifically, the SG function can be written as

$$$ \omega^n a_n + \omega^{n-1} a_{n-1} + \dots + a_0, $$$

where the coefficients $$$a_k$$$ are given by

$$$ a_k = \sum_{\sigma(x) = k} h_x. $$$

By fundamental principles in game theory, a game is a P-position (a position from which the second player has a winning strategy) if and only if its SG function is non-zero. This completes the discussion of the problem.

An another example is 最长待机 / Longest Standby.

Translated Statement

You have a program composed of $$$n$$$ functions, where the $$$i$$$-th function has a type $$$e_i$$$ and a sequence of sub-function indices $$$Q_i = (Q_{i,1}, Q_{i,2}, \ldots, Q_{i,l_i})$$$. The sequence $$$Q_i$$$ can be empty, in which case $$$l_i = 0$$$.

The following conditions must hold for the functions: - $$$n \ge 1$$$. - For all $$$1 \le i \le n$$$, $$$e_i \in \{0, 1\}$$$. - For all $$$1 \le i \le n$$$, elements in $$$Q_i$$$ are unique and must be integers from the range $$$[i + 1, n]$$$. - For all $$$2 \le j \le n$$$, there exists exactly one $$$Q_i (1 \le i \le n)$$$ that contains $$$j$$$.

Function Call Mechanics

When calling function $$$i (1 \le i \le n)$$$, the following occurs: 1. If $$$e_i = 0$$$, set variable $$$r_i$$$ to $$$1$$$. Otherwise, a positive integer value must be input for $$$r_i$$$. 2. If $$$Q_i$$$ is empty, the program waits for $$$r_i$$$ seconds. Otherwise, it repeats the following for $$$r_i$$$ times: — Call the functions with indices $$$Q_{i,1}, Q_{i,2}, \ldots, Q_{i,l_i}$$$.

If a function of type $$$1$$$ is called multiple times, each call requires a separate input for $$$r_j$$$.

The only action consuming time is "waiting $$$r$$$ seconds"; all other operations (calling functions and inputting values) occur instantaneously.

Game Rules

Two players prepare their functions and choose one to call. They know each other's function structure and selected function.

At time $$$0$$$, both players concurrently call their selected functions. The two players can observe all input values from time $$$0$$$ to $$$t-1$$$ and adjust their inputs accordingly at time $$$t$$$, but they cannot know each other's inputs at time $$$t$$$.

The player whose function call finishes first loses; if both finish simultaneously, it results in a draw.

Both players are assumed to be perfectly intelligent. If one player can guarantee a win, the game is deemed unfair. If both cannot guarantee a win, the game is fair.

Operations

You can perform two types of operations on the program:

Given $$$k$$$, toggle $$$e_k$$$ (i.e., set $$$e_k$$$ to $$$1 - e_k$$$).
Given $$$k$$$, play a game where one player calls their function $$$k$$$.

Constraints

$$$1 \le n \le 5 \times 10^5$$$ and $$$1 \le q \le 2 \times 10^5$$$, where $$$q$$$ is the number of operations. (You can try to solve it in $$$\mathrm O(nq)$$$ time first and optimize it.)

Try to solve it yourself! :) After solving it you can understand why $$$1 + \omega \ne \omega + 1$$$.

Full text and comments »