Hope you all enjoyed the problemset! Editorials to problems H and I are not ready yet, we will add them as soon as possible. We apologize for weak pretests and easy problems for top participants.

By the way, solution authors did not necessarily prepare the problems. The solutions were chosen at random.

**UPD.** Editorials for H and I are ready! Wish you all productive upsolving and high ratings!

**Tutorial**

**Solution (kefaa2)**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
int tst;
cin >> tst;
while (tst--) {
int n;
cin >> n;
cout << (n + 1) / 10 << '\n';
}
}
```

Idea: Errichto Preparation: Will not be revealed for now because we care for his/their safety.

**Tutorial**

**Solution (BledDest)**

```
q = int(input())
for i in range(q):
s = input()
t = input()
n = len(s)
m = len(t)
ans = False
for i in range(n):
for j in range(0, n - i):
k = m - 1 - j
if i + j < k:
continue
l1 = i
r = i + j
l2 = r - k
if s[l1:r+1] + s[l2:r][::-1] == t:
ans = True
print('YES' if ans else 'NO')
```

Idea: Errichto Preparation: BledDest

**Tutorial**

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int ans = 9;
{
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < 10; ++i) {
if (i % 2 == 0) cnt0 += s[i] != '0';
else cnt1 += s[i] == '1';
if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);
if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);
}
}
{
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < 10; ++i) {
if (i % 2 == 0) cnt0 += s[i] == '1';
else cnt1 += s[i] != '0';
if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);
if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);
}
}
cout << ans + 1 << '\n';
}
}
```

Idea: Adel_SaadEddin, Zaher Preparation: Will not be revealed for now because we care for his/their safety.

**Tutorial**

**Solution (Um_nik)**

```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 200200;
int n, m;
char s[N], t[N];
bool solve() {
scanf("%s %s", s, t);
n = strlen(s);
m = strlen(t);
if (n < m) return false;
int p = (n - m) & 1;
int q = 0;
int k = 0;
for (int i = p; i < n; i++) {
if (k == 1) {
k = 0;
continue;
}
if (q < m && s[i] == t[q]) {
q++;
} else {
k++;
}
}
return q == m;
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int T;
scanf("%d", &T);
while(T--) {
if (solve())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
```

Idea: bthero, mhq Preparation: BledDest

