Problem A: GCD Sum
Author and Problemsetting: ninja_28
Editorialist: sigma_g
<div>e2a970acb8bc15e0a6835e4380bfebf8</div>
Problem B: Box Fitting
Author and Editorialist: sigma_g
Problemsetting: ninja_28
Problem C: Planar Reflections
==================
Author, Problemsetter and Editorialist: [user:sigma_g]
<div>3ea91202f85b2eddb87bfdab4e6a258b</div>
<div>cccd7c1ac30767f4557e9919d8bc12b2</div>
<div>9a222dcdbc56a3fd9f4c674bcd5d95da</div>
<div>0715c2f1d3d122880efea24915623ed2</div>
<div>0f5c60fb50bcf6dc43f81ee05d878f89</div>
<div>c2441ecee00d070e90fa99725b16c391</div>
<div>5d0cc1878b430f9f4df9a88a6de02aa8</div>
Problem D: Bananas in a Microwave
Author: shash42 Problemsetting and Editorialist: sigma_g
include
include
using namespace std; using LL = long long;
const int DIV = 1e5;
inline LL ceil(LL x, LL y) { return (x + y — 1) / y; }
int main() { int T, M; cin >> T >> M;
vector<bool> is_seen(M + 1, false); is_seen[0] = true; vector<int> answer(M + 1, -1); answer[0] = 0; for (int timestep = 1; timestep <= T; timestep++) { auto new_is_seen = is_seen; int t, y; LL x; cin >> t >> x >> y; auto operation = [&](long long &curr) { if (t == 1) { curr = curr + ceil(x, DIV); } else { curr = ceil(curr * x, DIV); } }; for (int k = 0; k <= M; k++) { if (is_seen[k]) { long long curr = k; operation(curr); for (int a = 1; a <= y;) { if (curr > M) break; if (is_seen[curr]) break; new_is_seen[curr] = true; answer[curr] = timestep; a++; operation(curr); } } } is_seen = new_is_seen; } for (int i = 1; i <= M; i++) cout << answer[i] << " "; cout << endl;
}
</spolier>
<spoiler summary="Python solution">
</spolier>
Problem E: Two Houses
Author: dixitgarg Problemsetting and Editorialist: dixitgarg
In this problem we have to output two nodes $$$a$$$ and $$$b$$$ such that there is a path from $$$a$$$ to $$$b$$$ and $$$b$$$ to $$$a$$$ and the absolute value of the difference of the indegree $$$(|k_a - k_b|)$$$ should be maximum. First of all let us think of bireachability only i.e how to find two nodes $$$a$$$ and $$$b$$$ such that they are both reachable from each other? How can we verify this from the judge? Because if we ask $$$"? \ a \ b"$$$ i.e whether there is a path from $$$a$$$ to $$$b$$$ or not, then if the judge answers "Yes", we can't ask further queries. So we have to ask queries for those pairs $$$(a,b)$$$ for which we are sure that there is a path from $$$b$$$ to $$$a$$$. So how to ensure whether there is a path from $$$b$$$ to $$$a$$$ or not?
The answer lies in the fact that the given graph is not an ordinary graph, it is a special one. For every pair of vertices in this graph, there is a directed edge. So this type of graph has some interesting properties which we are going to see now.
Image how the compressed SCC of the graph will look like. For every pair of nodes of compressed SCC, there will be an edge, so it will have exactly one source, one sink and there would be only one possible topological sorting of this compressed SCC.
Since there is an edge between every pair of nodes, for every pair of nodes in the compresses SCC also, there would be an edge. And we know that if there is an edge between node $$$a$$$ to node $$$b$$$, then node $$$a$$$ comes before node $$$b$$$ in the topological sort. So for every pair of nodes of compressed SCC, we know which node would come first in the topological sorting, so it would result in a unique topological sorting.
Now we'll see one interesting and important property of this graph.
Property : Consider two consecutive strongly connneted components in the topological sorting, then all nodes present in the left component will have indegree strictly less than all nodes present in the right component. Here left denotes lower enumeration in the topological sorting.
Using the above property we can argue that if indegree of node $$$a$$$ is greater than the indegree of node $$$b$$$, then node $$$a$$$ is reachable from node $$$b$$$. Because either node $$$a$$$ lies in the same SCC or to the SCC of higher enumeration in topological sorting. In both cases $$$a$$$ is reachable from $$$b$$$.
So we can store all pairs of nodes $$$(a,b), 1 \leq a \leq n, 1 \leq b \leq n, a < b$$$ in an array and sort it according to decreasing order of absolute value of difference of indegrees i.e $$$|k_a - k_b|$$$. And if we pick a pair, let it be ($$$a$$$,$$$b$$$) and $$$indegree[b] > indegree[a]$$$, then we are sure that $$$b$$$ is reachable from $$$a$$$ so we need to check whether $$$a$$$ is reachable from $$$b$$$ or not, so we ask $$$"? \ b \ a"$$$ and if the judge responds by "Yes", then it means both $$$a$$$ and $$$b$$$ are reachable from each other. Since we were iterating in the dereasing order of $$$|k_a - k_b|$$$, we get the optimal answer.If judge never outputs "Yes" in the whole process, then there is no pair of nodes which are reachable from each other. So we will output $$$"? \ 0 \ 0"$$$
Overall Complexity : $$$O(n^2 \log_2 n)$$$
include <bits/stdc++.h>
using namespace std;
int main() { int n; cin >> n;
vector<int> indegree(n); for (int i = 0; i < n; i++) { cin >> indegree[i]; } vector<pair<int, pair<int, int>>> vec; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (indegree[i] > indegree[j]) vec.push_back({indegree[i] - indegree[j], {i, j}}); else vec.push_back({indegree[j] - indegree[i], {j, i}}); } } sort(vec.rbegin(), vec.rend()); for (auto it : vec) { if (it.first < 0) break; int a = it.second.first, b = it.second.second; cout << "? " << a + 1 << " " << b + 1 << endl; cout.flush(); string str; cin >> str; if (str == "Yes") { cout << "! " << a + 1 << " " << b + 1 << endl; cout.flush(); return 0; } } cout << "! 0 0" << endl; cout.flush(); return 0;
}
</spolier>
<spoiler summary="Python solution">
import sys input = lambda: sys.stdin.readline().rstrip()
n = int(input())
indegs = list(map(int, input().split()))
pairs = [] for i in range(n): for j in range(i + 1, n): if indegs[i] > indegs[j]: pairs.append((indegs[i] — indegs[j], (i, j))) else: pairs.append((indegs[j] — indegs[i], (j, i)))
pairs = sorted(pairs, reverse=True) l = len(pairs)
for _, nodes in pairs: ni, nj = nodes
sys.stdout.write(f"? {ni + 1} {nj + 1}\n") sys.stdout.flush() s = input() if s == "Yes": sys.stdout.write(f"! {ni + 1} {nj + 1}\n") exit(0)
sys.stdout.write("! 0 0\n")
</spolier>
Problem F: Christmas Game
Author: nikhil_c Problemsetting and editorialist: sigma_g
Let us say it's Alice's turn. If Alice moves some coins from an even step to an odd step, then Bob can move exactly those same coins from that odd step back to an even step. After this transition, once again it's Alice's move. In fact, we realize that Bob can "revert" every even->odd move by Alice.
Therefore, if Alice wants to win, she has to play at least one odd->even move. Moves that go from even->odd do not affect the game state at all, as the other player can always play another move that reverts them. Therefore, we can say that any coins present on even steps will not change the game state.
Hence, we can conclude that moving a coin from odd step to an even step is as good as taking a coin from the odd step and throwing it away.
How to calculate these xors? At each node $$$x$$$, we store a vector of size $$$D(n) = 2\cdot K$$$ where $$$D(n)_i$$$ is the xorsum of all nodes having their depth = $$$i$$$ — relative to node $$$x$$$ — in the subtree of node $$$n$$$.
include
include
using namespace std;
const int N = 1e5 + 1; const int K = 20 + 1;
using VI = vector; using VVI = vector<vector>;
VVI dp(N, VI(2 * K)); VI a(N); vector win(N); int n, k, k2;
void dfs(VVI &adj, int node, int prev) { dp[node][0] = a[node];
for (auto neigh : adj[node]) { if (neigh == prev) continue; dfs(adj, neigh, node); for (int rem = 1; rem < k2; rem++) dp[node][rem] ^= dp[neigh][rem - 1]; dp[node][0] ^= dp[neigh][k2 - 1]; }
}
void dfs2(const VVI &adj, const int node, const int prev, const vector &my_xors) { vector final_xors(k2); for (int i = 0; i < k2; i++) final_xors[i] = my_xors[i] ^ dp[node][i];
unsigned int odd_layer_xor = 0; for (int i = k; i < k2; i++) odd_layer_xor ^= final_xors[i]; win[node] = odd_layer_xor > 0; for (auto neigh : adj[node]) { if (neigh == prev) continue; auto xor_send = final_xors; // remove all contribution of this subtree for (int i = 1; i < k2; i++) xor_send[i] ^= dp[neigh][i - 1]; xor_send[0] ^= dp[neigh][k2 - 1]; // whatever was depth k for me is depth k+1 for my child node int last = xor_send.back(); for (int i = k2 - 1; i > 0; i--) xor_send[i] = xor_send[i - 1]; xor_send[0] = last; dfs2(adj, neigh, node, xor_send); }
}
int main() { cin >> n >> k; k2 = 2 * k;
VVI adj(n + 1); for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } for (int i = 1; i <= n; i++) cin >> a[i]; dfs(adj, 1, 0); dfs2(adj, 1, 0, vector<unsigned int>(k2)); for (int i = 1; i <= n; i++) cout << (win[i] ? 1 : 0) << " "; return 0;
}
</spoiler>
<spoiler summary="PyPy3 solution">
n, k = list(map(int, input().split())) k2 = 2 * k
dp = [[0 for _ in range(k2)] for _ in range(n + 1)] adj = [[] for _ in range(n + 1)]
for _ in range(n — 1): _x, _y = list(map(int, input().split())) adj[_x].append(_y) adj[_y].append(_x)
a = [0] + list(map(int, input().split()))
win = [0 for _ in range(n + 1)]
parent = [0 for _ in range(n + 1)]
def dfs(node): global parent global dp
stack = [node] pass_num = [0 for _ in range(n + 1)] while stack: node = stack[-1] pass_num[node] += 1 if pass_num[node] == 1: for neigh in adj[node]: if neigh == parent[node]: continue parent[neigh] = node stack.append(neigh) continue dp[node][0] = a[node] stack.pop() for neigh in adj[node]: if neigh == parent[node]: continue for rem in range(1, k2): dp[node][rem] ^= dp[neigh][rem - 1] dp[node][0] ^= dp[neigh][k2 - 1]
def dfs2(node): global win
stack = [[node, [0 for __ in range(k2)]]] global dp while stack: node, prev_xors = stack[-1] stack.pop() final_xors = [x ^ y for x, y in zip(prev_xors, dp[node])] for neigh in adj[node]: if neigh == parent[node]: continue send_xors = [x for x in final_xors] for i in range(1, k2): send_xors[i] ^= dp[neigh][i - 1] send_xors[0] ^= dp[neigh][k2 - 1] send_xors = [send_xors[-1]] + send_xors[:-1] stack.append([neigh, send_xors]) odd_xor = 0 for i in range(k, k2): odd_xor ^= final_xors[i] win[node] = 1 if odd_xor > 0 else 0
dfs(1) dfs2(1) print(" ".join(list(map(str, win[1:]))))
</spoiler>