Thank you for participating! We hope you enjoyed the problems.
Idea: _ja Preparation: _ja & quacksaysduck
Tutorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int x = 10000, y = 0;
for (int i = 0; i < n; ++i) {
int z;
cin >> z;
x = min(x, z), y += x;
}
cout << y << '\n';
}
return 0;
}
Idea: quacksaysduck Preparation: _ja & quacksaysduck & Boboge
Tutorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), c(n);
for (int i = 0; i < n; i++) cin >> a[i];
set<int> s;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x);
}
bool y = true;
for (int i = 0; i < n; ++i) {
auto it = s.lower_bound(a[i]);
if (it == s.end()) {
y = false;
break;
}
c[i] = *it;
s.erase(it);
}
if (!y) {
cout << -1 << '\n';
continue;
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (c[i] > c[j]) {
ans++;
}
}
}
cout << ans << '\n';
}
return 0;
}
Idea: quacksaysduck Preparation: Boboge
Tutorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void run() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
i64 ans = 0;
for (int i = 0; i < n; ++i) {
if (ans > a[i]) {
ans += a[i];
} else {
ans = a[i];
}
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
run();
}
return 0;
}
Idea: zeemanz Preparation: __baozii__
Tutorial
Tutorial is loading...
Implementation(python)
for _ in range(int(input())):
n = int(input())
a = [1, 0, 0]
x = 0
ans = 0
pre = ""
y = 0
for c in input():
if c == "0":
x -= 1
else:
x += 1
x %= 3
if c == pre:
y = 1
else:
y += 1
pre = c
ans += sum(a) - a[x]
a[x] += 1
ans -= (y - 1) // 2
print(ans)
2237E - Permutation Commutation
Tutorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
void run(int testCase) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i]--;
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
if (b[i] != -1) {
b[i]--;
}
}
vector<int> vis(n);
for (int i = 0; i < n; ++i) {
if (b[i] != -1 and !vis[i]) {
int j = i;
while (true) {
if (vis[j]) break;
vis[j] = 1;
if (b[a[j]] == -1) {
b[a[j]] = a[b[j]];
} else if (b[a[j]] != a[b[j]]) {
cout << "NO\n";
return;
}
j = a[j];
}
}
}
vector<int> cnt(n);
for (int i = 0; i < n; ++i) {
if (b[i] == -1) continue;
cnt[b[i]]++;
}
for (int i = 0; i < n; ++i) {
if (cnt[i] > 1) {
cout << "NO\n";
return;
}
}
vector<int> vis1(n), vis2(n);
vector<vector<int>> cycle1(n + 1), cycle2(n + 1);
for (int i = 0; i < n; ++i) {
if (b[i] == -1 and !vis1[i]) {
int j = i, len = 0;
while (!vis1[j]) {
vis1[j] = 1;
len++;
j = a[j];
}
cycle1[len].push_back(i);
}
}
for (int i = 0; i < n; ++i) {
if (cnt[i] == 0 and !vis2[i]) {
int j = i, len = 0;
while (!vis2[j]) {
vis2[j] = 1;
len++;
j = a[j];
}
cycle2[len].push_back(i);
}
}
for (int len = 1; len <= n; ++len) {
for (int i = 0; i < cycle1[len].size(); ++i) {
int x = cycle1[len][i], y = cycle2[len][i];
while (b[x] == -1) {
b[x] = y;
x = a[x];
y = a[y];
}
}
}
cout << "YES\n";
for (int i = 0; i < n; ++i) {
cout << b[i] + 1 << " \n"[i == n - 1];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
for (int t = 1; t <= T; ++t) {
run(t);
}
return 0;
}
Idea: StarSilk Preparation: StarSilk & Sugar_fan
Tutorial
Tutorial is loading...
Implementation
#include<bits/stdc++.h>
using namespace std;
int a[500000], pref[500001], suf[500001], dpvl[500001], inf = 1000000000;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T, n, m, i, c;
for (cin >> T; T > 0; T--) {
cin >> n >> m;
for (i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
for (i = 0; i <= n; i++) {
pref[i] = -inf;
suf[i] = -inf;
dpvl[i] = -inf;
}
pref[0] = 0;
for (i = 0; i < n; i++) {
c = suf[i];
if (i - a[i] >= 0) {
c = max(c, dpvl[i - a[i]]);
c = max(c, pref[i - a[i]]);
}
c++;
pref[i + 1] = max(pref[i], c);
suf[i + 1] = max(suf[i + 1], suf[i]);
if (i - a[i] >= 0)dpvl[i - a[i]] = max(dpvl[i - a[i]], c);
if (i - a[i] + m <= n)suf[i - a[i] + m] = max(suf[i - a[i] + m], c);
}
cout << n - max(suf[n], 0) << '\n';
}
return 0;
}
Tutorial
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
#define sz(a) (int)(a).size()
using namespace std;
using i64 = long long;
string type;
constexpr int P = 110;
constexpr int N = 1e6;
constexpr int sz_v = (1 << 18);
vector<int> ps, pks, v;
array<int, N + 1> idx;
void init() {
vector<int> max_p(N + 1);
max_p[1] = 1;
for (int i = 2; i <= N; ++i) {
if (max_p[i] == 0) {
ps.push_back(i);
for (int j = i; j <= N; j += i) {
max_p[j] = i;
}
}
}
ps.resize(P);
for (int p: ps) {
int x = p;
while (x * p <= N) x *= p;
pks.push_back(x);
}
for (int i = 1; i <= N and sz(v) < sz_v; ++i) {
if (max_p[i] <= ps.back()) {
v.push_back(i);
}
}
assert(sz(v) == sz_v);
for (int i = 0; i < sz(v); ++i) idx[v[i]] = i;
}
void run1() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> b;
for (int pk: pks) b.push_back(pk);
vector<int> bits;
for (int i = 0; i < n; ++i) {
for (int j = 19; j >= 0; --j) {
bits.push_back(a[i] >> j & 1);
}
}
while (sz(bits) % 18) bits.push_back(0);
for (int i = 0; i < sz(bits); i += 18) {
int now = 0;
for (int j = 0; j < 18; ++j) {
now *= 2;
now += bits[i + j];
}
b.push_back(v[now]);
}
int k = sz(b);
cout << k << '\n';
for (int i = 0; i < k; ++i) cout << b[i] << ' ';
cout << '\n';
}
void run2() {
int n, k;
cin >> n >> k;
auto ask = [&](int i, int j) {
assert(i != j);
cout << "? " << i + 1 << ' ' << j + 1 << endl;
int g;
cin >> g;
return g;
};
vector<int> bits;
for (int i = P; i < k; ++i) {
int x = 1;
for (int j = 0; j < P; ++j) {
int g = ask(i, j);
x *= g;
}
int now = idx[x];
for (int j = 17; j >= 0; --j) {
bits.push_back(now >> j & 1);
}
}
vector<int> a(n);
for (int i = 0, j = 0; i < n; ++i, j += 20) {
int now = 0;
for (int x = 0; x < 20; ++x) {
now *= 2;
now += bits[j + x];
}
a[i] = now;
}
cout << "!";
for (int i = 0; i < n; ++i) cout << ' ' << a[i];
cout << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
init();
cin >> type;
int T = 1;
cin >> T;
while (T--) {
if (type == "first") {
run1();
} else {
run2();
}
}
return 0;
}
Idea: StarSilk Preparation: StarSilk & Sugar_fan
Tutorial
Tutorial is loading...
Implementation
#include<bits/stdc++.h>
using namespace std;
vector<int> line[100000];
int dfn[100000], siz[100000], fa[100000], wp[100000], tp[100000], dep[100000], cdfn;
void dfs1(int t, int f) {
vector<int>::iterator it;
int mx = -1;
fa[t] = f;
siz[t] = 1;
wp[t] = -1;
for (it = line[t].begin(); it != line[t].end(); it++) {
if ((*it) == f)continue;
dep[*it] = dep[t] + 1;
dfs1(*it, t);
siz[t] += siz[*it];
if (siz[*it] > mx) {
mx = siz[*it];
wp[t] = *it;
}
}
}
void dfs2(int t, int f) {
vector<int>::iterator it;
dfn[t] = cdfn;
cdfn++;
if (wp[t] == -1)return;
tp[wp[t]] = tp[t];
dfs2(wp[t], t);
for (it = line[t].begin(); it != line[t].end(); it++) {
if ((*it) == f)continue;
if (*it == wp[t])continue;
tp[*it] = *it;
dfs2(*it, t);
}
}
map<int, int> mp, sg;
void access(int p) {
map<int, int>::iterator it;
int x;
it = sg.upper_bound(p);
it--;
x = (*it).second;
sg[p] = x;
}
int chkmap(int c, int vl) {
map<int, int>::iterator it;
int d;
while (1) {
it = mp.upper_bound(vl);
if (it == mp.begin())break;
it--;
d = min((*it).second, c);
c -= d;
(*it).second -= d;
if ((*it).second == 0)mp.erase(it);
if (c == 0)break;
}
return c;
}
int upd(int l, int r, int p) {
int ans = 0, lst, lvl;
map<int, int>::iterator it;
access(l);
access(r);
lst = l;
lvl = sg[l];
while (1) {
it = sg.upper_bound(l);
ans += chkmap((*it).first - lst, lvl);
lst = (*it).first;
lvl = (*it).second;
if ((*it).first == r)break;
sg.erase(it);
}
sg[l] = p;
mp[p] += r - l - ans;
return ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T, n, m, q, i, u, v, p;
long long ans;
for (cin >> T; T > 0; T--) {
cin >> n >> m >> q;
for (i = 0; i < n - 1; i++) {
cin >> u >> v;
line[u - 1].push_back(v - 1);
line[v - 1].push_back(u - 1);
}
dep[0] = 0;
dfs1(0, -1);
cdfn = 0;
tp[0] = 0;
dfs2(0, -1);
sg[0] = -1;
sg[n] = -1;
for (i = 0; i < m; i++) {
cin >> p;
p--;
access(dfn[p] + 1);
sg[dfn[p]] = 0;
}
mp[0] = m;
ans = 0;
for (i = 1; i <= q; i++) {
u = p;
cin >> p;
p--;
p = (p + ans) % n;
v = p;
while (1) {
if (tp[u] == tp[v]) {
if (dep[v] > dep[u])swap(u, v);
ans += upd(dfn[v], dfn[u] + 1, i);
break;
}
if (dep[tp[v]] > dep[tp[u]])swap(u, v);
ans += upd(dfn[tp[u]], dfn[u] + 1, i);
u = fa[tp[u]];
}
cout << ans << ' ';
}
cout << '\n';
for (i = 0; i < n; i++)line[i].clear();
mp.clear();
sg.clear();
}
return 0;
}
2237I1 - DBFS Order (Easy Version)
Idea: StarSilk Preparation: StarSilk & Sugar_fan & Boboge
Tutorial
Tutorial is loading...
2237I2 - DBFS Order (Hard Version)
Idea: StarSilk Preparation: StarSilk & Sugar_fan & Boboge
Tutorial
Tutorial is loading...
Implementation
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
vector<int> line[3000];
string s;
long long dp[4][3000][3001], dpc[4][3000][3001], tdp[4][3001], tdpc[4][3001];
int dep[3000], vis1[3000], vislink[3000];
void merge(int u, int v, int pu, int pv, int pt) {
int i, j;
for (i = 0; i <= dep[u]; i++) {
for (j = 0; j <= dep[v]; j++) {
tdp[pt][max(i, j)] = (tdp[pt][max(i, j)] + dp[pu][u][i] * dp[pv][v][j]) % mod;
if (i <= j)tdpc[pt][j] = (tdpc[pt][j] + dp[pu][u][i] * dpc[pv][v][j]) % mod;
if (i > j)tdpc[pt][i] = (tdpc[pt][i] + dpc[pu][u][i] * dp[pv][v][j]) % mod;
}
}
}
void dfs(int t) {
vector<int>::iterator it;
int i, j, p, x, y, r0 = 0;
long long vl;
dp[0][t][0] = 1;
dep[t] = 0;
vis1[t] = 0;
vislink[t] = 0;
for (it = line[t].begin(); it != line[t].end(); it++) {
if (s[*it] == '0')r0++;
}
for (it = line[t].begin(); it != line[t].end(); it++) {
dfs(*it);
if (s[*it] == '0')r0--;
merge(t, *it, 0, 0, 0);
if (s[*it] == '1') {
merge(t, *it, 3, 1, 2);
merge(t, *it, 3, 1, 3);
} else {
merge(t, *it, 2, 1, 2);
merge(t, *it, 3, 1, 3);
}
if (vis1[t] == 0 && r0 == 0 && vislink[*it]) {
if (vislink[t] == 0) {
vislink[t] = 1;
for (i = 0; i <= dep[*it]; i++) {
tdp[2][i] = (tdp[2][i] + dp[2][*it][i]) % mod;
tdpc[2][i] = (tdpc[2][i] + dpc[2][*it][i]) % mod;
tdp[3][i] = (tdp[3][i] + dp[3][*it][i]) % mod;
tdpc[3][i] = (tdpc[3][i] + dpc[3][*it][i]) % mod;
}
} else {
for (i = 0; i <= dep[*it]; i++) {
tdp[2][i] = (tdp[2][i] + dp[2][*it][i]) % mod;
tdpc[2][i] = (tdpc[2][i] + dpc[2][*it][i]) % mod;
tdp[3][i] = (tdp[3][i] + dp[2][*it][i]) % mod;
tdpc[3][i] = (tdpc[3][i] + dpc[2][*it][i]) % mod;
if (s[*it] == '1') {
tdp[2][i] = (tdp[2][i] + dp[1][*it][i]) % mod;
tdpc[2][i] = (tdpc[2][i] + dpc[1][*it][i]) % mod;
tdp[3][i] = (tdp[3][i] + dp[1][*it][i]) % mod;
tdpc[3][i] = (tdpc[3][i] + dpc[1][*it][i]) % mod;
}
}
}
}
vis1[t] |= vis1[*it];
dep[t] = max(dep[t], dep[*it]);
for (p = 0; p < 4; p++) {
for (i = 0; i <= dep[t]; i++) {
dp[p][t][i] = tdp[p][i];
dpc[p][t][i] = tdpc[p][i];
tdp[p][i] = 0;
tdpc[p][i] = 0;
}
}
}
if (s[t] == '0') {
dep[t]++;
return;
}
for (i = 0; i <= dep[t]; i++) {
tdp[0][i + 1] = (tdp[0][i + 1] + dp[0][t][i]) % mod;
tdpc[0][i + 1] = (tdpc[0][i + 1] + dpc[0][t][i]) % mod;
}
vl = 0;
for (i = 0; i <= dep[t]; i++) {
vl = (vl + dp[2][t][i]) % mod;
vl = (vl + mod - dpc[2][t][i]) % mod;
}
tdpc[0][1] = (tdpc[0][1] + vl) % mod;
dep[t]++;
vislink[t] = 1;
if (s[t] == '1') {
vis1[t] = 1;
for (i = 0; i <= dep[t]; i++) {
dp[0][t][i] = tdp[0][i];
dpc[0][t][i] = tdpc[0][i];
dp[1][t][i] = tdp[0][i];
dpc[1][t][i] = tdpc[0][i];
dp[2][t][i] = 0;
dpc[2][t][i] = 0;
dp[3][t][i] = 0;
dpc[3][t][i] = 0;
}
} else {
for (i = 0; i <= dep[t]; i++) {
dp[0][t][i] = (dp[0][t][i] + tdp[0][i]) % mod;
dpc[0][t][i] = (dpc[0][t][i] + tdpc[0][i]) % mod;
dp[1][t][i] = tdp[0][i];
dpc[1][t][i] = tdpc[0][i];
dp[3][t][i] = dp[2][t][i];
dpc[3][t][i] = dpc[2][t][i];
dp[2][t][i] = (dp[2][t][i] + tdp[0][i]) % mod;
dpc[2][t][i] = (dpc[2][t][i] + tdpc[0][i]) % mod;
}
}
for (i = 0; i <= dep[t]; i++) {
tdp[0][i] = 0;
tdpc[0][i] = 0;
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T, n, i, j, p, c;
long long ans;
for (cin >> T; T > 0; T--) {
cin >> n >> s;
s = '1' + s;
for (i = 0; i < n; i++) {
cin >> c;
for (j = 0; j < c; j++) {
cin >> p;
line[i].push_back(p - 1);
}
}
for (p = 0; p < 4; p++) {
for (i = 0; i < n; i++) {
for (j = 0; j <= n; j++) {
dp[p][i][j] = 0;
dpc[p][i][j] = 0;
}
}
}
dfs(0);
ans = 0;
for (i = 0; i <= dep[0]; i++) {
ans = (ans + dp[0][0][i]) % mod;
ans = (ans + mod - dpc[0][0][i]) % mod;
}
cout << ans << '\n';
for (i = 0; i < n; i++)line[i].clear();
}
return 0;
}
Auto comment: topic has been updated by Boboge (previous revision, new revision, compare).
D absolutely fried me man... Im quite happy with my +16 tho!
cheater
As stated in the official editorial, $$$a$$$ is valid if and only if $$$a_1=1,a_n=m$$$, and for each $$$1\leq i \lt n$$$, at least one of these is true:
$$$a_{i+1}=a_i+1,$$$
$$$a_i=m,$$$
$$$a_{i+1}=1.$$$
Let $$$dp[i][j]$$$ be the maximum number of elements in the length $$$i$$$ prefix of $$$a$$$ that do not need to be changed such that $$$a_i=j$$$ and the above conditions hold. The above conditions give us the following transitions:
$$$dp[i+1][1]:=max_k (dp[i][k])$$$
$$$dp[i+1][j]:=max(dp[i][j-1],dp[i][m])$$$ for $$$j \gt 1$$$
$$$dp[i+1][a_{i+1}] := dp[i+1][a_{i+1}]+1$$$
We can split the second transition into to two steps:
2a. $$$dp[i+1][j]:=dp[i][j-1]$$$
2b. $$$dp[i+1][j]:=max(dp[i+1][j],dp[i][m])$$$
Store $$$dp[i]$$$ in a deque. Also store the maximum value of $$$dp[i]$$$ in a variable $$$mx$$$.
To transition from $$$dp[i]$$$ to $$$dp[i+1]$$$, we can insert $$$mx$$$ at the beginning of $$$dp[i]$$$ and pop the last element. This shifts the remaining elements to the right, which handles transitions $$$1$$$ and $$$2a$$$. For transition $$$2b$$$, we store the value of $$$dp[i][m]$$$ in a variable $$$mn$$$ and lazily update $$$dp[i+1][j]:=max(dp[i+1][j],mn)$$$ whenever we want to access $$$dp[i+1][j]$$$. When doing transition $$$3$$$, make sure to update the value of $$$mx$$$ accordingly.
Since $$$dp[i+1]$$$ only depends on $$$dp[i]$$$, we can do all of these transitions in-place on the deque. After computing $$$dp$$$, the answer is just $$$n-dp[n][m]$$$. Since each transition is $$$O(1)$$$, the solution runs in $$$O(n)$$$.
Code: 379434014
Great solution!
Amazing solution!!!
very cool
Amazing!
Wonderful solution
.
I went to sleep early =(
in D, because our final value is either +1 or -1 we can deduce that the total sum is
3x+1or3x-1.After this, noting that alternating strings don't work or that there has to be at least one pair of adjacent equal characters suffices. My implementation
can you explain the part of ur code where you count the correct substrings ~~~~~ int r = n, ans = n; for(int i = n — 1; i > 0; i--) { if(s[i — 1] == s[i]) { while(r > i) { f[pref[r--]]++; } } int here = f[(pref[i — 1] + 1) % 3] + f[(((pref[i — 1] — 1) % 3) + 3) % 3]; ans += here; } ~~~~~
I maintain a pointer
rwhich stays at positionisuch that $$$ s_i = s_{i-1}$$$ and if I get to suchi, I decrease my pointer to that point while updating the map. Finally, as I said above the valid sum is $$$ 3x \pm 1 $$$, I am just calculating those values in the variablehere. $$$ 3x \pm 1 \equiv \pm 1 \mod 3 $$$man i got cooked by B so bad
Exactly I was like it's just sorting the array but how does an O(N^2) solution will be accepted and today's morning i submit and it accepted.
you so close to 1200 bro gl
man i got cooked by D so badly
D led to my -73 =(
For me it was a huge gap between C and D. A-C took <20 minutes, but was unable to solve D at all, even on next day. With so many problems and so much time for this contest, I wish there could be more solvable problems...
C is hard too. =(
But it's a good idea that run a code which is slow but right to seek the rule.
Really enjoyed the contest And problem D is fire ,,, happy to solve it
Is problem B — 2237B - Annoying the Ghost significantly harder if the problem is to change from array $$$b$$$ to $$$a$$$, instead of $$$a$$$ to $$$b$$$?
You're right! I still don't fully understand the solution yet. In the last contest, I only solved Problem A, and I still don't understand the solution for Problem B.
You can check my submission it it simpler to understand i just thought greedily replacing a[i] if(a[i] > b[i]) with a[j] that <= b[i] by performing swaps should do the work because it is optimal to do so like if a1<b1 a2<b2 and a3<b3 it is always possible to make b[i] from a[i].
thanks bro nice solution. i understand the problem bcz of your solution.i am sad i am stuck at this rating :(
B is extremely difficult... ...
Is there a way to solve D using DP, trying to store the count of beautiful substrings ending at 0 or 1, and also storing bad/alternating substrings, then adding them up for each index?
Plenty of edge cases arise. I tried this approach over and over but was always able to think of a case where it fails.
Yes, there is a way for D using just DP and I did exactly that in the contest. But the issue is I used 7 DP arrays.
Nevertheless, here is my solution.
Let $$$dp_{x}[i]$$$ denote the number of substrings ending at i, such that it is non alternating and the difference of counts of $$$0$$$ and $$$1$$$ is $$$x \space mod \space 3$$$. ($$$x = 0,1,2$$$)
Let $$$dp_{xy}[i]$$$ denote the number of substrings ending at i, such that they are alternating and they start at $$$x$$$ and end at $$$y$$$. ($$$xy = 00,01,10,11$$$)
Then loop through the string and at each character try adding it to the previous substrings. Just keep in mind that a single character is considered an alternating substring.
Here is my code for reference : 379415083
Thank you for the solution. If you don't mind, can you please share how you arrived, or why you went in the direction of taking the difference of counts? Taking the difference of counts wasn't even remotely in my thinking space, when trying to solve the problem. I kept trying to find the count at each index by checking if adding a 0 or 1 to the previous subarrays will yield a beautiful one, and adding them with half the alternating subarrays.But I couldn't go in the direction of taking the counts, as I kept thinking count of each element won't matter since we're taking a subarray.
try to set up an equation to just observe the initial and final (potential/target) states
we have two kinds of operations (-2, +1) and (-1, +2) on the pair (n, m) representing the number of 1s and 0s. say we did x and y of each operation and reached the final state of a single number lets say '1' for now.
n-2x + y = 1m-2y + x = 0n-m-1 = 3 * (x-y) , meaning n-m = 1 mod 3.
similarly for reaching a final state of '0' we get n-m = 2 mod 3.
This means we can only reach final state of a single number of we have n-m != 0 modulo 3.
Setting up the equations and playing around made me stumble upon this
Sorry for the comment, I completely missed that given b is sorted.
Array b is sorted
Thank you, Got it!
Array b is sorted in ascending order
note that array b is strictly increasing
it makes no sense that people with O(n^2) are passing B, those testcases are way too weak
You do realise that that is the intended time complexity?
Its intended, If thats not the case, then B should move down to maybe C or D.
n<=2000 it has to pass
It's ok to let O(n^2) pass that this problem is put in B.
not relevant to the solution of D but in D, is it true that for any binary string, if it is beautiful then it reduces to a unique value? Intuitively feels like that should be the case, but not sure how to prove it.
Yes thats true(if I understood your question correctly) and here is my proof:
Lets say $$$f^n(0)$$$ is the quantity of $$$0$$$ in some string $$$s$$$ after $$$n$$$ operations. The same with $$$f^n(1)$$$. It is easy to see that $$$f^{n-1}(1)-f^{n-1}(0) \equiv f^n(1)-f^n(0) \pmod3$$$(because -1-2 is 0 and 2-(-1) is also 0 by mod 3). So, we are assuming that string is beautiful so lets say that after $$$k$$$ operations we will end up with one symbol(WLOG lets say it is 1). So: $$$f^0(1)-f^0(0) \equiv f^1(1)-f^1(0) \equiv ... \equiv f^{k}(1)-f^{k}(0) \pmod3$$$
But we know that since we only have one 1 and zero 0 at the end after $$$k$$$ operations, $$$f^{k}(1)-f^{k}(0)=1 \pmod3$$$
If there was some combination where we can reach only 0 at the end after some $$$m$$$ operations, then with the same logic $$$f^0(1)-f^0(0) \equiv f^1(1)-f^1(0) \equiv ... \equiv f^{m}(1)-f^{m}(0) \equiv 0 -1 \equiv 2 \pmod3$$$
So we have $$$1 \equiv f^0(1)-f^0(0) \equiv 2 \pmod3$$$ which is not true
In less formal terms: Every single move you make changes the value of (count of 1s) — (count of 0s) by either $$$+3$$$ or $$$-3$$$. This means the remainder of this difference when divided by 3 never changes. Since a final 1 leaves a remainder of 1, and a final 0 leaves a remainder of 2, a string can never reduce to both. The final symbol is strictly predetermined from the very beginning.
Feel free to ask if anything is unclear
Well put
Heyy
idk if i have enough knowledge regarding this but idk i noticed some of my known friends whom i know personally solving D in like 15 mins who are new to CF like me. I dont wanna accuse someone but i got suspicious and after contest tried GPT and it gave the correct passable code logic within like 1 min.
Can something be done because i was bummed out seeing 4k submissions on D during contest(though i know here div 1 ppl were there too this time) . i do agree that most would have independently solved it and me finding it tough isnt a benchmark for saying that others cant do it quickly but just in case can any measures be taken??
Auto comment: topic has been updated by Boboge (previous revision, new revision, compare).
Oh boy, I don't remember having so many alternative solutions
After noticing that we do the leftmost operation, we know the fate of every number: it can be assumed to go to the right while it's greater than the next number, and we can assume that it will "absorb" all the numbers it goes through. For example, in the array
[3] 2 4 5 15the number3will go through2thus becoming5, then through4and then through5, so after considering this number alone, the array will be2 4 5 [14] 15. Therefore, it's sufficient to find for each number how far it'll go and take the maximum of all the corresponding subsegment sums.Now that I write it I realize that it can be done easier, but what I did was go from the end and maintain the stack of current prefix maxima or something and then for each number repeatedly binary search in this stack the answer to the question "ok we are currently $$$x$$$, what is the next number at least $$$x$$$ that we have a chance of not absorbing?", so we'll have to only do it like $$$\log nW$$$ times.
Actually I think same as here, but I noticed that if we consider
dp[i]being the max number of unchanged positions so that the last number isiafter we considered some prefix, then to compute thisdpafter we consider the next number in the input it's sufficient to shift the values (i.e. makenew dp[i + 1] := dp[i]), take a couple of subsegment maxima and then do a couple of global remaxes, for which we can create a segment tree with $$$n + m$$$ leaves and do all standard remaxing stuff. For shifting, we just say that the subsegment of leaves corresponding to ourdpmoves left by 1 position every time.I used first 150 primes, not 110, and then just noticed that if we denote $$$N = 10^6$$$ and $$$M$$$ to be the count of 150-smooth numbers, then $$$N^9 \lt M^10$$$ therefore we can encode each block of $$$k \leq 9$$$ numbers from $$$0$$$ to $$$N - 1$$$ with a block of $$$k+1$$$ numbers from $$$0$$$ to $$$M - 1$$$ by just converting a number from one base to another via repeated multiplying and adding.
For the record, I think it's very cool and I generally liked the problems as well, so thank you for the contest! (if only it had been on a weekend though)
1k+ people solved E (╥﹏╥)
E isn't hard but code is too long
How can I compute inversions in O(N log N) in problem B?
Merge sort
Use PBDS or BIT (Fenwick Tree).
Tysm
When testing the round, I found some optimizations that can be done on problem G to reduce the array length to $$$\left \lceil \frac{10n}{9} \right \rceil + 55$$$ and query count to $$$55n$$$, I think it's a pretty cool challenge to think about. Here's my solution:
The general strategy is to construct some set of integers $$$S$$$, such that the sequence $$$T(x)$$$ defined by $$$T(x)_i = \gcd(x, S_i)$$$ has at least $$$2^{18}$$$ different values for $$$1 \leq x \leq 10^6$$$. We wish to minimise $$$|S|$$$.
Instead of constructing $$$S$$$ to be the largest power $$$\leq 10^6$$$ for the first few primes $$$p$$$, we change our strategy for primes larger than $$$k$$$ (after some experimenting, $$$k=38$$$ was a good value for this threshold). For these primes, we add the products of adjacent primes into $$$S$$$ instead. The first few elements in $$$S$$$ of this form would look like $$$41 \cdot 43, 47 \cdot 53, 59 \cdot 61$$$ and so on.
While we are no longer able to use numbers which are multiples of $$$p^2$$$ for primes $$$p \gt 38$$$, we are able to cover much more prime factors, which becomes more efficient than the initial strategy for larger primes. Finally, to optimize slightly further I grouped some of the primes into triples instead of pairs, after playing around with it a little I managed to get $$$|S|$$$ to be $$$55$$$.
I'm quite sure $$$|S|$$$ can be pushed to be even smaller, if anyone knows how to further optimize the solution I'd like to hear!
I only accepted problem A,so I think I don't have enough programming level to take part in this contest.
D is such a cool problem.
OK, i couldnt solve it so i solved C instead lol
i dont get editorial of B i see if we map a1 to bj instead of bi < bj and say some other element am comes for bi then then am <= bi < bj which shows that am is also a valid candidate for bj so a better move is to do a1 for bi (as it reduces the cost)
i also dont understand what if for m the cost is less?
waw , Mate, D really gave me a proper thrashing
DAMN , although C is shit about D lol
Who agrees with me that B is harder than C and D?
Bro B is not that hard, is harder than C but not than D
Bro why does that G solution look so cracked, like how would you even come up with that.
hmm let's create runtwice with gcd.
$$$2n$$$ solution is clear.
this idea with subsets of primes is a bit harder but also clear.
let's merge those two!
It's much easier to come up with the idea if you try to enumerate solutions according to the constraints, as 150 points to first 150 primes and 10/9 leads to 9 elements in a row using 10 numbers to encode, then you can realize that 3e5^10 > 1e6^9 and figure out the solution
B was cool :)
Hello brother can u please help me understand why each a[i] should be increased to smallest b[j] greater than a[i] ? After a lot of try, still this couldn't make sense to me.
Because assigning each a[i] to the smallest available b[j] with b[j] >= a[i] leaves the larger b values for larger a's that may not fit anywhere else, so it never reduces the set of feasible future assignments and avoids blocking a valid matching.
guys why didnt my score change????????
D and E are great, almost among the best problems I've encountered on this platform!
B is such a cool problem
Hello brother can u please help me understand why each a[i] should be increased to smallest b[j] greater than a[i] ? After a lot of try, still this couldn't make sense to me.
Could solve 3 in this div1+2 as well
Did anyone solve D with DFA? It was nice building a DFA to solve an easy problem that could be solved with simpler observations. :V
Does anyone have a simpler explanation for E? I didn't understand what the editorial means by "cycles of a".
same that statement was not obvious at all heres a explaination/proof
Every permutation can be broken into disjoint "cycles". If you think of the permutation like a functions that maps (1-indexed) $$$i$$$ to $$$a_i$$$, then if you apply the permutation to itself, elements of each cycle will trade places with eachother.
For example the permutation 2 1 6 3 5 4 can be broken into the cycles (1, 2) (3 4 6) and (5) because 1 maps to 2 and 2 maps to 1, 5 maps to 5, etc.
The problem says if permutations $$$A$$$ and $$$B$$$ commute, than $$$A(B(i)) = B(A(i))$$$ for all $$$i$$$. if some element $$$j$$$ is in a cycle of length $$$n$$$ in $$$A$$$ then
$. therefore if $$$j$$$ is in a cycle of length n, then $$$B_j$$$ is also in a cycle of length n
ou shi
Thank you. I agree this should have been justified in the editorial.
For problem B, Can anyone please explain why each a[i] should be increased to smallest b[j] greater than a[i] ? After a lot of try, still this couldn't make sense to me.
Thanks for the contest! In case it's helpful to others, I thought I'd write down some thoughts on my solution to G and its motivation.
A natural first strategy to attempt is to write down the array $$$a$$$, then write down some other numbers that can be used alongside the GCD operation to decode it. One problem with any strategy of this shape, though, comes from handling inputs consisting of large primes. If the array $$$a$$$ consists of $$$n$$$ large primes, then each of these primes must appear twice in $$$b$$$ for it to be a possible output of the GCD operation, so for such an input, $$$b$$$ would require at least $$$2n$$$ elements, which is infeasible.
This indicates that rather than writing down $$$a$$$ itself, we'll need to encode its elements in some more convenient way, then decode them later. That motivates thinking about what numbers are easy to identify in $$$b$$$ using the provided GCD elements. One natural idea here is that if we fix an element of $$$b$$$ to be the largest power of some prime $$$p$$$ less than $$$10^6$$$, we can take the GCD of any other element of $$$b$$$ with this one to count the times $$$p$$$ appears in its prime factorization. So, if we use powers of the 150 smallest primes as the 'spare' elements of $$$b$$$, we can use them to compute the exact values of all other elements of $$$b$$$, provided those elements don't have any prime factors outside of these 150 smallest primes.
By writing a brute force, we can find that there are just over $$$3 \cdot 10^5$$$ numbers up to $$$10^6$$$ that have sufficiently small prime factors and can thus be identified exactly if we put them in $$$b$$$. Say the exact count of such values is $$$k$$$. By writing down a map from these $$$k$$$ values to the first $$$k$$$ nonnegative integers, we can imagine that instead of using the GCD queries described in the problem, we're allowed to write down $$$\frac{10n}{9}$$$ values up to $$$k$$$ in $$$b$$$, and the second player receives those exact numbers and needs to restore $$$a$$$.
A reasonable starting point from here is to write down $$$a_i \bmod k$$$ for all $$$i$$$. Then, for every nine elements of $$$a$$$, we can add one extra element to $$$b$$$, and we need to use this element to restore the values of $$$\left\lfloor \frac{a_i}{k} \right\rfloor.$$$ But given $$$k \approx 3 \cdot 10^5$$$, this quotient has to be between $$$0$$$ and $$$3$$$, so there are $$$4^9$$$ possible sequences of quotients for a series of nine elements of $$$a$$$. Since $$$4^9 \lt k$$$, we can encode all nine of these quotients in a single element of $$$b$$$, e.g. by writing down a nine-digit number in base four. This is enough to solve the reduced problem, so we're done!
A mildly amusing aside: I was able to overkill F using segment tree beats (the first time I've actually used segtree beats to implement a problem), which saved me from thinking harder about how to use prefix minima/maxima to optimize the DP transitions :)
I have another idea:
We will encode $$$9$$$ consecutive numbers in the array $$$a$$$ to $$$10$$$ consecutive numbers in the array $$$b$$$.
Let $$$base = 10^6 + 1$$$, and define $$$c_i = a_i * base^0 + a_{i + 1} * base^1 + ... + a_{i + 8} * base^8$$$ and we can change every $$$c_i$$$ $$$(i = 9 * x + 1$$$, there are $$$\lceil n/9 \rceil$$$ such $$$c_i)$$$ to other form, here I chose base $$$252000$$$ (we need a base of at least $$$\sqrt[10]{base^9} \approx 251189$$$ so it fits in $$$10$$$ digits).
I chose $$$252000$$$ representatives of the form $$$2^x * 3^y * p_1 * p_2 * ...$$$ (I tried $$$2^x * p_1 * p_2 * ...$$$ and $$$p_1 * p_2 * ...$$$ but they don't have enough numbers less than $$$10^6$$$ to represent base $$$252000$$$) with $$$p_i$$$s are the first $$$140$$$ primes greater than $$$3$$$ and they have to be pairwise distinct. I'm pretty sure $$$140$$$ is somewhat large, it can be reduced further but it's not necessary because we only used $$$k = \lceil 10n/9 \rceil + 142$$$.
We transformed a 9-digit number in base $$$10^6 + 1$$$ to a 10-digit number in base $$$252000$$$, Quack can just get the array $$$b$$$ in $$$\lceil 10n/9 \rceil * 140$$$ queries and decode to $$$a$$$ easily.
I almost got that during the contest, but my base conversion code was stupidly bugged :( looking forward to see more interactive/communication problems soon.
Implementation: 379431426
the prove of greedy problem on codeforces is terrible
Nice problems
Is there a typo in the tutorial for B? It isn’t necessarily true that a_m <= a_1, right?
Can anyone explain 2237C plz
Hi in c if we remove constraint of adjacent and swap any two position according to rule. can anyone suggest the way to the modified problem.
Rating problem D at 1500 is insane i guess, man that problem is tough.
d why the number of odd substrings for aletranting string is
⌊y−1/2]?))Problem I is a really great problem! The DP part is super detail-oriented. Fully digesting it really puts your understanding and implementation skills to the test.