**Tutorial**

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
int cycle_count(vector<int> q, int n)
{
for(int i = 0; i < n; i++)
q[i]--;
vector<int> used(n);
int ans = 0;
for(int i = 0; i < n; i++)
{
if(used[i] == 1) continue;
int j = i;
while(used[j] == 0)
{
used[j] = 1;
j = q[j];
}
ans++;
}
return ans;
}
bool check(int n, int m, int k, vector<int> p)
{
vector<int> q;
for(int i = k; i < n; i++)
q.push_back(p[i]);
for(int i = 0; i < k; i++)
q.push_back(p[i]);
return n - cycle_count(q, n) <= m;
}
void solve()
{
int n, m;
scanf("%d %d", &n, &m);
vector<int> p(n);
for(int i = 0; i < n; i++)
scanf("%d", &p[i]);
vector<int> cnt(n);
for(int i = 0; i < n; i++)
{
int offset = i + 1 - p[i];
if(offset < 0)
offset += n;
cnt[offset]++;
}
vector<int> ans;
for(int i = 0; i < n; i++)
if(cnt[i] + 2 * m >= n && check(n, m, i, p))
ans.push_back(i);
printf("%d", ans.size());
for(auto x : ans) printf(" %d", x);
puts("");
}
int main()
{
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
{
solve();
}
}
```

Idea: mhq, Errichto Preparation: bthero

**Tutorial**

**Solution (bthero)**

```
// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<int N> struct Fenw {
ll t[N + 1];
Fenw() {
fill(t + 1, t + N + 1, 0ll);
}
void update(int p, ll x) {
for (; p <= N; p |= (p + 1)) {
t[p] += x;
}
}
ll get(int p) {
ll ret = 0;
for (; p > 0; --p) {
ret += t[p];
p &= (p + 1);
}
return ret;
}
ll get(int l, int r) {
return get(r) - get(l - 1);
}
};
const int M = (int)3e5;
void solve() {
int n;
cin >> n;
Fenw<M> A, B;
ll pref = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
ans += x * (i - 1ll);
ans += A.get(x);
ans += pref;
pref += x;
for (int j = x; j <= M; j += x) {
int l = j, r = min(M, j + x - 1);
ans -= B.get(l, r) * j;
A.update(l, -x);
}
B.update(x, 1);
cout << ans << " \n"[i == n];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
for (int i = 1; i <= tt; ++i) {
solve();
}
return 0;
}
```

**Segment tree solution (bthero)**

```
// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define debug(x) cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int M = (int)3e5;
namespace A {
ll t[M * 4];
void update(int l, int r, ll x, int v = 1, int tl = 1, int tr = M) {
if (l > r || tl > r || tr < l) {
return;
}
if (l <= tl && tr <= r) {
t[v] += x;
return;
}
int mid = (tl + tr) >> 1;
int c1 = (v << 1), c2 = (c1 | 1);
update(l, r, x, c1, tl, mid);
update(l, r, x, c2, mid + 1, tr);
}
ll get(int p, int v = 1, int tl = 1, int tr = M) {
if (tl == tr) {
return t[v];
}
int mid = (tl + tr) >> 1;
int c1 = (v << 1), c2 = (c1 | 1);
if (p <= mid) {
return t[v] + get(p, c1, tl, mid);
}
else {
return t[v] + get(p, c2, mid + 1, tr);
}
}
}
namespace B {
ll t[M * 4];
void update(int p, ll x, int v = 1, int tl = 1, int tr = M) {
if (tl == tr) {
t[v] += x;
return;
}
int mid = (tl + tr) >> 1;
int c1 = (v << 1), c2 = (c1 | 1);
if (p <= mid) {
update(p, x, c1, tl, mid);
}
else {
update(p, x, c2, mid + 1, tr);
}
t[v] = t[c1] + t[c2];
}
ll get(int l, int r, int v = 1, int tl = 1, int tr = M) {
if (l > r || tl > r || tr < l) {
return 0ll;
}
if (l <= tl && tr <= r) {
return t[v];
}
int mid = (tl + tr) >> 1;
int c1 = (v << 1), c2 = (c1 | 1);
return get(l, r, c1, tl, mid) + get(l, r, c2, mid + 1, tr);
}
}
int n;
void solve() {
cin >> n;
ll pref = 0, ans = 0;
rep (i, 1, n + 1) {
int x;
cin >> x;
ans += x * (i - 1ll);
ans += A::get(x);
ans += pref;
pref += x;
for (int j = x; j <= M; j += x) {
int l = j, r = min(M, j + x - 1);
ans -= x * B::get(l, r) * (j / x);
A::update(l, r, -x * (j / x));
}
B::update(x, 1);
cout << ans << " \n"[i == n];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
for (int i = 1; i <= tt; ++i) {
solve();
}
return 0;
}
```

Idea: Adel_SaadEddin, Zaher, Errichto Preparation: Errichto

**Tutorial**

**Solution (Errichto)**

```
// gcd, AC, O((N+Q) * log^2), by Errichto
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
struct DSU {
vector<int> parent;
DSU(int m) {
parent.resize(m + 1);
for(int i = 0; i <= m; ++i) {
parent[i] = i;
}
}
int find(int a) {
if(a == parent[a]) {
return a;
}
return parent[a] = find(parent[a]);
}
void uni(int a, int b) {
parent[find(a)] = find(b);
}
};
int main() {
// 1) read input
int n, q;
scanf("%d%d", &n, &q);
vector<int> a(n);
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
int m = *max_element(a.begin(), a.end());
// 2) prime sieve
vector<vector<int>> prime_divisors(m + 2);
for(int p = 2; p <= m + 1; ++p) {
if(prime_divisors[p].empty()) {
for(int j = p; j <= m + 1; j += p) {
prime_divisors[j].push_back(p);
}
}
}
// 3) DSU, find initial connected components
DSU dsu(m + 2);
for(int x : a) {
for(int p : prime_divisors[x]) {
dsu.uni(x, p);
}
}
// 4) DSU, find edges of cost 1
set<pair<int,int>> edges;
for(int x : a) {
vector<int> nodes = prime_divisors[x+1];
nodes.push_back(x);
for(int& node : nodes) {
node = dsu.find(node);
}
for(int i = 0; i < (int) nodes.size(); ++i) {
for(int j = i + 1; j < (int) nodes.size(); ++j) {
int one = nodes[i];
int two = nodes[j];
if(one != two) {
if(one > two) {
swap(one, two);
}
edges.insert({one, two});
}
}
}
}
debug() << imie(edges);
cerr << imie(edges.size()) << endl;
// 5) answer queries
while(q--) {
int s, t;
scanf("%d%d", &s, &t);
--s;
--t;
s = dsu.find(a[s]);
t = dsu.find(a[t]);
if(s == t) {
puts("0");
}
else if(edges.count({min(s, t), max(s, t)})) {
puts("1");
}
else {
puts("2");
}
}
}
```

Idea: mhq Preparation: BledDest, mnaeraxr, mhq

**Tutorial**

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int INF = int(1e9);
const int K = 20;
struct node
{
int max_val, min_val, ans, len;
node* left;
node* right;
void recalc()
{
len = left->len + right->len;
max_val = max(left->max_val, right->max_val + left->len);
min_val = min(left->min_val, right->min_val + left->len);
ans = min(min(left->ans, right->ans), min(INF, right->min_val - left->max_val + left->len));
}
node(int x)
{
ans = INF;
len = 1;
if(x == 1)
max_val = min_val = 0;
else
{
max_val = -INF;
min_val = INF;
}
}
node(node* l, node* r)
{
left = l;
right = r;
recalc();
}
node() {};
};
int cnt[1 << K];
node tree[2 << K];
int n, k, m;
void build(int v, int l, int r)
{
if(l == r - 1)
tree[v] = node(cnt[l]);
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
tree[v] = node(&tree[v * 2 + 1], &tree[v * 2 + 2]);
}
//cerr << v << " " << l << " " << r << " " << tree[v].min_val << " " << tree[v].max_val << " " << tree[v].len << " " << tree[v].ans << endl;
}
void swap_segments(node* v, int d)
{
if(d == 0)
{
swap(v->left, v->right);
v->recalc();
}
else
{
swap_segments(v->left, d - 1);
swap_segments(v->right, d - 1);
v->recalc();
}
//cerr << v->min_val << " " << v->max_val << " " << v->len << " " << v->ans << endl;
}
int res[1 << K];
int cur = 0;
void rec(int x)
{
if(x == 0)
res[cur] = tree[0].ans;
else
rec(x - 1);
swap_segments(&tree[0], x);
cur ^= (1 << (k - x - 1));
if(x == 0)
res[cur] = tree[0].ans;
else
rec(x - 1);
}
int main()
{
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
cnt[x]++;
}
m = 1 << k;
build(0, 0, m);
rec(k - 1);
for(int i = 0; i < m; i++)
printf("%d ", res[i]);
puts("");
}
```

**Alternative solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int INF = int(1e9);
const int K = 20;
struct node
{
int max_val, min_val, ans, len;
node(const node& left, const node& right)
{
len = left.len + right.len;
max_val = max(left.max_val, right.max_val + left.len);
min_val = min(left.min_val, right.min_val + left.len);
ans = min(min(left.ans, right.ans), min(INF, right.min_val - left.max_val + left.len));
}
node(int x)
{
ans = INF;
len = 1;
if(x == 1)
max_val = min_val = 0;
else
{
max_val = -INF;
min_val = INF;
}
}
node() {};
};
int cnt[1 << K];
vector<node> tree[2 << K];
void build(int v, int l, int r)
{
tree[v].resize(r - l);
if(l == r - 1)
{
tree[v][0] = node(cnt[l]);
}
else
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
for(int i = 0; i < m - l; i++)
{
tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]);
}
}
}
int main()
{
int n, k;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
cnt[x]++;
}
int m = 1 << k;
build(0, 0, m);
for(int i = 0; i < m; i++)
printf("%d ", tree[0][i].ans);
puts("");
}
```

Idea: bthero, mhq, BledDest Preparation: BledDest, mhq

**Tutorial**

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define sz(a) ((int)((a).size()))
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
template<const int &MOD>
struct _m_int {
int val;
_m_int(int64_t v = 0) {
if (v < 0) v = v % MOD + MOD;
if (v >= MOD) v %= MOD;
val = int(v);
}
_m_int(uint64_t v) {
if (v >= MOD) v %= MOD;
val = int(v);
}
_m_int(int v) : _m_int(int64_t(v)) {}
_m_int(unsigned v) : _m_int(uint64_t(v)) {}
static int inv_mod(int a, int m = MOD) {
int g = m, r = a, x = 0, y = 1;
while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
explicit operator int() const { return val; }
explicit operator unsigned() const { return val; }
explicit operator int64_t() const { return val; }
explicit operator uint64_t() const { return val; }
explicit operator double() const { return val; }
explicit operator long double() const { return val; }
_m_int& operator+=(const _m_int &other) {
val -= MOD - other.val;
if (val < 0) val += MOD;
return *this;
}
_m_int& operator-=(const _m_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
return unsigned(x % m);
#endif
// Optimized mod for Codeforces 32-bit machines.
// x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;
}
_m_int& operator*=(const _m_int &other) {
val = fast_mod(uint64_t(val) * other.val);
return *this;
}
_m_int& operator/=(const _m_int &other) {
return *this *= other.inv();
}
friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
_m_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
_m_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
_m_int operator++(int) { _m_int before = *this; ++*this; return before; }
_m_int operator--(int) { _m_int before = *this; --*this; return before; }
_m_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
_m_int inv() const {
return inv_mod(val);
}
_m_int pow(int64_t p) const {
if (p < 0)
return inv().pow(-p);
_m_int a = *this, result = 1;
while (p > 0) {
if (p & 1)
result *= a;
a *= a;
p >>= 1;
}
return result;
}
friend ostream& operator<<(ostream &os, const _m_int &m) {
return os << m.val;
}
};
extern const int MOD = 998244353;
using Mint = _m_int<MOD>;
const int LOGN = 19;
const int N = (1 << LOGN);
const int T = 2;
Mint g = 3;
vector<Mint> w[LOGN];
vector<int> rv[LOGN];
void precalc() {
Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
forn(st, LOGN - 1) {
w[st].assign(1 << st, 1);
Mint bw = wb.pow(1 << (LOGN - st - 1));
Mint cw = 1;
forn(k, 1 << st) {
w[st][k] = cw;
cw *= bw;
}
}
forn(st, LOGN) {
rv[st].assign(1 << st, 0);
if (st == 0) {
rv[st][0] = 0;
continue;
}
int h = (1 << (st - 1));
forn(k, 1 << st)
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
}
}
void ntt(vector<Mint> &a, bool inv) {
int n = sz(a);
int ln = __builtin_ctz(n);
forn(i, n) {
int ni = rv[ln][i];
if (i < ni) swap(a[i], a[ni]);
}
forn(st, ln) {
int len = 1 << st;
for (int k = 0; k < n; k += (len << 1)) {
fore(pos, k, k + len){
Mint l = a[pos];
Mint r = a[pos + len] * w[st][pos - k];
a[pos] = l + r;
a[pos + len] = l - r;
}
}
}
if (inv) {
Mint rn = Mint(n).inv();
forn(i, n) a[i] *= rn;
reverse(a.begin() + 1, a.end());
}
}
vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
a.resize(cnt);
b.resize(cnt);
ntt(a, false);
ntt(b, false);
vector<Mint> c(cnt);
forn(i, cnt) c[i] = a[i] * b[i];
ntt(c, true);
while(c.size() > 1 && c.back() == 0)
c.pop_back();
return c;
}
struct dp
{
vector<Mint> val[T][T];
bool is_unit;
dp() {};
dp(int len)
{
is_unit = len == 1;
for(int j = 0; j < T; j++)
for(int k = 0; k < T; k++)
val[j][k] = {0};
if(len == 1)
val[0][0][0] = 1;
else
val[1][1][0] = 2;
}
dp(const dp& a, const dp& b)
{
is_unit = false;
for(int l1 = 0; l1 < T; l1++)
for(int r1 = 0; r1 < T; r1++)
for(int l2 = 0; l2 < T; l2++)
for(int r2 = 0; r2 < T; r2++)
{
vector<Mint> cur = mul(a.val[l1][r1], b.val[l2][r2]);
if(val[l1][r2].size() < cur.size())
val[l1][r2].resize(cur.size());
for(int i = 0; i < cur.size(); i++)
val[l1][r2][i] += cur[i];
Mint merge_coeff = 2;
if(r1 == 1)
merge_coeff /= 2;
if(l2 == 1)
merge_coeff /= 2;
cur.insert(cur.begin(), 0);
for(int i = 0; i < cur.size(); i++)
cur[i] *= merge_coeff;
int L1 = l1;
int R2 = r2;
if(a.is_unit)
L1 = 1;
if(b.is_unit)
R2 = 1;
if(val[L1][R2].size() < cur.size())
val[L1][R2].resize(cur.size());
for(int i = 0; i < cur.size(); i++)
{
val[L1][R2][i] += cur[i];
}
}
}
};
ostream& operator<<(ostream& out, const dp& a)
{
for(int i = 0; i < T; i++)
for(int j = 0; j < T; j++)
{
out << "[" << i << "][" << j << "]";
for(auto x : a.val[i][j])
out << " " << x;
out << endl;
}
return out;
}
int a[N];
int len[N];
Mint fact[N];
int n;
int s;
dp build(int l, int r)
{
if(l == r - 1)
{
dp res(len[l]);
//cerr << l << " " << r << endl;
//cerr << res;
return res;
}
else
{
int m = (l + r) / 2;
dp res(build(l, m), build(m, r));
//cerr << l << " " << r << endl;
//cerr << res;
return res;
}
}
int main()
{
precalc();
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
int cur = 0;
while(cur != n)
{
if(cur + a[cur] > n)
{
cout << 0 << endl;
return 0;
}
for(int l = cur; l < cur + a[cur]; l++)
if(a[l] != a[cur])
{
cout << 0 << endl;
return 0;
}
len[s++] = a[cur];
cur += a[cur];
}
fact[0] = 1;
for(int i = 1; i <= s; i++)
fact[i] = i * fact[i - 1];
dp res = build(0, s);
Mint ans = 0;
for(int i = 0; i < s; i++)
for(int j = 0; j < T; j++)
for(int k = 0; k < T; k++)
if(res.val[j][k].size() > i)
ans += fact[s - i] * res.val[j][k][i] * (i % 2 == 0 ? 1 : MOD - 1);
cout << ans << endl;
}
```

