1991A — Maximize the Last Element
Consider the parity of the position.
The answer is the maximum value of the elements at odd indices.
Proof
- Any element at an odd index can be preserved until the end.
Since each element at an odd index has an even number of elements on both sides, pairs of adjacent elements can be removed from left to right until only the element at the odd index remains. For example, if you want to keep the element at the $$$i$$$-th position, you can remove the elements at positions $$$1$$$ and $$$2$$$, $$$3$$$ and $$$4$$$, and so on, until the elements at positions $$$i-2$$$ and $$$i-1$$$ are removed. Then, continue removing elements at positions $$$i+1$$$ and $$$i+2$$$, and so on, until the elements at positions $$$n-1$$$ and $$$n$$$ are removed. Therefore, any element at an odd index can be preserved through this method.
- No element at an even index can be preserved until the end.
Since $$$n$$$ is odd, there are more elements at odd indices than at even indices. Each operation removes one element at an odd index and one element at an even index. Since there are always more elements at odd indices, the last remaining element must be at an odd index.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 105;
int t, n, a[MAX_N];
int main() {
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int max_value = 0;
for (int i = 1; i <= n; i += 2)
max_value = max(max_value, a[i]);
cout << max_value << '\n';
}
}
1991B — AND Reconstruction
Consider $$$b_{i - 1} | b_i$$$.
Let's construct an array $$$a$$$ using the formula $$$a_i = b_{i - 1} | b_i$$$ (assuming $$$b_0$$$ and $$$b_n$$$ are $$$0$$$). We then verify the condition $$$b_i = a_i \& a_{i + 1}$$$ for $$$1 \le i < n$$$. If any condition fails, then such an array $$$a$$$ does not exist.
Explanation
Using the above construction method, we get: $$$a_i \& a_{i + 1} = (b_{i - 1} | b_i) \& (b_i | b_{i + 1}) = b_i | (b_{i - 1} \& b_{i + 1})$$$
If for any $$$i$$$, $$$b_i | (b_{i - 1} \& b_{i + 1}) \neq b_i$$$, then the constructed array $$$a$$$ does not satisfy the required condition. This indicates that there exists a bit in $$$b$$$ where $$$b_{i - 1} = 1$$$, $$$b_i = 0$$$, and $$$b_{i + 1} = 1$$$, which can prove there is no solution. Proof: If $$$a_{i - 2} \& a_{i - 1} = b_{i - 1} = 1$$$, then $$$a_{i - 1} = 1$$$. Similarly, since $$$a_i \& a_{i + 1} = b_i = 1$$$, then $$$a_i = 1$$$. However, $$$a_{i - 1} \& a_i = 1 \& 1 = 1$$$, which contradicts $$$b_i = 0$$$. Therefore, this configuration is unsolvable.
This shows that our construction method can construct a valid array $$$a$$$, except in cases where the above bit configuration in $$$b$$$ makes it unsolvable.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
int n, b[MAX_N], a[MAX_N];
void solve() {
cin >> n;
for (int i = 1; i < n; i++)
cin >> b[i];
b[0] = b[n] = 0;
for (int i = 1; i <= n; i++)
a[i] = b[i - 1] | b[i];
bool valid = true;
for (int i = 1; i < n; i++)
if ((a[i] & a[i + 1]) != b[i]) {
valid = false;
break;
}
if (valid) {
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
cout << '\n';
} else
cout << -1 << endl;
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
1991C — Absolute Zero
If the array contains both odd and even elements, it is impossible to zero the array.
Is there a method to narrow the range of elements after every operation?
If the array contains both odd and even numbers, it is impossible to zero the array. This is because any operation will maintain the presence of both odd and even elements.
Otherwise, if all elements in the array are either odd or even, it is feasible to zero the array in no more than $$$31$$$ operations.
The operation strategy works by iteratively narrowing the range of all elements. Initially, the range of all elements is between $$$[0, 2^{30}]$$$. Starting from $$$x = 2^{29}$$$, we use each power of $$$2$$$ as $$$x$$$, reducing the exponent by one each time (i.e., $$$2^{29}, 2^{28}, \ldots, 2^{0}$$$). After each operation, the range of all elements is halved, narrowed down to $$$[0, x]$$$. Continuing this process, after $$$30$$$ operations, all elements will become $$$0$$$ or $$$1$$$. If all elements are $$$1$$$ after $$$30$$$ operations, perform one last operation with $$$x = 1$$$ to turn all $$$1\text{s}$$$ into $$$0\text{s}$$$.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
int n, a[MAX_N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
bool has_odd = false, has_even = false;
for (int i = 1; i <= n; i++)
if (a[i] % 2 == 1)
has_odd = true;
else
has_even = true;
if (has_even && has_odd)
cout << -1 << '\n';
else {
vector<int> operations;
for (int i = 29; i >= 0; i--)
operations.push_back(1 << i);
if (has_even)
operations.push_back(1);
cout << operations.size() << '\n';
for (int x : operations)
cout << x << ' ';
cout << '\n';
}
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
1991D — Prime XOR Coloring
We can use only $$$4$$$ colors for all $$$n$$$.
For $$$n \ge 6$$$, the minimum number of colors is always $$$4$$$.
Proof
First, we can show that the number of colors cannot be less than $$$4$$$. This is because vertices $$$1$$$, $$$3$$$, $$$4$$$, and $$$6$$$ form a clique, meaning they are all connected, so they must have different colors.
Next, we can provide a construction where the number of colors is $$$4$$$. For the $$$i$$$-th vertex, assign the color $$$i \bmod 4 + 1$$$. This ensures that any two vertices of the same color have a difference that is a multiple of $$$4$$$, so their XOR is a multiple of $$$4$$$, which is not a prime number.
For $$$n < 6$$$, the example provides the coloring for all cases:
- $$$n = 1$$$: A valid coloring is $$$[1]$$$.
- $$$n = 2$$$: A valid coloring is $$$[1, 2]$$$.
- $$$n = 3$$$: A valid coloring is $$$[1, 2, 2]$$$.
- $$$n = 4$$$: A valid coloring is $$$[1, 2, 2, 3]$$$.
- $$$n = 5$$$: A valid coloring is $$$[1, 2, 2, 3, 3]$$$.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
if (n < 6) {
if (n == 1)
cout << 1 << '\n' << "1" << '\n';
else if (n == 2)
cout << 2 << '\n' << "1 2" << '\n';
else if (n == 3)
cout << 2 << '\n' << "1 2 2" << '\n';
else if (n == 4)
cout << 3 << '\n' << "1 2 2 3" << '\n';
else if (n == 5)
cout << 3 << '\n' << "1 2 2 3 3" << '\n';
} else {
cout << 4 << '\n';
for (int i = 1; i <= n; i++)
cout << i % 4 + 1 << ' ';
cout << '\n';
}
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
1991E — Coloring Game
Determine if the graph is bipartite.
If the graph is not bipartite, Alice will win. If the graph is bipartite, Bob will win.
If the graph is not bipartite, Alice can always choose colors $$$1$$$ and $$$2$$$. According to the definition of a non-bipartite graph, Bob cannot color the graph with two colors without having two adjacent vertices of the same color.
If the graph is bipartite, it can be divided into two parts, Part $$$1$$$ and Part $$$2$$$, with no edges within each part. If the colors chosen by Alice include color $$$1$$$, Bob can paint vertices in part $$$1$$$ with color $$$1$$$. If the colors chosen by Alice include color $$$2$$$, Bob can paint vertices in part $$$2$$$ with color $$$2$$$. Once one part is completely painted, Bob can use color $$$3$$$ or continue using the original color of that part to paint the remaining vertices, ensuring no two adjacent vertices have the same color. In this way, Bob will win.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e4 + 5;
int n, m, color[MAX_N], isBipartite;
vector<int> graph[MAX_N];
void dfs(int vertex) {
for (auto neighbor: graph[vertex])
if (!color[neighbor]) {
color[neighbor] = 3 — color[vertex];
dfs(neighbor);
} else if (color[neighbor] + color[vertex] != 3)
isBipartite = 0;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
graph[i].clear();
color[i] = 0;
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
isBipartite = 1;
color[1] = 1;
dfs(1);
if (!isBipartite) {
cout << "Alice" << endl;
for (int i = 1; i <= n; i++) {
cout << 1 << ' ' << 2 << endl;
int vertex, chosenColor;
cin >> vertex >> chosenColor;
}
} else {
cout << "Bob" << endl;
vector<int> part1, part2;
for (int i = 1; i <= n; i++)
if (color[i] == 1)
part1.push_back(i);
else
part2.push_back(i);
for (int i = 1; i <= n; i++) {
int color1, color2;
cin >> color1 >> color2;
if ((color1 == 1 || color2 == 1) && part1.size()) {
cout << part1.back() << ' ' << 1 << endl;
part1.pop_back();
} else if ((color1 == 2 || color2 == 2) && part2.size()) {
cout << part2.back() << ' ' << 2 << endl;
part2.pop_back();
} else if (!part1.size()) {
int chosenColor = (color1 == 1 ? color2 : color1);
cout << part2.back() << ' ' << chosenColor << endl;
part2.pop_back();
} else {
int chosenColor = (color1 == 2 ? color2 : color1);
cout << part1.back() << ' ' << chosenColor << endl;
part1.pop_back();
}
}
}
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
1991F — Triangle Formation
Under the constraints of the problem, there exists a (small) integer $$$C$$$ such that for intervals longer than $$$C$$$, it is guaranteed to form two triangles.
If there are at least $$$45$$$ sticks, it is guaranteed to form a triangle. Proof: For any sequence of stick lengths that cannot form a triangle, we can replace it with the Fibonacci sequence. By replacing the sticks in increasing order, the sequence will remain incapable of forming a triangle. This implies that the Fibonacci sequence is one of the longest sequences that cannot form a triangle. The $$$45$$$th Fibonacci number exceeds $$$10^9$$$. Therefore, having at least $$$45$$$ sticks ensures that it is possible to form a triangle.
If there are at least $$$48$$$ sticks, it is guaranteed to form two triangles. Proof: We can first form the first triangle and remove those sticks. The remaining number of sticks is still at least $$$45$$$, which is sufficient to form the second triangle.
Therefore, only for intervals with fewer than $$$48$$$ sticks, we need to check whether it is possible to form two triangles.
First, we sort the sticks within the interval. Then we use the following algorithm to find two triangles:
Algorithm 1: Enumerate all possible sets of $$$6$$$ consecutive sticks and check if they can form two triangles.
Algorithm 2: Identify all possible sets of $$$3$$$ consecutive sticks that can form a triangle, and check if there exist two disjoint sets among them.
If neither algorithm can find two triangles, then it is impossible to form two triangles within the given interval. Proof: Consider an interval where Algorithm 1 cannot find two triangles. Suppose it is indeed possible to form two triangles; the six sticks must be non-consecutive. For any unselected sticks between the chosen sticks, if there exists a stick to its left and a stick to its right that belongs to the same triangle, we can replace the leftmost stick of this triangle with the unselected stick. Continuing this process, either the six sticks will become consecutive, or the left side will form one triangle and the right side will form another, which can be detected by Algorithm 2.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
int n, q, a[MAX_N], p[MAX_N];
bool canFormTwoTriangles(int l, int r) {
int t = 0;
for (int i = l; i <= r; i++)
p[++t] = a[i];
sort(p + 1, p + t + 1);
for (int i = 1; i <= t - 5; i++)
for (int j = i + 1; j <= i + 5; j++)
for (int k = j + 1; k <= i + 5; k++) {
int q[4], c = 0;
for (int m = i + 1; m <= i + 5; m++)
if (m != j && m != k)
q[++c] = p[m];
if (p[i] + p[j] > p[k] && q[1] + q[2] > q[3])
return true;
}
int triangleCount = 0;
for (int i = 1; i <= t - 2; i++)
if (p[i] + p[i + 1] > p[i + 2]) {
i += 2;
triangleCount++;
}
return triangleCount > 1;
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
while (q--) {
int l, r;
cin >> l >> r;
if (r — l + 1 >= 48 || canFormTwoTriangles(l, r))
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
}
1991G — Grid Reset
Perform horizontal operations only on the leftmost $$$k$$$ columns and vertical operations only on the topmost $$$k$$$ rows.
Prioritize operations that will lead to a reset.
Here is a strategy to ensure you can perform operations infinitely:
- Perform horizontal operations only on the leftmost $$$k$$$ columns and vertical operations only on the topmost $$$k$$$ rows.
- Prioritize operations that will lead to a reset. If multiple operations can cause a reset, perform any of them; if no operations can cause a reset, perform any available operation.
Proof of Correctness
For a $$$n \times m$$$ grid, we define it to be in a horizontal state if its black cells can be covered by non-overlapping $$$1 \times m$$$ rectangles without gaps. Similarly, the grid is in a vertical state if its black cells can be covered by non-overlapping $$$n \times 1$$$ rectangles without gaps.
Our strategy ensures the grid always satisfies the following properties:
- The $$$k \times k$$$ region in the top-left corner, the $$$(n-k) \times k$$$ region in the bottom-left corner, and the $$$k \times (m-k)$$$ region in the top-right corner are either in a horizontal state, vertical state, or both.
- The top-left and bottom-left regions cannot both be purely in a vertical state; similarly, the top-left and top-right regions cannot both be purely in a horizontal state.
We will prove two points: first, when these properties are satisfied, there is always a valid operation; second, after performing operations according to our strategy, the grid still satisfies these properties.
Existence of Valid Operations
Assume the current operation is horizontal (the proof for vertical operations is similar). If the top-left and bottom-left regions cannot perform a horizontal operation, they must be completely black or in a purely vertical state. If one region is completely black, the other cannot be completely black or purely vertical, because that would have led to a reset earlier. According to the second property, the top-left and bottom-left regions cannot both be in a purely vertical state. Therefore, there is always a valid operation.
Maintaining the First Property
- For the bottom-left and top-right regions, they always satisfy the first property. Proof: Consider the bottom-left region (the proof for the top-right region is similar). It starts as completely white, turning black row by row, maintaining a horizontal state. Once it is completely black, it resets column by column, maintaining a vertical state. Thus, it alternates between horizontal and vertical states.
- For the top-left region, it always satisfies the first property. Proof: After coloring and before resetting, the top-left region still satisfies the first property. Suppose it is in a horizontal state before resetting (the proof for a vertical state is similar). Since it cannot reset vertically, it remains at least in a horizontal state after resetting. If it becomes completely black and resets horizontally (the proof for a vertical reset is similar), it remains in a horizontal state. Unless $$$k = 1$$$, rows and columns cannot reset simultaneously. Suppose both rows and columns can reset, and assume the current operation is horizontal in the top-left region (the proof for a vertical operation is similar). This means the top-left region was in a purely horizontal state before turning completely black. The row in the top-right region was completely black, while other rows were white, contradicting the second property before the operation.
Maintaining the Second Property
- Assume the current operation is horizontal (the proof for vertical operations is similar) and causes a reset, the second property still holds. Proof: If the operation is in the bottom-left region, it was completely black before resetting. After resetting, the top-left region turns completely white, maintaining the second property. We previously proved that unless $$$k = 1$$$, rows and columns cannot reset simultaneously. If the horizontal operation is in the top-left region and columns reset, the top-left region was completely black before resetting. After resetting, the top-left region becomes vertical, while the bottom-left region turns white, maintaining the second property. If the horizontal operation is in the top-left region and rows reset, the top-left region remains unchanged, while the row in the top-right region turns white. If the top-right region's state changes and resets to a purely horizontal state (the only possible violation of the second property), the top-right region is completely black before resetting. Thus, the top-left region was not in a purely horizontal state before resetting. Since the top-left region remains unchanged, it cannot be in a purely horizontal state, maintaining the second property.
- Assume the current operation is horizontal (the proof for vertical operations is similar) and does not cause a reset, the second property still holds. Proof: If the operation is in the bottom-left region, it remains in a horizontal state, maintaining the second property. If the operation is in the top-left region, the only possible violation of the second property is if the top-right region remains in a purely horizontal state while the top-left region becomes purely horizontal. This means the top-left region was completely white before the operation. In this case, we can choose to reset any completely black row in the top-right region. According to the strategy, we prioritize resets, leading to a contradiction. Thus, the second property still holds.
#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 105;
char operationType;
int n, m, k, q, grid[MAX_SIZE][MAX_SIZE];
string s;
int calculateSum(int x1, int y1, int x2, int y2) {
int sum = 0;
for (int i = x1; i <= x2; i++)
for (int j = y1; j <= y2; j++)
sum += grid[i][j];
return sum;
}
void performOperation(int x, int y) {
cout << x << ' ' << y << '\n';
for (int i = 1; i <= k; i++) {
grid[x][y] = 1;
if (operationType == 'H')
y++;
else
x++;
}
int rowSums[MAX_SIZE] = {}, colSums[MAX_SIZE] = {};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
rowSums[i] += grid[i][j];
colSums[j] += grid[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (rowSums[i] == m || colSums[j] == n)
grid[i][j] = 0;
}
void solve() {
cin >> n >> m >> k >> q >> s;
s = ' ' + s;
memset(grid, 0, sizeof(grid));
for (int i = 1; i <= q; i++) {
operationType = s[i];
if (operationType == 'H') {
int row = -1;
for (int j = 1; j <= n; j++)
if (calculateSum(j, 1, j, k) == 0) {
row = j;
if (calculateSum(j, 1, j, m) == m - k) {
break;
}
}
performOperation(row, 1);
} else {
int col = -1;
for (int j = 1; j <= m; j++)
if (calculateSum(1, j, k, j) == 0) {
col = j;
if (calculateSum(1, j, n, j) == n - k) {
break;
}
}
performOperation(1, col);
}
}
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
1991H — Prime Split Game
Consider which pairs of numbers an odd number can be split into. What about an even number?
Consider a simplified version of the game with only two piles of stones, where the first pile contains $$$x$$$ stones, and the second pile contains one stone. Determine all winning positions for this game configuration.
For the simplified version of the game, given that we have calculated the odd $$$x$$$ which are losing positions, we can quickly determine the winning positions for even $$$x$$$ using Fast Fourier Transform or bitset operations.
We can determine the winner of most games by considering how many $$$a_i$$$ are in winning positions and whether $$$n$$$ is odd or even.
For games where we currently cannot determine the winner, we can use the number of $$$a_i$$$ that can be split into two winning positions to determine the final winner.
Let's analyze this problem from simple to complex scenarios.
First, let's consider how to split a single number $$$x$$$:
- For an odd number $$$x$$$, it can only be split into $$$x - 2$$$ and $$$2$$$. Proof: An odd number can only be split into an odd and an even number, and the only even prime is $$$2$$$.
- For an even number $$$x$$$, apart from $$$x = 4$$$ which can be split into $$$2$$$ and $$$2$$$, it can only be split into two odd numbers. Proof: An even number can only be split into odd and odd, or even and even. The only even prime is $$$2$$$, thus only $$$4$$$ can be split into even and even.
Next, let's consider a simplified version of the game with only two piles of stones, where the first pile contains $$$x$$$ stones, and the second pile contains one stone. If Alice wins in this setup, we call $$$x$$$ a winning position; otherwise, it is a losing position. We first determine whether an odd $$$x$$$ is a winning position, then determine whether an even $$$x$$$ is a winning position:
- For an odd $$$x$$$, we need to calculate how many times $$$2$$$ stones can be split from $$$x$$$ until $$$x - 2$$$ is not a prime. If the number of splits is odd, then it is a winning position; otherwise, it is a losing position.
- For an even $$$x$$$, if $$$x$$$ can be split into two losing positions, then $$$x$$$ is a winning position; otherwise, $$$x$$$ is a losing position. Apart from $$$x = 4$$$ (a winning position), other even numbers can only be split into two odd numbers. Optimization: Directly checking all ways to split each even number will time out. However, we can use the Fast Fourier Transform (FFT) or bitset operations, based on the losing positions of odd numbers, to determine the winning positions of even numbers. If you are not familiar with this optimization technique, it is recommended to first solve 2014 ICPC SWERC Problem C Golf Bot, the tutorial is here.
In summary, the characteristics of winning and losing positions are: losing positions either cannot be split, or they must split out at least one winning position. Winning positions can be split into two losing positions.
Let's return to the original game. If all $$$a_i$$$ are in losing positions, Bob will win. Proof: No matter how Alice moves, Bob can always turn all $$$a_i$$$ back to losing positions. Suppose Alice splits to produce $$$2 \cdot k$$$ new piles in one move, then at least $$$k$$$ of them will be in winning positions. Bob can split these $$$k$$$ piles into $$$2 \cdot k$$$ losing positions and remove the remaining $$$k$$$ new piles. As a result, all piles will be back in losing positions. This process will continue until no more losing positions can be split, which will lead to Bob's win.
Since we now have a general scenario where Bob wins, we can discuss all scenarios that can turn into this scenario with one move. In these scenarios, Alice will win:
The only unresolved case is when $$$n$$$ is odd and the number of winning positions $$$a_i$$$ equals $$$n$$$. Alice cannot turn all positions into losing positions in one move because at most $$$2 \cdot k$$$ positions can be changed in a single move. Since $$$2 \cdot k < n$$$, it is impossible to change all $$$n$$$ positions. In this case, if someone splits a winning position into a losing position, the number of winning positions will drop to $$$[1, n - 1]$$$, leading to failure. However, winning positions can sometimes be split into two winning positions. Therefore, we only need to consider this splitting case.
A number is called a good position if it can be split into two winning positions; otherwise, it is called a bad position. We find that odd numbers cannot be good positions because they can only be split into $$$x - 2$$$ and $$$2$$$, and $$$2$$$ is not a winning position. Thus, only even numbers can be good positions if they can be split into two odd winning positions. Optimization: Directly checking ways to split each even number will time out. We can use FFT or bitset operations to identify good positions among even numbers.
Note that good positions can only be split into two bad positions because even numbers can only be split into odd numbers or $$$2$$$, both of which are considered bad positions. Thus, when $$$n$$$ is odd and all $$$a_i$$$ are in winning positions, we only need to determine the winner based on the number of good positions:
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
bitset<MAX_N + 1> isComposite, isWinning, isPrimeLosing, isPrimeWinning, isGoodPosition;
void initialize() {
isComposite[1] = true;
for (int i = 2; i <= MAX_N; i++)
for (int j = 2 * i; j <= MAX_N; j += i)
isComposite[j] = true;
for (int i = 3; i <= MAX_N; i += 2) {
int count = 0, j = i;
while (!isComposite[j - 2]) {
count++;
j -= 2;
}
isWinning[i] = count % 2;
isPrimeLosing[i] = !isComposite[i] && !isWinning[i];
}
isWinning[4] = true;
for (int i = 3; i <= MAX_N; i += 2)
if (isPrimeLosing[i])
isWinning |= isPrimeLosing << i;
for (int i = 1; i <= MAX_N; ++i)
isPrimeWinning[i] = (i % 2) && isWinning[i] && !isComposite[i];
for (int i = 3; i <= MAX_N; i += 2)
if (isPrimeWinning[i])
isGoodPosition |= isPrimeWinning << i;
}
void solve() {
int n, x, totalWinning = 0, totalGood = 0;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x;
totalWinning += isWinning[x];
totalGood += isGoodPosition[x];
}
if (totalWinning <= n - n % 2)
cout << (totalWinning ? "Alice" : "Bob") << endl;
else
cout << (totalGood && totalGood < n ? "Alice" : "Bob") << endl;
}
int main() {
initialize();
int t;
cin >> t;
while (t--)
solve();
}
1991I — Grid Game
Notice that if the problem requires our selected numbers' sum to be greater than the interactor's sum, instead of smaller, the essence of the problem changes.
Depending on whether $$$n \cdot m$$$ is odd or even, we can use different methods to fill the grid and adapt our game strategy.
When $$$n \cdot m$$$ is odd, we can adopt a strategy that forces the interactor to choose the largest number, $$$n \cdot m$$$.
When $$$n \cdot m$$$ is even, we can divide the grid into several tiles. After the interactor chooses a number from a tile, we immediately choose from the same tile.
We set each tile size to be even, ensuring we always select the second number from each tile.
When $$$n \cdot m$$$ is even, we can create some T-shaped tiles at the edges of the grid, where each T-shaped tile consists of a cell on the edge and three cells surrounding it.
Place a small number in the center of each T-shaped tile, and fill the surrounding three cells with large numbers. This way, we can always select the smallest number from each T-shaped tile, except for the interactor's first choice.
When $$$n \cdot m$$$ is even, we only need to create $$$4$$$ T-shaped tiles and divide the remaining cells into several dominos, each containing two adjacent numbers. This method of filling numbers is sufficient to ensure that the sum of the numbers we choose is smaller.
Notice that if the problem requires our selected numbers' sum to be greater than the interactor's sum, instead of smaller, the essence of the problem changes. Specifically, when $$$n \cdot m$$$ is odd, the interactor will select one more number than us. If the goal is to have a greater sum of numbers, the interactor will have an advantage; conversely, if the goal is to have a smaller sum, we will have an advantage.
Depending on whether $$$n \cdot m$$$ is odd or even, we can use different methods to fill the grid and adapt our game strategy. Here, we will explain these two methods and strategies in detail.
When $$$n \cdot m$$$ is odd, we can adopt a strategy that forces the interactor to choose the largest number, $$$n \cdot m$$$. Specifically, we can divide the grid into:
- $$$\lfloor \frac{n \cdot m}{2} \rfloor$$$ dominos ($$$1 \times 2$$$ or $$$2 \times 1$$$ tiles), each containing two adjacent numbers.
- In the remaining single cell, we place the largest number.
Our strategy is as follows: If the interactor chooses a number from a domino and the other number has not yet been chosen, we choose that number; otherwise, we choose any valid number from the dominos. This ensures that:
- In each domino, both we and the interactor select one number. Proof: The interactor cannot choose both numbers in a domino because as soon as they choose the first one, we immediately choose the second one. Therefore, we select at least one number in each domino. We cannot select two numbers in any domino because our total number of selections would exceed the number of dominos, which equals our total number of selections. Hence, we exactly select one number in each domino.
- The interactor will inevitably choose the largest number. Proof: Since we only choose numbers from the dominos, the remaining largest number will not be selected by us.
In the worst case, we will choose the larger number in each domino. However, the interactor will always select the largest number. Therefore, in this scenario, our sum will be less than the interactor's sum by $$$n \cdot m - \lfloor \frac{n \cdot m}{2} \rfloor = \lceil \frac{n \cdot m}{2} \rceil$$$.
When $$$n \cdot m$$$ is even, we can divide the grid into several tiles. After the interactor chooses a number from a tile, we immediately choose from the same tile. We set each tile size to be even, ensuring we always select the second number from each tile.
If a small number is surrounded by large numbers in a tile, as the second chooser we can choose the small number. We place the small numbers on the edges of the grid, where the number of surrounding cells is odd, ensuring that each tile has an even number of cells. This tiling arrangement gives us a significant advantage; only a few such tiles are needed, while the rest of the grid can be filled with dominos containing adjacent numbers, making our sum of numbers smaller. Here are the detailed descriptions of grid filling and game strategy:
We divide the grid into:
- $$$4$$$ T-shaped tiles, each with a small number at the edge of the grid, surrounded by three large numbers.
- $$$\frac{n \cdot m - 16}{2}$$$ dominos, each containing two adjacent numbers.
Specifically, we define $$$[1, 4]$$$ as small numbers, and $$$[n \cdot m - 11, n \cdot m]$$$ as large numbers. Numbers $$$[n \cdot m - 11, n \cdot m - 9]$$$ surround number $$$1$$$, $$$[n \cdot m - 8, n \cdot m - 6]$$$ surround number $$$2$$$, $$$[n \cdot m - 5, n \cdot m - 3]$$$ surround number $$$3$$$, and $$$[n \cdot m - 2, n \cdot m]$$$ surround number $$$4$$$.
Assuming $$$n \le m$$$, we divide the grid as follows:
- For $$$n = 4$$$ and $$$m = 4$$$, as well as $$$n = 4$$$ and $$$m = 5$$$, we manually divide the grid.This is a specific layout for a $$$4 \times 4$$$ grid, with bold lines indicating tiles division, green cells representing small numbers, and red cells representing large numbers.This is a specific layout for a $$$4 \times 5$$$ grid, with additional settings, where yellow cells represent adjacent numbers in dominos.
- For $$$m \geq 6$$$, we place two T-shaped tiles and two dominos in the top left and top right $$$4 \times 3$$$ areas. The remaining part of the top four rows can be filled with vertical dominos. For rows beyond the top four, if $$$m$$$ is even, we fill them with horizontal dominos; if $$$m$$$ is odd, we fill them with vertical dominos.This is a specific layout for a $$$5 \times 8$$$ grid, an example where $$$m$$$ is even.This is a specific layout for a $$$6 \times 7$$$ grid, an example where $$$m$$$ is odd.
Our strategy is as follows: After the interactor chooses a number from a tile, we will immediately choose the smallest valid number from the same tile. This ensures that the interactor can only start choosing from the large numbers in each T-shaped tile, allowing us to choose the small number, except for the small number that the interactor initially chooses.
Next, we will analyze why this strategy ensures a smaller sum. For each T-shaped tile, if the interactor did not initially choose from this tile, we can at least choose the smallest and largest numbers; if the interactor initially chose from this tile, we can at least choose the second smallest and largest numbers. We find that if the interactor chooses to start from the T-shaped tile, they take away our smallest number and give us the second smallest number. Thus, in the worst case, the interactor starts choosing from number $$$4$$$, where the difference between the smallest and second smallest numbers in that tile is the largest. In dominos, we assume we will choose the larger number.
In the worst case, the calculation of our sum of numbers minus the interactor's sum of numbers is: $$$(1 - (n \cdot m - 11) - (n \cdot m - 10) + (n \cdot m - 9)) +$$$
$$$(2 - (n \cdot m - 8) - (n \cdot m - 7) + (n \cdot m - 6)) +$$$
$$$(3 - (n \cdot m - 5) - (n \cdot m - 4) + (n \cdot m - 3)) +$$$
$$$(-4 + (n \cdot m - 2) - (n \cdot m - 1) + n \cdot m) +$$$
$$$(n \cdot m - 16) / 2 =$$$
$$$20 - 1.5 \cdot n \cdot m$$$
When $$$n$$$ and $$$m$$$ are at their minimum, this value is the largest and unfavorable for us. However, when $$$n$$$ and $$$m$$$ are at their minimum of $$$4$$$, our sum of numbers is still $$$4$$$ less than the interactor's ($$$20 - 1.5 \cdot 4 \cdot 4 = -4$$$).
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 15, dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
int n, m, x, y, grid[MAX_N][MAX_N], color[MAX_N][MAX_N], visited[MAX_N][MAX_N], currentValue, currentColor, flipCoords;
bool isAdjacent(int x, int y) {
int nx, ny;
for (int i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (1 <= nx && nx <= n && 1 <= ny && ny <= m && visited[nx][ny])
return true;
}
return false;
}
void interact() {
cin >> x >> y;
if (flipCoords)
swap(x, y);
visited[x][y] = 1;
}
void output(int x, int y) {
visited[x][y] = 1;
if (flipCoords)
cout << y << ' ' << x << endl;
else
cout << x << ' ' << y << endl;
}
void placePair(int x1, int y1, int x2, int y2) {
grid[x1][y1] = ++currentValue;
grid[x2][y2] = ++currentValue;
color[x1][y1] = color[x2][y2] = ++currentColor;
}
void placeTShape(int x, int y) {
int largestValue = n * m - 12 + currentColor * 3;
grid[x][y] = ++currentValue;
color[x][y] = ++currentColor;
int nx, ny;
for (int i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (1 <= nx && nx <= n && 1 <= ny && ny <= m) {
grid[nx][ny] = ++largestValue;
color[nx][ny] = currentColor;
}
}
}
void printGrid() {
if (!flipCoords)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << grid[i][j] << ' ';
}
cout << endl;
}
else
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cout << grid[j][i] << ' ';
}
cout << endl;
}
}
void fillHorizontalPairs() {
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++)
if (!grid[i][j] && !grid[i][j + 1])
placePair(i, j, i, j + 1);
}
void fillVerticalPairs() {
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
if (!grid[i][j] && !grid[i + 1][j])
placePair(i, j, i + 1, j);
}
void solve() {
cin >> n >> m;
memset(grid, 0, sizeof(grid));
memset(color, 0, sizeof(color));
memset(visited, 0, sizeof(visited));
currentColor = currentValue = flipCoords = 0;
if (n % 2 == 1 && m % 2 == 1) {
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j += 2)
placePair(i, j, i, j + 1);
for (int i = 1; i <= n; i += 2)
placePair(i, m, i + 1, m);
grid[n][m] = n * m;
printGrid();
for (int i = 1; i < n * m; i += 2) {
interact();
bool selected = false;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (!visited[i][j] && color[i][j] == color[x][y]) {
output(i, j);
selected = true;
break;
}
if (selected)
break;
}
if (selected)
continue;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!visited[i][j] && isAdjacent(i, j) && grid[i][j] != n * m) {
output(i, j);
i = n;
j = m;
}
}
cin >> x >> y;
return;
}
if (n > m) {
swap(n, m);
flipCoords = 1;
}
if (n == 4 && m == 4) {
placeTShape(1, 2);
placeTShape(2, 4);
placeTShape(3, 1);
placeTShape(4, 3);
} else if (n == 4 && m == 5) {
placeTShape(1, 2);
placeTShape(3, 1);
placeTShape(3, 5);
placeTShape(4, 3);
fillHorizontalPairs();
} else {
placeTShape(1, 2);
placeTShape(3, 1);
placeTShape(1, m — 1);
placeTShape(3, m);
placePair(2, 3, 3, 3);
placePair(4, 2, 4, 3);
placePair(2, m — 2, 3, m — 2);
placePair(4, m — 2, 4, m — 1);
if (m % 2 == 0)
fillHorizontalPairs();
else
fillVerticalPairs();
}
printGrid();
for (int i = 1; i <= n * m; i += 2) {
interact();
pair bestMove = {-1,-1};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!visited[i][j] && color[i][j] == color[x][y] && (bestMove.first == -1 || grid[i][j] < grid[bestMove.first][bestMove.second]))
bestMove = {i,j};
output(bestMove.first, bestMove.second);
}
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}
so zengminghao told me during the round that problem I can be found at https://www.brand.site.co.il/riddles/200802q.html
Fortunately, it seems it has affected almost no one. Sorry for this unfortunate coincidence though :/
D is nice
Worst problem I've ever seen.
D feels more like a math problem rather than an algorithmic one. I don't think it's a good problem. :(
Why?
It's not mathy at all
It’s not something mathy it’s just a puzzle.
for problem D
for the test case where n = 4, shouldn't the answer be 2 because if we connect (1 with 2,3,4) we only need 2 colors, c1 for 1 and c2 for ( 2,3,4 ) each as they are connected to 1 and not with others.
Please correct me if I'm wrong.
$$$3$$$ and $$$4$$$ are also connected, as $$$3 = 11_2, 4 = 100_2, 11_2 \oplus 100_2 = 111_2 = 7$$$, which is prime.
In D sample test case with n = 6, the edges are (1, 2), (1, 4), (3, 4). Then we can color vertices 1 as c1, 2 as c2, 3 as c1, and 4 as c2. So only 2 colors are needed so how is the answer 4 with coloring (1 2 2 3 3 4)? Please correct where I am wrong.
There is also edge $$$(1, 3)$$$, since $$$1 \oplus 3 = 01_2 \oplus 11_2 = 10_2 = 2$$$.
Thanks, understood.
D was so annoying, I spent literally the last 2/3 of the contest trying to make an efficient checker if a xor b is prime, but I missed the easy solution for x>=6 (due to the 4 colors theorem in math or smth like that).
I didn't need a mathy theorem. All primes except 2 are odd, so there will only be edges between odd and even numbers so we can color odd and even in different colors, however the xor 2 will make an edge between numbers of same parity. We can build a graph for only odd numbers and one for only even numbers sith edges of xor 2 and color them like a bipartite graph
can you explain little more. I get till you have even and odd separately and edges between even even and odd odd. But how to handle even — odd edges ?
Just color odd numbers with colors 1-2 , and even numbers with 3-4. This way there will never be two connected nodes such that one of them is odd and the other is even with the same color.
4 color theorem doesn't apply here. Consider $$$K_5$$$ where the chromatic number is 5.
D was like Goodbye 2023, u either saw the pattern or cried
Downvoters are the ones who cried lol
I believe anyone can't get the solution unless you know the four color theorem :(
Your belief is false
imo, D wasn't so good
D is going on bullet point 1 of my suicide note
I came to that conclusion of minimum number of colors being 4 in a more rigorous way and paid dearly for it by being unable to implement it.
I had this idea, let edges between $$$a$$$ and $$$b$$$ have the number $$$XOR(a, b)$$$ being a prime number say $$$p_1$$$. then let's take $$$3$$$ numbers $$$a, b, c$$$
where $$$b$$$ and $$$c$$$ have edges with $$$a$$$.
then if $$$a$$$ and $$$b$$$ have edge with value $$$p_1$$$
and $$$a$$$ and $$$c$$$ have edge with value $$$p_2$$$
(and none of $$$p_1$$$ or $$$p_2$$$ is 2)
then the associated edge number between $$$b$$$ and $$$c$$$ must be $$$XOR(p_1, p_2)$$$ but both of them are odd. so this $$$XOR$$$ must be even or perhaps $$$2$$$!
if $$$XOR(p_1, p_2)=2$$$ and $$$XOR(a, d) = 2$$$; then $$$XOR(p_1, 2) = p_2$$$ and $$$XOR(p_2, 2) = p_1$$$ which implies that all $$$a, b, c, d$$$ are connected strongly and must have different colors.
There can be no higher form of "strong" connection. (I assume it's trivial by now).
I was first thinking about pruning a DFS/BFS like thing. I thought these $$$p_1$$$ and $$$p_2$$$ must be twin primes (ending with 01 and 11 in binary). Wrote a program to see how many such primes are and found they were less than 1400 till 200000, also did a bunch of weird stuff. but ultimately failed to do the thing.
I also tried so so many complex things. Actually, I reached conclusion that for n = 2 * 1e5, we need at maximum 36 colors, if we colour the graph greedily. And then implemented completely different thing. tried multiple appraoches, but all failed.
$$$K_4$$$ appears as a subgraph for $$$n \geq 6$$$ as $$$(1,3,4,6)$$$ is completely rigorous...
My comment was partially supposed to be a rant, (I understand $$$(1, 3, 4, 6)$$$ is $$$K_4$$$) Perhaps I focused too much on proving it without assuming it.
Had I assumed and then validated my assumption, I could have reached the solution.
Edit: Perhaps rigor is not the word I should have used. but you get what I wanted to say, I just meant proving it without assuming it. (which I understand, is in no way more complete or anything).
Also you ultimately prove your bound of $$$4$$$ by giving a valid construction.
saying that $$$K_4$$$ appears as a sub graph for $$$n>5$$$ just tells that the number of colors cannot be less than $$$4$$$. (for $$$n>5$$$)
you prove that it is in-fact, $$$4$$$, by providing a valid construction.
(Just putting it here so that others don't confuse this statement with a completely rigorous proof).
I’ve got the same idea.
D was like Goodbye 2023, u either saw the pattern or cried
If you're wondering about about the connection between XOR and modulo 4, you can upsolve CF15C : Industrial Nim
Update: I also created a video and practice contest on this idea.
quite a few constructives
constructiveforces
edit: A master copy pasted the exact same comment from me and got +38. What are the downvotes for??
so, you confirm that you just copy-pasted it and expect upvotes
I posted first.
ratism?
Maybe if you didn't edit your comment and whine about receiving downvotes, your comment would be in the green now
Probably my worst contest so far, I knew what to do but had some errors. Might need to take a step back and re-eval my approaches
Problem E is so similar to this Problem.
I can't note that $$$4\mid \left(a\oplus (a+4k)\right)$$$. So sad.
Why does 4∣(a xor (a+4k))? Is there an easy way to see this?
The last two bits of a and a + 4k are the same. So the last two bits of (a xor a+4k) are 0, which is the same as being divisible by 4.
Maybe noting this instead is better: The least significant bit of a — b and a ^ b are the same. So their divisibility by a power of 2 is always the same.
I can easily solve problems of E and F, but I struggled with problem D for a long time before coming up with a solution
B can be solved like this also ~~~~~
void Solve() { int n; cin >> n; vi a(n-1); cin >> a;
}
~~~~~
Why is the title of problem C "Maximize the Last Element"? Shouldn't it be "Absolute Zero"?
UPD: Changed.
A round full of ARC&AGC problems. :)
F could maybe be AGC A so I struggle to understand you since 3 problems don't make a full round. Is it sarcasm?
F is too ugly to be in AGC.
Well, I meaned all the problems are very tricky as ARC&AGC problems. Of course they cannot form a full AGC round, but forming an ARC round is possible.
Alternative solution for C (for the "YES" case):
Until all values become zero, do this for each iteration: Get the minimum and maximum of the current array. Change the values of the array with x = (maximum+minimum) / 2; At each iteration the value of (maximum-minimum) reduces by a factor of 2. So we will achieve the desired result in at most ceil(log(maximum-minimum)) operations.
Very cool, much more intuitive. I like it.
I did same sort array, subtracting all elements with the mean of the first and last element and sorting again
Repeat the process 40 times
if last element =0
Print YES else NO
Enjoyed the round a lot, especially D and E are great. Thanks to coordinators, authors and testers!
Human intelligence round
I think G is very Tang (I don't know how to say it in English?
D should have come after E I swear. I almost had E even though I only spent the last 30 mins on it, just didn't have time to get color assignment bugs sorted :(
No evaluation of good or bad but problem D strikes me as utterly absurd.
I think it's a perfect example of the current meta, where the first 3-4 problems are discrete math puzzles that are trivial to implement and only after them you get to the actual programming problems. Also not sure if this is good or bad
D is a good problem, I like it very much!
For any unselected sticks between the chosen sticks, if there exists a stick to its left and a stick to its right that belongs to the same triangle, we can replace the rightmost stick of this triangle with the unselected stick.
This is incorrect. Let's consider sticks 2, 4, 10, 11 and select non-consecutive 2, 10 and 11. Then we can't replace rightmost 11 with unselected 4 because 2 + 4 < 10. I think correct proof here should be something like: if we consider our triangle as two connected intervals left and right ([2;10] and [10;11]), then if the unselected stick is in the left interval (4 is in [2;10]) then we can replace the leftmost stick of the triangle with it, otherwise we can replace the rightmost.
leftmost will always work actually
Constructive Forces.
same solution as editorial. why still WA ??
upd: got it. thanks
273223229
I also have WA, can you please help why?
edit: got it, thankyou!
anyone tried colouring graph greedily in the problem D ???
yeah, when you do that it makes a weird pattern:
1 2 2 3 1 4 4 3 1 2 2 3 1 4 4 3 1 5 5 3 1 6 6 3 1 5 5 3 1 6 6 3 1 5 5 3 1 6 6 3 1 5 5 3 1 6 6 3 1 2 2 3 1 4 4 3 1 2 2 3 1 4 4 3 1 4 4 3 1 2 2 3 1 4 4 3 1 2 2 3 1 6 6 3 1 5 5 3 1 6 6 3 1 5 5 3 1 6 6 3
been there, and it touches 36, at n = 2054... and then we don't need any more colour than 36 till n = 2 * 1e5.
Problem C Video Editorial
https://youtu.be/wsD3l8J1Hog
G killed me, maybe guessing that the construction is not that hard will help next time
In H, it's possible to get AC without using FFT or bitset operations to find winning/good positions. Just generate all primes <= 2*10^5, find out if they're winning or losing, and sum every pair of losing primes (to find winning positions) and every pair of winning primes (for good positions).
can some body explain E and F? in E how it is biparitie and F would'nt it will be tle if for n queries there are there is multiple for loops ?plz explain
My another solution for $$$C$$$:
Note $$$k$$$ is the maximum integer such that $$$2^k \le max(a_i)$$$. I subtract $$$x=2^k-1$$$ from all the numbers. In most cases, the highest position will drop. But there is one exception: $$$max(a_i)=2^{k+1}-1$$$. In this case, I will perform an additional operation — randomly select a number between $$$[1,2^k-1]$$$.
It looks wrong in the worst case. But idk if it is hackable.
https://codeforces.net/contest/1991/submission/273218080
I tried a long ahh time, but can someone tell me how is this wrong for problem E. Let alone out of bounds error because theres no way thats possible
https://codeforces.net/contest/1991/submission/273238586
Edit: I found out, when clearing my adj list, i was clearing from 0 to n-1 instead of 1 to n :((
Atleast I'm happy i wasnt wrong
D: The sample says the answer is $$$4$$$ if $$$n=6$$$. So let's guess, in the general cases the answer is $$$4$$$ <- This is just a riddle.
I couldn't find any rules yet, so tried around $$$n=20$$$ with Chromatic Number. Then I said the answer is $$$4$$$, so starting to consider construct $$$4$$$-coloring.
I think it's somewhat natural, still it's a mascle approach.
Different solution to F:
For each right point you find the maximal left endpoint for which the answer is yes. It is easy to see that you can use the two pointer technique to compute this. We maintain a set (for its sorted order) and then moving the pointers basically amounts to inserting or removing from the set. To check whether a set is valid, treat it as a sorted vector and find the number of indices $$$i$$$ for which $$$a_i \lt a_{i-1}+a_{i-2}$$$; if it's at least 4 then we can show that two disjoint non-degenerate triangles exist, otherwise run a bruteforce. To make the solution efficient enough, we maintain the number of such indices throughout the insertions and removals, noticing that an element can only affect the state of at most three indices.
PLEASE REVIEW THIS ALTERNATE METHOD I USED FOR PROBLEM D.
this code is what i made but it does not pass the system testing.
let me explain in short what i have done.
first of all, i can find the array of colors for n <= 5 myself. for n > 5, there will be two cases: n is odd or n is even.
now if n is odd, it will never connect with vertex 1 (because odd ^ 1 = even ( >= 4) when odd >= 5, which are not prime) hence i can give color 1 to the all odd numbers after 3.
we will have more subcases when n is even. n ^ odd can be prime but n ^ even can never be prime except when n ^ even is 2, which is only possible when n & 2 is 2 (that is, binary representation of n has 2 in it) and even is n — 2 (as it will have all the 1s and 0s at the same position except the 2nd bit).
for checking with odd, we only need to care about 3 as it is colored with color 2, whereas all other odds are colored with color 1. Now we will keep track of the colors we have remaining. if n ^ 3 is prime, we will not have color 2. also if n ^ (n — 2) is prime, we will not have the color of vertex n — 2 as well. as we know that chances of n ^ odd being prime are significant, hence we assume that we do not have color 1 for n. so if n ^ 3 is not prime and n ^ (n — 2) is not prime or n ^ (n — 2) is prime but n — 2 has larger color (like 3 or 4) we will have color 2 free for n, else we will have color 3 free. else if n ^ 3 is prime we will have color 3 and 4 free for n (using the same logic).
so we will never require more that 4 colors and no two connected vertices will have the same color.
pls find any logical shortcoming in my answer, if there is any....
If n >= 14, then any two vertices from (11, 9, 12, 14) are adjacent. It means, that they must be with different colors. But in your code for every i > 5 vertex i can be colored in colors 2, 3, 4.
all odd numbers >= 5 are colored with color 1, so i am using all 4 colors available.
now if n is odd, it will never connect with vertex 1
this is correcthence i can give color 1 to the all odd numbers after 3
this is wrong.You failed to check that the odd numbers after 3 don't connect within themselves. And they do.
We have $$$4k+1 \oplus 4k+3 = 2$$$ (this is because the binary representation is all the same except for the last 2 bits). Substitute in any integer $$$k>=2$$$ to get a pair of odd numbers both greater than 3 that connect, so no you cannot give the color 1 to all odd numbers after 3. And thus your entire solution fails.
A big F...
thanks!
I would like to share another approach for Problem C : while the 40 operations are not over we will sort the array provided to us find the minima and maxima find the middle value and then use this middle value to form the new array and find absolute diff between array and mid and again sort the array till either all the values are 0 or the operations are over.
My code:Have a look
How is this giving optimal answer.
My cool (imo) solution to G :
Lets keep a buffer of size K * K at top left
The right section of K * (M — K) will be my V-placing zone
The bottom section of (N — K) * K will be by H-placing zone
We normally put any H or V in their respective zones, except for when the zones are full, then we use the buffer
Lets call a H block => buffer has a H type thing
H full => we cant place H in its zone
V full and V block defined similarly
If we can ensure V-zone full and H block doesnt happen simulatenously (and ofc its symmetric thing as well), we win
However, its easy to do that
1) if there is a H block, filling up V — zone naturally gets rid of that
2) if V — zone is full, there exists a row such that the row becomes full upon placing a H there
This looks equivalent to the editorial solution, prioritizing resets in the editorial is the same as maintaining the buffer here.
My post contest discussion stream for A-F
Hint for problems A-F
D is ok-ish, don't think all the hate is justified. (though reasoning in the editorial is strange – looks way too observation-based while just thinking about xor of odd/even almost immediately provides a solution)
But E imo is atrociously uninspiring – I couldn't believe that I understood the problem correctly until I got AC.
Can you explain the odd/even logic for D?
my thought process:
xor of same-parity numbers is even, which is usually not prime
so the most greedy approach would be to divide in two groups – even and odd
of course it doesn't work, e.g. 1^3=2
We know (at least from test case) that at some point we would need at least 4 groups, so let's try to divide both current groups in two
Let's just take odd numbers starting with one trying to avoid 2 as xor-sum of last two elements: 1, 5, 9, 13, 17...
And at this point I got the solution from the editorial
after writing it up I guess there are still some strange observations, but well, problem is mathy
Oh that's actually much more straightforward than I thought. That's a lot more intuitive than I thought.
ZhouShang2003, could you please share how the checker for problem D is implemented?
ZhouShang2003 shared Bitwise Xor Convolution, which can be applied to the values of each color to validate that no two numbers of the same color have their XOR equal to a prime number. Thanks!
The most cool thing was proving that range greater than equal to 48 will always be yes.
Swap D and E
I clearly am doing something wrong while writing code. My question is whether anyone can tell me what :pleading_face:
So many constructive problems, I got stuck on D for 10 minutes and nearly failed to get positive delta
Problem D could've been erased from the contest
" This ensures that any two vertices of the same color have a difference that is a multiple of 4, so their XOR is a multiple of 4"
Can anyone explain for me this line
Or in a less mathy way, you can think of their binary numbers. If you add a multiple of 4 to a binary number, it never affects the first two bits. This is because every bit to the left of the first two bits is divisible by 4, and the first two bits aren't. So adding something divisible by 4 can't change the first two bits. That means the last two bits of A and A+4 are the same which means that they both become zero when we xor them. This makes it divisible by 4.
D is a piece of shit
Hello,could you please tell me In Problem B’s answer ,what's the meaning of" If a(i-2) & a(i-1)=b(i-1)=1 , then a(i — 1)=1 ?" .
The idea I got in D after going through editorial was
If we take two number x and x+4 and so on their xor is always gonna yield a number which is multiple of 4 , so we need only 4 color as it is the minimum non prime number , so we can arrange all the numbers in these way so that it will take only 4 numbers to color them.
worst contest ever
the editorial approach for C which nobody did in the contest is actually understandable like you can see why it will make all numbers 0 after at most 30 iterations but what most of people did is (max_element /2 ) which I spent 3hours trying to get how did they think about that and I reached nothing I think getting this idea require some strong knowledge in some math field
I thought about it like this: Always choosing max_element/2 is the best option for narrowing all numbers in the array down, because there will never be number greater than the max if we chose max_element/2 as x prior, since there will be no number greater than abs(0-max/2), which is equal or lower than max-max/2. It is easy to understand that by choosing max/2 as x all the time, max will eventually be equal to 1, and since no number in the array is higher than max and all numbers have the same parity, when max==1, every number will be equal to 1, so when max turns 1, all you have to do is choose x as your next x and turn every number in the array to 0
Problem D
Constructive forces .
In F why do we need to use both algorithms would only either one of them not work to check for triangles?
You can find counter examples to both algorithms if used alone:
If only using algorithm 1 (6 consecutive elements), you will miss [1, 1, 2, 3, 10, 10, 11].
If only using algorithm 2, you will miss [1, 1, 2, 2, 2, 2].
It is not necessary to enumerate all sets of 6 consecutive sticks if the Algorithm 2 fails in F, we can only check 6 that are with the largest 3 that form a triangle
Here's a cool idea for problem F in brute forcing the '6 consecutive' sticks to find 2 triangles.
After sorting the range [l,r], we are dividing each set of 6 consecutive elements to 2 triangles... Each element could either be in triangle 0 or triangle 1. We hence want to be finding all permutations of [0,0,0,1,1,1] and mask them over the sticks..
The best part is that, we only need to check for 3 masks and not all masks. these are:
[0 1 0 0 1 1],
[0 1 1 0 0 1],
[0 1 1 1 0 0].
Why does this work?
Consider the mask [0,1,0,1,0,1] and let the elements be v_0, v_1, .. v_5
If this mask gave us two triangles it would mean:
v_0 + v_2 > v_4
v_1 + v_3 > v_5
Note that if this is true, so is
v_0 + v_2 > v_3
v_1 + v_4 > v_5
which is essentially mask [0,1,0,0,1,1].
This reduces the time taken immensely from TLE (5000 ms) to AC in 180 ms
Sub
I solved C in a alternate way :- Get the minimum and maximum ele in the array. Calculate the midpoint x between them by calculating the average. Apply the transformation ai = abs(ai-x). Perform this until all the elements becomes 0 or total num of operations exceeds 40.
I am not sure why this works ,it may be hackable,but in this way I was able to normalize quicker on pen and paper. Here is the submission:- 273227608
My thought process behind solving Problem D 1991D - Prime XOR Coloring:
In coloring problems with high constraints on the number of nodes, it's likely that the amount of needed colors in an answer is bounded by some number. I didn't immediately think that number would be $$$4$$$, but I kept this in the back of my mind.
Now, since we can't obviously create all edges where the xor of the endpoints is prime, I tried thinking of special properties of the graph:
1. There is an edge $$$(1, p - 1)$$$ for all primes $$$p$$$.
2. Can two even numbers have an edge between them? No, because primes are all odd and the xor of two even numbers can never be odd. Similarly, the xor of two odd numbers is even because they both have their $$$0$$$-th bit set initially.
Observation 1 wasn't too useful and observation 2 was wrong because I had forgotten about the only even prime number 2. But this reasoning was important because this meant that the only edges between odd numbers would be in pairs of complements where the $$$1$$$-th bit was set in one number and the $$$1$$$-th bit was off in the other. The same for even numbers. You can even print out these edges and draw them to visualize a small disconnected graph.
Now the final observation is that all the remaining edges are between odd and even numbers. And because even nodes connected to each other need to have different colors (same for odd nodes), this meant that the new even-odd edges didn't require any coloring changes to the graph. This is also a construction with just $$$4$$$ colors for any $$$N$$$. Looking at the sample made it clear that I could manually handle cases with small $$$N$$$ and run my solution for larger $$$N$$$.
D is the kind of problem that makes you burn the whole world down.
I agree it.
I felt E was better than D. Though I only got E a few minutes after the contest ended, it's a beautiful problem that lets you choose to play as Alice or Bob (although game is deterministic)
Since authors are getting slammed for no reason, I'll have to state that problem D is a nice problem, and the round was generally enjoyable. Good job!
Agreed, i enjoyed every problem except F.
Upsolved H, that too was excellent
D is a problem that might be obvious for skilled xor-problem solvers and really hard to guess otherwise, and as E and F felt like D and E I don't see why it should've been here. This problem alone is good, but this contest might be better without it. Of course I am speaking knowing how many people solved each task, but still
you are not supposed to guess it
editorial is badly written for D
all primes except 2 are odd => x, y cannot have an edge if parity(x) = parity(y), except for y = x ^ 2
divide into groups by parity, now every node has degree <= 1, trivially 2-colourable, combine to do 4 colours
Observe by samples n = 6 is already 4, so you're done. Great problem imo. Excellent to have n = 1...6 in samples, no guessing needed
THIS IS REALLY NICE
Who asked?
I am very sorry for this comment. I actually really enjoyed the round and problem D. I commented on it only as a joke and regret my decision.
constructive round
I have one question about problem D: Assume that we only need 2 color to color all node, the i-th node is color with color i%2+1 so that every node with same color will have the XOR is a multiple of 2. But this assumption is wrong because we can point out that vertices 1, 3, 4, and 6 form a clique. So that the minumun answer is 4 color. But it is possible that we can find a case that prove 4 color is wrong like the example above? Thanks in advanced.
No, because the counterexample is that 1 xor 3 = 2. 2 is a multiple of 2, but it is also prime.
On the other hand, 4 is a multiple of 4, but 4 itself is not prime.
I got it, thanks
There are too many constructive problems!
https://codeforces.net/contest/1991/submission/273321133
can anyone please help me figure out whats wrong with this . the logic seems to be same as that of the editorial.
Can someone explain why am i getting MLE in this?
273351492
How can we mathematically prove that a^(a+4k) will be a multiple of 4? Here ^ is XOR . Also does this hold only for powers of 2( 4 in this case)? a^(b+c) != a^b+a^c, otherwise it was trivial, let me know how do we come up with these proofs.
if the difference is 4 between a and b , a<b , then always the first two bits of the a and b will be the same (since we are adding on the 3rd bit on the a and that can only affect bits who are higher or equal to 3rd bit of a). since the first 2 bits are equal , first two bits of a^b is 00 , and you can only represent each number as a multiple of 4 if their first 2 bits is 00(you can shift it 2 times which is equilavent to dividing it by 4 , if first 2 bits is not 00 while shifting you will lose some true bits which means number will be rounded down)
That helps! Thank you
Right now the official code for H is broken, and gives a out of bound error. To fix it you must initialize bitset to MAXN+1 instead of MAXN.
Someone please explain the proof for F...Why it is always possible to form 1 triangle if we have at least 45 sticks. Also that fibonacci thing...that is not clear to me....please explain ..it will be helpful.
Lets say you want to create a longest sequence of numbers such that no three sticks can form a triangle. Suppose the sorted order is a[1], a[2], ..., a[n].
Now, we know by triangle inequality a[1]+a[2]<=a[3] a[2]+a[3]<=a[4] ... so on
Suppose we want to construct our sequence in this ascending order. It is obviously correct to choose the smallest number possible in the sequence. I.e. if our existing sequence is a[1], a[2], ..., a[m-1], a[m], then we want to put the smallest x such that x>a[m] and there does not exist indices 1<=i<j<=m such that a[i]+a[j]>x. It is optimal to choose x=a[m-1]+a[m]. This is because choose anything smaller and we have a[m-1]+a[m]>x, so a[m-1], a[m], and x can be made into a triangle. Anything bigger and we are simply limiting our future terms in the sequence more.
Now, the Fibonacci thing seems clear. By using this greedy strategy of choosing the smallest number possible for the next term in the sequence, we construct the sequence 1, 1, 2, 3, 5, 8, 13, ..., the fibonacci numbers.
The 45 comes from the fact that F_45>10^9, which is the bound on the array values in the question.
However, since the question asks for two constructing two triangles, we must use the number 48 instead, as we need 3 more numbers in our sequence to guarantee we can always construct two triangles
in ques 2 why are we taking or?
In D, in the tutorial it is stated for more than 6 nodes we need 4 colors. But if there is a triangle in the graph, we need 3 colors, how is this ensured that there will be no triangle in the graph.