I hope you all enjoyed the contest!
| Predictor | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|
| AksLolCoding | 800 | 900 | 1000 | 1400 | 1500 | 1800 | 1800 | — |
| ALnQ417 | 800 | 900 | 1100 | 1300 | 1500 | 1600 | — | — |
| bookcat | 800 | 1200 | 1200 | 1500 | 1600 | 1600 | 1600 | 2000 |
| chromate00 | 800 | 800 | 1000 | 1400 | 1400 | 1800 | 1800 | 2200 |
| cry | 800 | 1000 | 1200 | 1600 | 1700 | 2100 | 2100 | 2400 |
| Edeeva | 800 | 800 | 1000 | 1300 | 1400 | 1600 | 1900 | — |
| efishel | 800 | 1000 | 1000 | 1500 | 1500 | 1800 | 1900 | 2200 |
| _Equinox | 800 | 800 | 800 | 1200 | 1500 | 1600 | 1800 | — |
| fatalerror | 800 | 1400 | 1200 | 1600 | 1700 | 1900 | 2000 | 2100 |
| -firefly- | 800 | 800 | 900 | 1400 | 1400 | 1600 | 1800 | 2500 |
| nifeshe | 800 | 800 | 1000 | 1500 | 1600 | 1800 | 1900 | 2400 |
| Non-origination | 800 | 800 | 1000 | 1600 | 1300 | 1600 | 1800 | — |
| reirugan | 800 | 900 | 1200 | 1500 | 1500 | 1800 | 1800 | — |
| temporary1 | 800 | 800 | 900 | 1400 | 1300 | 1800 | 1900 | 2200 |
| white_two | 800 | 800 | 1200 | 1400 | 1400 | 1900 | — | — |
Idea: -firefly-
Preparation: -firefly-
Analysis: temporary1
The step $$$2$$$ doesn't affect step $$$1$$$.
2131B - Чередующаяся последовательность
Idea: -firefly-
Preparation: -firefly-
Analysis: reirugan
There are no much difference between the series when $$$n=k$$$ and $$$n=k+1$$$.
Construct the series from the left to the right greedily.
Idea: Tobo
Preparation: Tobo, -firefly-, Friedrich
Analysis: Tobo
Consider the operations modulo $$$k$$$.
Idea: -firefly-
Preparation: -firefly-
Analysis: __baozii__
What is the minimum diameter achievable?
How are leaves significant?
Idea: -firefly-
Preparation: -firefly-
Analysis: __baozii__
2131F - Несправедливая бинарная жизнь
Idea: efishel, __baozii__
Preparation: -firefly-
Analysis: temporary1, reirugan
The grid possesses a significant property. Try to generate some grids with random $$$a$$$ and $$$b$$$, and understand the distribution of $0$s and $1$s.
For each point $$$(x, y)$$$, you can derive the answer formula like $$$\min(f(x,y), g(x,y))$$$. Note that $$$\displaystyle\min(f,g)=\frac{f+g}{2}-\frac{|f-g|}{2}$$$
Idea: -firefly-
Preparation: -firefly-
Analysis: __baozii__
For a set $$$S$$$, how many operations are required to transform $$$S$$$ into $$$S \setminus {\min(S)}$$$?
$$$S$$$ can be represented as a binary number (though very large).
How to calculate the answer when elements in $$$S$$$ are very large?
Idea: __baozii__, -firefly-
Preparation: -firefly-
Analysis: -firefly-
Let's consider an easier problem: how do we find one coprime pair from $$$a$$$?
If there exists one coprime pair, it means there exists an $$$i$$$ such that
In other words, there are at least one other indices $$$j$$$ such that $$$\gcd(a_i, a_j)=1$$$.
Therefore, we strengthen the problem that we need to find $$$\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1]$$$ for each $$$i$$$. Here, we introduce two ways to solve the formula.
In the following discussion, we denote $$$f(d)$$$ to be the count of elements in $$$a$$$ divisible by $$$d$$$. We can precompute $$$f(1), f(2), \dots, f(m)$$$ in $$$O(m\log m)$$$ time using harmonic trick.
For each $$$a_i$$$, find the set of distinct prime factors of $$$a_i$$$. Let's call this set $$$P_i$$$. For each prime factor $$$p_k \in P_i$$$, let $$$S_k$$$ be the set of elements in the array $$$a$$$ that are divisible by $$$p_k$$$.
Any number that is NOT coprime to $$$a_i$$$ must share at least one prime factor with $$$a_i$$$, so it must belongs to the set union $$$S_1 \cup S_2 \cup \dots \cup S_k$$$. By PIE we can calculate the size of the union:
Here:
- $$$|S_r|$$$ is the count of elements in $$$a$$$ divisible by $$$p_r$$$, which is $$$f(p_r)$$$.
- $$$|S_r \cap S_s|$$$ is the count of elements in $$$a$$$ divisible by both $$$p_r$$$ and $$$p_s$$$, that is, divisible by $$$p_rp_s$$$, which is $$$f(p_rp_s)$$$.
- Similarly, $$$|S_r \cap S_s \cap S_t|$$$ is $$$f(p_rp_sp_t)$$$.
Since $$$f(d)$$$ has been precomputed, we can compute $$$|S_1 \cup S_2 \cup \dots \cup S_k|$$$ for each $$$i$$$ in $$$O(2^{|P_i|})$$$ time. Because $$$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 9699690 \gt 10^6$$$, the size of $$$P_i$$$ won't exceed $$$7$$$. Therefore, the operation number is roughly $$$2^7 \cdot n \le 3 \cdot 10^7$$$, which is acceptable.
After finding the count of elements that is NOT coprime to $$$a_i$$$, we can then easily obtain $$$\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1]$$$ by subtraction.
Another advanced approach to find the result is Mobius inversion. We will assume that you know the definition and property of mobius function $$$\mu(n)$$$ in the following discussion.
Since we know that $$$\displaystyle[\gcd(x, y) = 1] = \sum_{d|\gcd(x, y)}\mu(d)$$$, we can expand the orginal formula as:
Let's swap the order of summation and get
Because $$$d | \gcd(a_i, a_j)$$$ is equivalent to $$$d|a_i$$$ and $$$d|a_j$$$, we can simplify the formula to
Thus, we can enumerate the divisors of $$$a_i$$$ for each $$$i$$$ and compute the summation above by brute force, which yields a $$$O(n\sqrt{m})$$$ or $$$O(nd(n))$$$ time.
Let's build a graph $$$G$$$ where vertex $$$i$$$ and $$$j$$$ has an undirected edge if and only if $$$\gcd(a_i, a_j) = 1$$$. The problem becomes finding a match of size $$$2$$$ in the graph. However, we only has each vertex's degrees based on the discussion above. How do we find the match only based on degrees?
We use a greedy approach to obtain the match of size $$$2$$$. Let's say $$$G$$$ has at least one edge.
- Choose a vertex $$$u$$$ with the maximum degree.
- From all vertices that is connected to $$$u$$$, pick a vertex $$$v$$$ with the minimum degree.
- Remove vertices $$$u$$$ and $$$v$$$ and their associated edges from $$$G$$$ to get a new graph $$$G^\prime$$$.
- If there are at least one remaining edge in $$$G^\prime$$$, $$$G$$$ has a match of size $$$2$$$ that contains $$$(u, v)$$$ and the remaining edge. Otherwise, it doesn't have a match of size $$$2$$$.
We will prove that if $$$G^\prime$$$ contains no edges, $$$G$$$ doesn't have a match of size $$$2$$$.
Because $$$G^\prime$$$ has no edge, all of the vertices that is not isolated in $$$G$$$ connect to $$$u$$$, $$$v$$$ or both. It means $$$G$$$ has only one connected component that contains more than two vertices. To make disucssion easier, we will use $$$G$$$ to refer to $$$G$$$'s major connect component. That means all of the vertices other than $$$u$$$ and $$$v$$$ have a degree of $$$1$$$ or $$$2$$$ in $$$G$$$.
- If all vertices other than $$$u$$$ and $$$v$$$ have a degree of $$$1$$$. If at least one vertex is connected to $$$u$$$, the minimum degree that $$$u$$$'s connected vertices becomes $$$1$$$. Since the algorithm choose $$$v$$$ with the minimum degree, $$$v$$$ also has a degree of $$$1$$$, so all vertices are connected to $$$u$$$. In this case, $$$G$$$ is a star-shaped tree, which doesn't have a match of size $$$2$$$ for obvious reason. On the other hand, if all vertices are connected to $$$v$$$, the degree of $$$v$$$ is greater than $$$u$$$, which is impossible become the degree of $$$u$$$ is maximum.
- If exactly one vertex other than $$$u$$$ and $$$v$$$ has a degree of $$$2$$$, it must connect to both $$$u$$$ and $$$v$$$. Similar to the discussion above, we can prove that no other vertex can be connected to either $$$u$$$ or $$$v$$$. In this case, $$$G$$$ is a three-vertex loop, or $$$K_3$$$, which doesn't have a match of size $$$2$$$.
- If more than two vertices other than $$$u$$$ and $$$v$$$ have a degree of $$$2$$$, it means $$$v$$$ has a degree of more than $$$3$$$. Let's denote a vertex that connects to both $$$u$$$ and $$$v$$$ as $$$w$$$, then $$$\mathrm{deg}(w) = 2 \lt 3 \le \mathrm{deg}(v)$$$. Because $$$w$$$ is also connected to $$$u$$$, it contradicts to the step $$$2$$$ of the algorithm.
For our problem, for each $$$i$$$, the degree is $$$\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1] - [a_i = 1]$$$. We can then brute force to find the first edge, remove it, and then try to find the second edge.