Auto comment: topic has been updated by Harbour.Space (previous revision, new revision, compare).Same in video format: https://youtu.be/NqgObtKz_jM

This is what you want with coffee in the morning.Big Thanks

https://codeforces.com/contest/1553/submission/123329166

here is a solution for problem D. since mr um_nik was so fast in solving that he forgot to add editorial

The code is written in python and should be pretty self explanatory

EDIT: THANKS FOR REPLY ERRICHTO. I didn't pay attention to the fact that he was a tester

As you can read in the main blog, um_nik was a tester. He has nothing to do with the editorial.

No offence, but I am curious: do you personally like problems B & C? It's very surprising to me that these are the best ideas an LGM, who's also involved in a number of CP activities, can come up with.

No worries, I'm happy to explain my/our reasoning.

I certainly like B & C more than problem A. In the discussion below some CF blogs, I've already argued that math puzzles aren't that good for easy problems. But yeah, you can also say that I'm getting out of shape and my taste is getting worse. I lost my hopes after feedback from my AGC 47.

I suggested three easy problems: something rejected as A, penalties

withoutquestion marks as B, and Reverse String with $$$n \leq 2000$$$ as C or with $$$n \leq 200$$$ as B. I would use those three in my round and I can defend that choice. In particular, I like Penalties most as it's a natural problem that I came up with during Euro Cup. "Given a binary string like 1011100000, say when the winner is already decided".Reverse String was rejected because it would be adjacent to the similar-styled Backspace. Penalties were too easy for the second slot (or so we thought) so somebody suggested question marks. Sadly, that change modifies the problem from cute to artificial. Testers then provided feedback that the round is too difficult for beginners. To fit the slot between Digits Sum and Penalties, we used Reverse String with $$$n \leq 200$$$.

