### Qingyu's blog

By Qingyu, history, 20 months ago,

Could not find an official announcement, let's discuss problems here.

• +133

 » 20 months ago, # | ← Rev. 2 →   +14 How to solve Div.2 M(Colors and Pearls) and P(Number Sequence)?
•  » » 20 months ago, # ^ |   +49 It looks like the problems for Div.2 were taken from some past ICPC Asia online contests...M: A brute force solution is to denote $f_n$ as the answer for $a_{1} \cdots a_n$, then $f_n = \min_{0 \leq i < n} (f_i+v^2(i,n))$. Note that $f_n \leq n$, so we only need to keep the states that satisfy $v(i,n)\leq \sqrt n$. Time complexity is $\Theta(n \sqrt n)$. Code#include using namespace std; const int N = 2e5 + 50; int a[N], dp[N], f[N], g[N], lst[N]; int main() { int n; ios::sync_with_stdio(false); cin.tie(nullptr); while (cin >> n) { for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) { lst[i] = g[a[i]]; g[a[i]] = i; } int tot = 0; memset(dp, 0x3f, n + 1 << 2); memset(f, 0, n + 1 << 2); memset(g, 0, n + 1 << 2); dp[0] = 0; for (int i = 1; i <= n; ++i) { int cnt = 0; g[++cnt] = i; for (int k = 1; k <= tot; ++k) if (a[f[k]] != a[i]) g[++cnt] = f[k]; for (int i = 1; i <= cnt; ++i) f[i] = g[i]; tot = cnt; tot = std::min(tot, (int)sqrt(i) + 1); for (int k = 1; k <= tot; ++k) dp[i] = std::min(1ll * dp[i], dp[f[k + 1]] + 1ll * k * k); } printf("%d\n", dp[n]); } } N: For a pile of stones, we have $\mathcal G_n = \operatorname{mex}_{i+j using namespace std; int main() { int T, n; ios::sync_with_stdio(false); cin.tie(nullptr); while ((cin >> n)) { int sum = 0, x; while (n--) { cin >> x; sum ^= x; } puts(sum ? "Win" : "Lose"); } } O is just a simple breadth first search problem.P: We can make each$a_i\oplus b_i$become$(111\cdots 1)_2$by greedily pairing. This is obviously the optimal answer. Code#include const int N = 1e5 + 50; int a[N], b[N], n; long long s, o, tot; int main() { while (~scanf("%d", &n)) { s = 0; memset(b, -1, sizeof b); for (int i = 0; i <= n; ++i) scanf("%d", a + i); for (int i = n; i >= 0; --i) if (b[i] == -1) { tot = 1; while (tot <= i) tot <<= 1; tot--; o = tot ^ i; s += tot * 2; b[i] = o; b[o] = i; } printf("%lld\n", s); for (int i = 0; i <= n; ++i) printf(i == n ? "%d\n" : "%d ", b[a[i]]); } return 0; }   » 20 months ago, # | +19 Thanks to the problemsetters, the problems were really nice (D in particular). How to solve C, G, J and K? •  » » 20 months ago, # ^ | +65 There's an editorial prepared by the problemsetters. •  » » » 20 months ago, # ^ | ← Rev. 2 → +10 I had been looking for the editorial since the end of the contest, but couldn't seem to find it anywhere. Do you mind sharing how you found it? Most of the previous GP editorials were usually posted in the respective CF announcements, but this one doesn't seem to have any official announcement post.Thanks for sharing the editorial btw. •  » » » » 20 months ago, # ^ | +26 Well... In fact, the contest was used in Petrozavodsk Camp, and it was shared by the problemsetters during the camp. •  » » 20 months ago, # ^ | -75 baaki sab ban gaya bhai? •  » » » 20 months ago, # ^ | +6 Tere ban gaye kya?  » 20 months ago, # | +36 Thanks to problem F! I learned something new. Here is a tricky case not in the judge tests (it's OK as I know it's not easy to create a strong cases): 1 10 9 100 3 -63 4 We have$E = \{ (3,1), (6,2), (9,3), (12,4), (15,5) \}\$ and the answer should be 701423582.My first attempt used quadtree-like DFS but I only checked the center of the ellipse and the boundary lattice points of the square to decide that they have any intersection. It is not correct for thin ellipses.
•  » » 20 months ago, # ^ |   +38 As the problem setter, thanks for caring about problem F!
 » 20 months ago, # |   +30 The contest is available in GYM now :)