what is the 85th token of 19th test case of problem D??

If t matches the first few characters of s, you need to judge whether the number of remaining characters of s is even. Only if the number is even can the match be true.

yaa, i missed it. thanx bwxnQAQ Now you are my friend.

A very big thanks to you buddy bwxnQAQ

Thank you very much.

Thanks bwxnQAQ , I was scratching my head for almost 2 hours because of this silly error or not so silly idk

You need to judge if the number of the remaining letters is even or not.

Can u give that testcase or something similar to that, I am facing trouble regarding that t-c 19 85-th token..

1 ab a

Can you told me why I am getting TLE on test 30 in Problem D? -_- I used binary search. Can it be a reason? Here is my solution :

https://codeforces.com/contest/1553/submission/126554472

na apu,,,,,..... nlogn is efficient......... but you declare vector odd[200010] which complexity is O(n),n=size......... total complexity will be O(n*q)......... then if q=100000, it will definitely fail..............

https://codeforces.com/contest/1553/submission/126596025

Many Thanks... I was totally confused why I am getting tle. Thanks a lot for replying..

can we use bitmask enumeration technique to generate all possibilities in problem C?

Hey, I am an author of problem F. We actually did not intend any $$$O(N \sqrt{M} \log M)$$$ solutions to pass at the beginning.

The thing is, my Fenwick tree solution works in ~400 ms, but my segment tree solution works in ~2.5 s. Segment tree with pushes does not even pass the time limit because of a high constant factor. Also we had to care about Java solutions, so I decided to raise the TL from 3s to 4s, letting $$$O(N \sqrt{M} \log M)$$$ to pass.

I know I had to fix this problem in a more adequate way by experimenting with constraints. Will certainly do that in future rounds. Sorry about that.

I think you mean $$$\mathcal{O}(N\sqrt{M*\log{M}})$$$ solutions, as I am not aware of any $$$\mathcal{O}(N\sqrt{M}*\log{M})$$$ solution. The thing is, mine was nowhere close even with pragmas and the 64-bit compiler.

My $$$\mathcal O(N \sqrt{M} \log M)$$$ passes pretty comfortably within the TL. Unfortunately, I was not able to debug this quickly enough during the contest.

Submission

My solution with a time complexity of $$$\mathcal{O}(N\sqrt M)$$$ passed all the pretests using $$$3400\space\text{ms}$$$ and then passed all the system tests using $$$3416\space\text{ms}$$$.

Note: this is not a comment talking about creative solutions, but a comment talking about how to use some ordinary data structure to compensate stupidity, so please forgive me if this sounds not so inspiring...... QwQ

Just sharing some thoughts...... QwQ

If you use enumerate all of the possible results of $$$\lfloor\dfrac{a_i}{x}\rfloor$$$, you will end up with a condition in which you need to maintain a sequence allowing you to perform to operations:

And the length of the sequence is $$$\mathcal{O}(M)$$$, the total number of "update"s is $$$\mathcal{O}(N)$$$, while the total number of "query"s is $$$\mathcal{O}(N\sqrt M)$$$.

You choose a power of $$$2$$$ near $$$\sqrt M$$$, in my case I chose $$$2^9=512$$$, and divide the sequence into several blocks, each have a length of $$$512$$$.

You maintain two sequences, $$$C_i$$$ and $$$\Delta_i$$$, in which $$$C_i$$$ means the sum of elements in the $$$i-1$$$-th, $$$i-2$$$-th, ......, and the $$$1$$$-st block, while $$$\Delta_i$$$ means the sum of elements in the $$$i$$$-th position, $$$i-1$$$-th position, $$$i-2$$$-th position, ......, and the earliest position that still belongs in block $$$i$$$.

It's not hard to see the answer to any queries to position $$$i$$$ is $$$C_{\lfloor\dfrac{i}{2^9}\rfloor}+\Delta_i$$$, meanwhile $$$\lfloor\dfrac{i}{2^9}\rfloor$$$ can be calculated quickly enough using the bitwise

`>>`

operation.When an update occurs, if the update is a plus $$$x$$$ at position $$$i$$$, you just enumerate all the blocks $$${\lfloor\dfrac{i}{2^9}\rfloor}+1,{\lfloor\dfrac{i}{2^9}\rfloor}+2,{\lfloor\dfrac{i}{2^9}\rfloor}+3$$$,...... and add $$$x$$$ to the $$$C$$$ of those; and within block $$${\lfloor\dfrac{i}{2^9}\rfloor}$$$, you just enumerate all the positions and add $$$x$$$ to the $$$D$$$ of those.

This data structure handles each update in $$$\mathcal{O}(\sqrt M)$$$ time, each query in $$$\mathcal{O}(1)$$$ time, or constant time, and it also has a pretty excellent constant factor.

My implementation(may be very ugly QAQ) is here: Submission #123330049 — Codeforces

Thank you very much for your time reading this! I really appreciate it.

It is amusing that this is kind of a "two-layer" segment tree, and if you change it into three layers, the time complexity handling updates will reduce to $$$\sqrt[3]M$$$ while not changing the time complexity of queries(since its adds up $$$3$$$ pieces of information instead of $$$2$$$).

That means that you can actually chose ANY constant number $$$\lambda$$$ and make the time complexity $$$\mathcal{O}(\sqrt[\lambda]M)$$$ — $$$\mathcal{O}(1)$$$......

But in practice I've only seen choosing $$$\lambda=2,3,4$$$ and a large proportion of them $$$2$$$...... QwQ

Shouldn't the complexity be $$$O(\sqrt[\lambda]{M} + M)$$$?

Thanks for your correction, but I meant to say that It costs $$$\mathcal{O}(\sqrt[\lambda]M)$$$ time to use the data structure to handle EACH update operation, and $$$\mathcal{O}(1)$$$ time to use the data structure to handle EACH query operation QwQ.

$$$\lambda = \log n$$$ requires $$$O(\log n)$$$ for both updates and queries.

Harbour.space is a ripoff and clearly, this contest sucked. Please downvote the blog to support the cause!

Regarding problem E, could someone elaborate on transforming a permutation into another one? Why does the provided algorithm work? Could you provide some online resource about this?

Suppose you have a connected component of size $$$k$$$. It will surely be a cycle. You can easily show that this cycle can be fixed using $$$k-1$$$ swaps, but not less. In total this will sum up to $$$n - cycles$$$ operations.

Also you could try mixing elements between different cycles, but you will see it does not help either. This is not a formal proof, just a simple explanation built on pure intuition and logic.

Thanks for the intuition. I derived the contradiction of minimality for the case of swapping vertices between two components. And as for the $$$k - 1$$$ swaps, I guess proof is redundant, seems logical to me. :)

Also thanks to Errichto for his comment.

You need $$$k-1$$$ swaps to transform $$$[1, 2, 3, 4, \ldots, k]$$$ into $$$[2, 3, 4, \ldots, k, 1]$$$. Swapping two values (e.g. the first two) puts one element in proper position. This happens for $$$k-2$$$ swaps and then the last swap puts the last two elements in proper positions.

Auto comment: topic has been updated by Harbour.Space (previous revision, new revision, compare).Alternate solution for B

Store all the substrings of the string $$$s$$$ in an unordered map with the string being the key and the value being a vector of ending indices of the substring (note that a single substring might exist multiple times). For the string $$$t$$$, split it into two at every index and let's say we get string $$$t_1$$$ and $$$t_2$$$, check if -

can I have your solution link? preferably in c++.

https://codeforces.com/contest/1553/submission/123329371

there

Solution for B, not c.

https://codeforces.com/contest/1553/submission/123320496

sorry, this is it

F in chat for person who lost scholarship due to hacks

I used a sledgehammer to crack a nut. Used KMP algorithm in B.

My submission: 123364212

Works in $$$\mathcal O(n^2)$$$ probably.

Could U give a brief solution on your idea?

In short, I'm searching for all prefixes of $$$t$$$ and reverse of the remaining part in $$$s$$$.

SpoilerAt every $$$i$$$-th step, maintain $$$i$$$-th prefix of $$$t$$$ and the reverse of the remaining part of $$$t$$$. Formally, maintain $$$p_i = t_0t_1\cdots t_{i-1}$$$ and $$$q_i = t_{n-1}t_{n-2}\cdots t_i$$$. What we look for is an $$$i$$$, such that $$$p_i$$$ and $$$q_i$$$ are substrings of $$$s$$$ and if $$$p_i$$$ ends at position $$$k$$$ in $$$s$$$, then $$$q_i$$$ should end at $$$k-1$$$. Also, the corner cases are if $$$q_0$$$ or $$$p_n$$$ is present in $$$s$$$.

Use KMP algorithm to search for corner cases. For the interior cases, I've stored all (ending) indices at which they're found (again using KMP algorithm) and used two pointers to match the condition for $$$k$$$. If any $$$i$$$ satisfies, or any corner case is satisfied, I'm done.

The KMP algorithm works in $$$\mathcal O(n)$$$ time and there are $$$\mathcal O(n)$$$ searches done.

Edit:

1. $$$n$$$ is the length of $$$t$$$.

2. All searches are done in $$$\mathcal O(n)$$$ as the two substrings to be searched add up to a length $$$n$$$.

3. $$$0$$$-based indexing is used.

Got it,thx so much.

solution of the second problem https://codeforces.com/contest/1553/submission/123320281

Dear problem setters please attach images for better understanding of problems !

My solution to H is different from the first one provided in the editorial, and the second one provided in the editorial is too vague, so I’ll describe mine here.

## Alternate Solution for 1553H - XOR and Distance

SpoilerAs in the editorial, build a trie on the provided numbers. For each node in the trie, all we need to store is whether it contains a number.

Now, imagine calculating the answer for some $$$x$$$, and suppose that we fix the highest bit in which $$$a_i$$$ and $$$a_j$$$ differ. Assuming WLOG that $$$a_j \oplus x > a_i \oplus x$$$, we simply want to make it so that in the remaining bits $$$a_i \oplus x$$$ has $$$1$$$ bits and $$$a_j \oplus x$$$ has $$$0$$$ bits where possible.

Suppose further that we already fixed the higher bits of $$$a_i$$$ and $$$a_j$$$ (the ones that match), so that $$$a_i$$$ will come from one specific node in the trie and $$$a_j$$$ will come from its sibling. For the next bit that we need to choose, if we can make $$$a_i$$$ have $$$1$$$ and $$$a_j$$$ have $$$0$$$, we should obviously do that. This will mean that $$$a_i$$$ must come from a specific child of its current node, and the same for $$$a_j$$$.

If we can’t do that, but we can make both have the same bit, then note that this bit will be determined, as otherwise we could make $$$a_i$$$ have $$$1$$$ and $$$a_j$$$ have $$$0$$$.

If we can’t do either, then we just let $$$a_i$$$ have $$$0$$$ and $$$a_j$$$ have $$$1$$$. In all of these cases, we simply move down to a

singlechild for each of $$$a_i$$$ and $$$a_j$$$.That procedure runs in $$$O(k)$$$ time. Now note that when we fix that the $$$j^{\text{th}}$$$ bit is the highest to differ, then we need to try $$$2^{k - j - 1}$$$ possibilities for the higher bits of $$$a_i$$$ and $$$a_j$$$, but because those bits don’t matter in $$$x$$$, we also determine the answer for $$$2^{k - j - 1}$$$ values of $$$x$$$ (the answer when fixing $$$j$$$).

This means that, since for each possible value of $$$x$$$ there are the same $$$k$$$ possible values of $$$j$$$, overall we run the above procedure $$$k2^k$$$ times, making the overall runtime of the algorithm $$$O(k^22^k)$$$.

I think it should be $$$2^{10}$$$ in the editorial of C, instead of $$$2^10$$$.

How to solve B in $$$O(n^2)$$$, I thought a lot but couldn't come up with a solution.

Suppose x is the starting position, y is the rightmost position you covered and z is the leftmost position you covered. For every pair of x and y, z is unique (if it exists)(because length of t is fixed). Now you can easily compare by hashing.

here : 123296482

some explanationSubstr is a fuction I copied from gfg, which checks if one string is substring of another. Other than that the solution is self explanatory.

solution i think my dp solution is n2 .correct me if i am wrong.

123306389 my dfs solution is truly similar to yours.I think that the dp array in your solution isn't necessarry and it may not work because we keep going right and then keep going left.So we cannot get repetitive (i,j,flag),right? of course i think our solutions are

O(n²)and it may work even faster in tests.TerriblePretestsForces

Preparation : will not be revealed for now cuz we care for their safety ...lol .. Btw fstforces

Wow, problem B was really harder than many people thought.

Not so hard, as $$$\Theta(n^3)$$$ is really easy to think and code.

Many people thought they can work out $$$\Theta(n^2)$$$ ，but they failed. That's no need.

But why $$$O(n^{3})$$$ passes as it is $$$500^{3} = 1.25 * 10^{8}$$$ operations but it should be maximum of around $$$10^{7}$$$ per second, right?

Edit — Found this

it's around $$$2 * 10^8$$$ I think, CF's judging machines are fast, and I think $$$2 * 10^8$$$ is also standard for ICPC

it's not strict n^3 it's lesser than n^3 / 2 and even n^3 alone runs easily under a second

I think it's $$$O(N^3)$$$ because $$$std::string.find$$$ is quadratic in worst case

Ya, same happened with me!

I had totally ignored bound on m, got that cyclic swaps part during the contest, but screwed all the time by thinking about how can I optimize my solution. Now I have learned from this mistake to read questions carefully :)

I think tests on H are weak. I passed them with solution with some stupid approaches + random, but after I looked at the tests I noticed that all big tests have all 1's as answers. Here is the solution that takes random pair i, j and calculates for all x and if n>200 writes all 1's.

the pre testcases was weak and made a round not fair for some people i solved a b c d and hacked 6 subbmisions so i was in 1000 place but after main test found d get wrong answer and become in 2200 place it was big shock for me

https://codeforces.com/contest/1553/submission/123309155 in this submission i used dp with size 600 but lenth of t maybe equal to 999 why it didnt get run run time error can any one answer me??

Where is the D?

read um_nik's code and dry run on a few cases u will understand.

Is it possible to solve D using binary search?

I implemented it, it's giving WA on test case 6.

6th test case is too long, not possible to check what went wrong in my code :{

used brute O(n^3) solution in B. Accepted in PyPy in only 358ms

123296399

Solution for B: suppose you're standing on the position $$$i$$$. There are 4 cases:

you can go only to the right, so $$$t$$$ is a substring from $$$s$$$.

you can go only left, so the reverse of $$$t$$$ is a substring from $$$s$$$.

you can go right then left, then there are two cases:

either you go from index $$$i$$$ to index $$$i+x$$$: $$$(x >= 0)$$$ then to index $$$i-y$$$ $$$(y >= x)$$$.

then you can divide that into an odd-length-palindrome prefix and some sector, so you take from the center of the palindrome till the end of $$$t$$$. then reverse and check if that is a substring from $$$t$$$.

or you go from index $$$i$$$ to index $$$i+x$$$: $$$(x >= 0)$$$ then to index $$$i-y$$$ $$$(y < x)$$$. then you can divide that into some sector an odd-length-palindrome suffix, so you take from the center of the palindrome till the beginning of $$$t$$$. then reverse and check if that is a substring from $$$t$$$.

If it doesn't belong to any of these options, then the answer is No.

complexity: $$$O(n^2)$$$

link for the submission:

https://codeforces.com/contest/1553/submission/123368933

In problem E, can someone provide me a proof why for each cycle of size $$$k$$$ the minimum number of swaps is $$$k-1$$$ ? couldn't it be less than $$$k-1$$$ swap?

Proof works with induction.

The base case is that k==2, then one swap fixes both elements. Else k>2, and swapping two elements fixes at most one of them, leaving us with a cycle of size k-1. It is easy to see that swapping two elements without fixing one does not give a better solution.

H can be implemented in a similar style to FFT/FWHT. I don't know if there is a way to interpret this in terms of polynomials.

The code is quite short (shortest submission at time of writing): 123356112. It uses $$$O(k2^k)$$$ time and $$$O(2^k)$$$ memory.

actually,i dont think that weak pretest make contest somehow worse.becouse it teach u to be more attentive and re-read code even if it got AC on pretest.And every solution tests on same set of pretests so every one is on equal terms.

So do you submit a solution to A and get pretests passed and then stare at the whole solution till the contest ends, because maybe it will not pass system tests?

can some1 help me with B , it is giving me runtime error idk why, https://codeforces.com/contest/1553/submission/123372047

@sa_so_ in both for loops u have used n and n-i But may be in some loop it might be 'm'

Why can not I see the tutorial of the problem D

Because tutorial of D is not available.

Thanks

Solution for D$$$Problem:$$$ 1553D - Backspace

We iterate from right to left, or from back to front.

Let $$$n$$$ be the

currentsize of $$$s$$$ and let $$$m$$$ be thecurrentsize of $$$t$$$.Now, if $$$s[n] == t[m]$$$ Then we simplify the question to $$$s := s[1...n - 1]$$$ and $$$t := t[1...m - 1]$$$. Thus, we reduce the size of $$$s$$$ and $$$t$$$ once.

The other case is when $$$s[n]$$$ != $$$t[m]$$$, Here we obviously need to click a backspace otherwise our last character will be $$$s[n]$$$ which is not what we want. So, we click a backspace. But when we do so, we delete some previous character(if any) as well. Therefore, we reduce the problem to, $$$s := s[1... n - 2]$$$ and $$$t$$$ remains the same. Thus, you pop $$$s$$$ twice.

After one of the strings is empty you stop and break your loop.

For your final answer, if string $$$t$$$ is empty the answer is "YES" else, "NO".

Time Complexity: $$$O(n + m)$$$.

My Code: 123381503

The tutorial for D is most likely not written yet or its written and is undergoing some edits. Whatever the case, the tutorial is still not out and available yet.

thanks

Very well explained.Thanks

why we have to move right to left ,i tried an approach where i am are moving from left to right and if difference between some part is even we can delete it

but it is giving wrong answer my code

can you please tell which case i am missing?

or can you tell me how i can think of approach of moving pointer from right to left?

You can just reverse strings right after reading them from the input and then do left to right processing in the rest of your code. That's what I did myself during the contest. If the standard C++ library doesn't offer a native way to reverse strings, then it makes sense to have such function somewhere in your collection of code templates.

The main idea is that in many cases it is possible to do some cheap pre-processing of the input data to make the problem easier. Sometimes it's sorting of the input data, sometimes it's reversing the order of elements, etc.

My random guess is that maybe the official solution for D was not originally intended to be greedy?

I first tried to implement my solution as a recursive DP with a two-dimensional state array of 1-bit boolean states, but this is obviously not a good fit for the problem constraints and needed improvements. Still I used this code as a reference implementation to generate a lot of testcases. I thought that maybe a single-dimensional DP state array (storing something like the best index or whatever) could do the job. But then noticed that just a simple greedy modification doesn't seem to fail any of the generated testcases. This was a facepalm moment for me. Spent so much time on something that turned out to have just a greedy solution! The letter D was really deceiving. However observing many system tests failures and hacks after the contest made me change my mind to some extent. The time spent on thoroughly testing solutions locally was not a completely wasted effort after all.

I wake up and see result problem D Time limit on test 99 , very sad!!!!!!

I have the same problem as you. Have you found where the wrong is? Tell me about it, please.

Looking at test 99 I came up with a way to escape the time limit, I check the string s, if the string t contains a character that the string s doesn't, make the word print "no" and return, good luck

I got it, thank you.

hello, can you tell me the logic of penalty and why in last test case the answer is 9. It would be helpful if you give me some competitive programming tips. thanks

Hello, which problem are you talking about here?

As for the penalty, For every submission you get a non-AC verdict on tc != 1 during the contest, you get a penalty of 10mins, that is your solution is considered to be 10mins late after the actual AC verdict.

I am asking about problem C. Can you help me why is the answer 9 in last test case of problem

ExplainationOkay, so the given string is - 0100000000

The game isn't decided till the second last shot because the referee thinks that this string is possible- 0100000010

In the above string the score is [1 : 1].

But after the 9th shot the referee knows the score is [0 : 1] and its second teams turn, and irrespective of whether or not the last shot goes in or not the second team is bound to win.

But until the 9th shot the end result was unknown, it could result in a tie or the second team might win.

Therefore the minimum possible shots required to determine the absolute end result is 9.

I hope you understood. Incase something wasn't clear, feel free to ask me.

thank you :)

Looks like whoever prepared the problem, provided the solution.

Does that mean problem $$$B$$$ is prepared by BledDest and $$$D$$$ by Um_nik ?

(Sorry for the mentions)

An Easy to understand Recursive Solution of Problem BIt's complexity

For each character, we are exploring right as well left characters, so it should be O(n^2).

If you have noticed in editorial or not but I found this funny :-

Preparation: Will not be revealed for now because we care for his/their safety.:)i noticed that too.haha i wonder if they will be in danger if their handles are shown?

Easy to understand C++ implementation of problem B : 123307537

When I tried to see the tutorial of problem D, I saw "Tutorial is not available". However, someone has asked a problem about the problem D's tutorial, so if anyone can tell me what's wrong?

I tried solving B using two pointers, getting WA on TC 14. Can anyone point out what's wrong? 123384175

In D,many codes failed for test 19 ,you guys just have looked the things from back like say you have two strings str1 abd str2 with length n and m respectively. All you need to do is keep a pointer(j) for str2 starting from m-1 coming back to 0 and start iterating for str1 from n-1 (i) if you find such i such that str1[i]=str2[j] and elements which didinot match their count is even then just decrement j and iterate from i-1 .No edge case to be handled in it. You can see my submission,its simple to understand.

can u tell why i am getting wa on test 14 in prob B https://codeforces.com/contest/1553/submission/123345312

I think this guy AURRUM can help,he also got wrong answer on test 14 and he got it accepted now

thx bro

my solution was even simpler but had almost the same idea 123325031

This is the solution for D, I am asking for B. I got the idea of O(n^3) approach given in the tutorial, just curious what's wrong with my approach.

A very simple test for D would be the following:

It is no, because whatever you do, you cannot delete your remaining odd number of symbols(in this case $$$cde$$$) without affecting the other letters, simply because not adding another two symbols requires two(duh), and an odd number is obviously not a multiple of two.

That's the reason why solutions that worked from 1 to n failed, but those working from n to 1 passed. You can delete as many symbols from the beginning as you like, but this doesn't work for the end, you need to check whether the length from the position of your last taken character till the end of array is an even number. Only then it is possible.

Can anybody help me calculate the time complexity of my solution to B? I think it's O(n^4), but it passed the system test. Code here

Sorry it's O(n^3), my brain got stuck.

Oops, sorry about that!! Thanks to Nezzar and Rossoneri_Forever!!

It's lowercase in your output dude, here's the picture.

Your output is lowercase, I think the checker converted it to uppercase.

I have easier solution for problem D , if needed I will explain the code as well

Thanks for your solution.

Great contest from which I learned a lot

Because I have missed this multiple times in the past and I missed it in E again. So, as a reminder to myself and also for it may help others. These are two other problems which use Constraint Exploitation.

First

Second.

If you know of more such Problems, it would be nice if you could comment them down here.

For

Problem B, just enumerate all possible turing point (where you change direction), then you will get $$$|a|$$$ strings, which are $$$a'$$$s. Use KMP to query whether string $$$b$$$ is a substring of them, which costs $$$O(|a|(|b| + |a'|))$$$.Since first step cost $$$O(n^2)$$$, all the problem can be solved in $$$O(n^2)$$$

Code is here: https://codeforces.com/contest/1553/submission/123304298

For problem A, if we take n=100 then the possible interesting numbers are 9,18,27,36,45,54,63,72,81,90,99 so there are total of 11 interesting numbers but according to the solution given above the answer would be 10

Can someone explain this anomaly?

Thanks in advance!!

Interesting numbers should be numbers whose last digit is 9, not multiples of 9. So there are 10 in total.

okayy..I mistook as summing all digits until I get a single digit thank you!

For n=100, the possible interesting numbers are actually 9,19,29,39,49,59,69,79,89,99, which results in the answer becoming 10. other than 9,99 none of the numbers you mentioned are interesting, for example 18 : sum of digits is 9 18+1 = 19 : sum of digits is 10 which violates that S(19) < S(18) and therefore is not an interesting number. Similarly for the other numbers you mentioned. Hope this helped!

Deleted. 1001 way to overcomplicate your solution, lol.

Lol.I did the same thing. I initially did 200 times and got an unnecessary TLE because that.

123389429 can anyone help me in finding the error in my code for 2nd question

Auto comment: topic has been updated by Harbour.Space (previous revision, new revision, compare)."Preparation: Will not be revealed for now because we care for his/their safety."

Can someone provide tutorial for Um_nik solution of problem D. It would be really helpful.

Thanks in advanced :)

We first observe that if we type backspace, 2 characters in the origin text will be deleted. If the difference of the lengths between the origin text and the expected text is odd, then we must delete at least one character at the beginning of the origin text (which is what this

`int p = (n - m) & 1;`

and`for (int i = p;...)`

does). Then, if the character at s[i] == t[q], we can go and check the next. If not, then we must delete this mismatch. At mentioned at the beginning, we have to delete the both characters starting from the mismatch, which is what the variable k does. Now, at the end, if the index q == the length of expected text m, we have found a way. Otherwise, we cannot transform the origin text to the expected.And just saw the official editorial is also avaliable now.

in E's tutorial, what does — n/(n — 2n/3) signifies. I count cnt > n — 2m = n/3 why only 3 such counts are possible??

If the sum of many numbers is n, only three of them can be greater than n/3.

Thanks, I will read tutorial again, but can you explain why these 3 value of k are turned out to be only 0, 1, 2, 3?

I don't understand your question. Are you asking about some particular test? You might want to watch the video explanation too, it's in the first comment below the blog.

I got the solution completely, thank you so much, man...I don't know whether it will benefit me in the future or not to get problems solved using editorials and looking at other's code.

It will benefit you. Upsolving is much more important than solving problems during the contest.

Why are they not revealing who prepared certain questions? What security concerns are they worried about? Have there been any past incidents?

import java.util.*; import java.lang.*; import java.io.*; import java.math.*;

public class CODEFORCES {

} }

//This is my Solution of question 2, Getting wrong on test case 14 ,33 token but not knowing why Please can anyone help ?

Here is another solution for Problem D: Backspace

Solution

Despite several comments mentioning KMP/Z-function as applicable to problem B, I don't see any mentioning that it can actually be solved in linear time $$$O(|s| + |t|)$$$ with that tool.

The basic idea is that the 'turning point' where the chip goes from moving right in $$$s$$$ to moving left must happen in the middle of a palindromic suffix or prefix of $$$t$$$ with some odd length $$$2k+1$$$. The substring of $$$s$$$ visited by the chip in this case is then either the substring of $$$t$$$ without its last $$$k$$$ characters (for palindromic suffixes) or the reversal of the substring of $$$t$$$ without its first $$$k$$$ characters (for palindromic prefixes).

In either case, it is clearly optimal to take $$$k$$$ as large as possible, i.e. use the longest odd-length palindromic prefix or likewise suffix of $$$t$$$. These can easily be found in $$$O(|t|)$$$ with KMP/Z-function, and then the problem is reduced to testing $$$s$$$ for the presence of either of two substrings.

I felt like sharing my $$$\mathcal{O}(N \sqrt M + (M + N) \sqrt N)$$$ solution for F.

The basic idea of using the identity $$$a \text{ mod } b = a - b \lfloor \frac{a}{b} \rfloor$$$ and grouping queries by the same values of $$$\lfloor \frac{a}{b} \rfloor$$$ is the same as the tutorial. What is different is that when we are checking the $$$k$$$-th element $$$a_k$$$ we separate in two cases (1) $$$a_k <\sqrt M$$$ and (2) $$$a_k \geq \sqrt M$$$.

We also have an array $$$B$$$ of size $$$\sqrt M$$$ which is updated with the value of $$$x \lfloor \frac{a_k}{x} \rfloor$$$ for all $$$x \leq \sqrt M$$$ on each $$$a_k$$$.

To calculate the sum of $$$a_i \lfloor \frac{a_k}{a_i} \rfloor$$$ for $$$i < k$$$: If (1) $$$a_k <\sqrt M$$$, we just iterate over all $$$a_i < a_k$$$ (as simple optimization, not really needed), and if (2) $$$a_k \geq M$$$, we iterate over values of $$$\lfloor \frac{a_k}{a_i} \rfloor$$$, of which there are at most $$$2\times\lceil\sqrt a_k\rceil$$$.

To calculate the sum of $$$a_k \lfloor \frac{a_i}{a_k} \rfloor$$$ for $$$i < k$$$: If (1) $$$a_k <\sqrt M$$$, we get the value from array $$$B$$$, and if (2) $$$a_k \geq \sqrt M$$$ we query over at most $$$\sqrt M$$$ ranges and sum.

So far, it is not exactly clear how to avoid either having $$$\log M$$$ queries or $$$\log M$$$ updates. What we do now is to separate the array in $$$\sqrt N$$$ groups and update all auxiliary arrays only once for each group. The queries only account for the values of the previous groups, which means that the values missing are of $$$a_i \text{ mod } a_j$$$, for pairs that are in the same group. These values can be recovered offline by checking $$$(\sqrt N)^2$$$ pairs in each of the $$$\sqrt N$$$ groups.

Cool thing about this strategy is that (to my knowledge) it still works if there are repeated values in A.

code

For problem B, we can fix the segment [i,j] which goes from left to right, then calculate k, in that way we can fix the chip's route and then we can use hash to check. The time complexity is $$$O(n^2)$$$.

But I wonder whether we can solve it in an $$$O(n \log n)$$$ or quicker way.

the solution of Problem F may be wrong because it won't print any integer on test 26. Please check your standard solution, thanks.

What's wrong with test #26 of problem F? I don't know why the jury says the length of answer should be 0. I tried some AC codes, but they all get WA on test 26.

me too

Is there a problem with the 26th test point of question f? The code of the person I have used is still wrong. STD can't pass

Unfortunately, the testing on test 26 of problem F was malfunctioning for the last several hours (I don't know the exact reason, probably something with Codeforces cache). The problem is fixed by now, all submissions that failed test 26 will be rejudged in a few minutes.

Can someone please tell me why the answer to

cabad

should becabac

YESfor problemB? (Test case 14).TIA

If we move the chip position in the order 0, 1, 2, 1, 0 we get cabac.

Oh, I can't believe I missed that. I was considering the order 0, 1, 2, 3, and couldn't understand how I could get the 'c' from this. Thank you so much.

A solution for B works in O(n). Use Manacher and KMP. https://codeforces.com/contest/1553/submission/123674097

In problem E I think you mean the sum of cnt[k]= n, not n! This is why mathematicians shouldn't get overly excited (:

Has anyone tried to solve problem D using regex?

It's a pretty straightforward solution with regex but I'm getting TLE with Java/Python and I'm unable to use regex in C++

Can anyone told me why I am getting TLE on test 30 in Problem D? -_- I used binary search. Can it be a reason? Here is my solution :

https://codeforces.com/contest/1553/submission/126554472

Can anyone provide me with the testcase 7 for problem D.

Can we use submask enumeration technique to generate all possibilities for problem C?

Will preparation for B and D ever be revealed?

I don't know what could my code faces in prob B if it was like this (I run 2 times in string S and each of the identical character I found in string T[k], I will increase value K to k++. Because the problem is only allowed to move right then left in order so My solution could be uindertood as greedy. However I was wrong in test 9. If any one finished this please send me test 9 input or explain what I missed, thank you.

.