Educational Codeforces Round 192 Editorial

Tutorial

Solution (BledDest)

t = int(input())
for i in range(t):
    k = int(input())
    a = list(map(int, input().split()))
    if max(a) > 2 or a.count(2) > 1:
        print('YES')
    else:
        print('NO')

2242B - Predominant Frequency Division

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include <bits/stdc++.h>
 
using namespace std;

const int INF = 1'000'000'007;
 
void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}

	vector<int> pref1(n + 1);
	vector<int> pref2(n + 1);
	for (int i = 0; i < n; i++){
		pref1[i + 1] = pref1[i] + (a[i] == 1 ? 1 : -1);
		pref2[i + 1] = pref2[i] + (a[i] == 3 ? -1 : 1);
	}

	int mn = INF;
	for (int i = 1; i < n; i++){
		if (pref2[i] - mn >= 0){
			cout << "YES\n";
			return;
		}
		if (pref1[i] >= 0){
			mn = min(mn, pref2[i]);
		}
	}

	cout << "NO\n";
}

 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

2242C - Unstable Elements

Idea: BledDest

Tutorial

Solution (BledDest)

#include <bits/stdc++.h>

using namespace std;

void solve() 
{
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> a[i];
    }
    
    vector<int> lens;

    int cur = 1;
    for (int i = 1; i < n; i++) 
        if (a[i] != a[i - 1]) 
        {
            lens.push_back(cur);
            cur = 1;
        } 
        else cur++;
    lens.push_back(cur);
    sort(lens.begin(), lens.end());

    int m = (int)lens.size();
    int d = 0;

    int ans = 0;
    int i = 0;
    while(i < m)
    {
        int len = lens[i];
        int x = len - 1;
        int q = m - i;
        int curLen = n - d - x * q;
        if (curLen <= k && (k - curLen) % q == 0)
            ans++;
            
        int j = i;
        while (j < m && lens[j] == len)
            j++;
        d += (j - i) * lens[i];
        i = j;
    }

    cout << ans << '\n';
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

2242D - Two Digit Strings

Idea: Roms

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

void upd(int& x, int y)
{
    if(x < y) x = y;
}

void solve()
{
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    vector<int> ps(n + 1), pt(m + 1);
    for(int i = 0; i < n; i++)
        ps[i + 1] = (ps[i] + (s[i] - '0')) % 10;
    for(int i = 0; i < m; i++)
        pt[i + 1] = (pt[i] + (t[i] - '0')) % 10;
    n++;
    m++;
    if(ps.back() != pt.back())
    {
        cout << -1 << "\n";
        return;
    }

    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            if(i < n) upd(dp[i + 1][j], dp[i][j]);
            if(j < m) upd(dp[i][j + 1], dp[i][j]);
            if(i < n && j < m && ps[i] == pt[j]) upd(dp[i + 1][j + 1], dp[i][j] + 1);
        }
    cout << dp[n][m] - 1 << "\n";
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

2242E - Product of Closures

Idea: adedalic

Tutorial

Solution (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	fore(i, 0, sz(v)) {
		if(i) out << " ";
		out << v[i];
	}
	return out;
}

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int l, r, n;

void solve() {
	cin >> l >> r >> n;
	
	int k = 63 - __builtin_clzll(r);
	int x = -1, y = -1;
	if (l >= (1ll << k)) {
		int p = 30;
		while (((l >> p) & 1) == ((r >> p) & 1))
			p--;
		assert(p >= 0);
		x = l;
		y = l - (l & ((1 << p) - 1)) + (1 << p);
	}
	else {
		x = max(l, (1 << (k - 1)));
		y = 1ll << k;
	}
	cerr << l << " " << r << ": " << x << " " << y << endl;
	assert(l <= x && x < y && y <= r);

	auto getBinary = [](int v) {
		vector<int> rep;
		while (v > 0) {
			rep.push_back(v & 1);
			v >>= 1;
		}
		reverse(rep.begin(), rep.end());
		return rep;
	};

	auto x_bits = getBinary(x);
	auto y_bits = getBinary(y);

	string ans(n, '0');
	fore (i, 0, n)
		ans[i] = '0' + (x_bits[i % x_bits.size()] & y_bits[i % y_bits.size()]);
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);

	int t; cin >> t;
	while (t--) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

2242F - Summer Vacation

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include <bits/stdc++.h>

using namespace std;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MX = 200000;
const int REBUILD_EVERY = 5000;

struct item {
    int value, cnt;
    int l, r;

    item(): value(0), cnt(0), l(0), r(0) {}
    item(int x): value(x), cnt(1), l(0), r(0) {}
};

vector<item> treap(1);

int copy(int v) {
    treap.push_back(treap[v]);
    return int(treap.size()) - 1;
}

int cnt(int v) {
    return v ? treap[v].cnt : 0;
}

void upd_cnt(int v) {
    if (v) {
        treap[v].cnt = cnt(treap[v].l) + cnt(treap[v].r) + 1;
    }
}

int merge(int l, int r) {
    if (!l || !r) {
        return l ? l : r;
    }

    int rang = rng() % (cnt(l) + cnt(r));

    if (rang < cnt(l)) {
        int res = copy(l);
        treap[res].r = merge(treap[res].r, r);
        upd_cnt(res);
        return res;
    } else {
        int res = copy(r);
        treap[res].l = merge(l, treap[res].l);
        upd_cnt(res);
        return res;
    }
}

int find_first(int v) {
    if (!treap[v].l) {
        return treap[v].value;
    } else {
        return find_first(treap[v].l);
    }
}

void dfs(int v) {
    if (!v) {
        return;
    }

    if (treap[v].l) {
        dfs(treap[v].l);
    }

    cout << treap[v].value << ' ';

    if (treap[v].r) {
        dfs(treap[v].r);
    }
}

pair<int, int> split(int t, int key, int add = 0) {
    if (!t) {
        return make_pair(0, 0);
    }

    t = copy(t);

    int cur_key = add + cnt(treap[t].l);

    if (key <= cur_key) {
        auto [l, r] = split(treap[t].l, key, add);
        treap[t].l = r;
        r = t;
        upd_cnt(t);
        return {l, r};
    } else {
        auto [l, r] = split(treap[t].r, key, add + 1 + cnt(treap[t].l));
        treap[t].r = l;
        l = t;
        upd_cnt(t);
        return {l, r};
    }
}

int change(int x, int it) {
    auto [l, r] = split(it, x, 0);
    auto [rl, rr] = split(r, x, 0);
    auto [l1, r1] = split(it, MX - x, 0);
    return merge(rl, l1);
}

void collect_values(int v, vector<int>& values) {
    if (!v) {
        return;
    }

    collect_values(treap[v].l, values);
    values.push_back(treap[v].value);
    collect_values(treap[v].r, values);
}

int build_balanced(const vector<int>& values, int l, int r) {
    if (l >= r) {
        return 0;
    }

    int m = (l + r) / 2;

    treap.emplace_back(values[m]);
    int v = int(treap.size()) - 1;

    treap[v].l = build_balanced(values, l, m);
    treap[v].r = build_balanced(values, m + 1, r);

    upd_cnt(v);
    return v;
}

int rebuild(int tr) {
    vector<int> values;
    values.reserve(cnt(tr));

    collect_values(tr, values);

    treap.clear();
    treap.emplace_back();

    return build_balanced(values, 0, int(values.size()));
}

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> ans(n);

    treap.reserve((size_t)((1 << 25) * 1.5));

    int tr = 0;

    for (int i = 0; i < MX; i++) {
        treap.emplace_back(i);
        tr = merge(tr, int(treap.size()) - 1);
    }

    int changed_iterations = 0;

    for (int i = n - 1; i >= 0; i--) {
        tr = change(a[i], tr);
        ans[i] = find_first(tr);

        changed_iterations++;

        if (changed_iterations % REBUILD_EVERY == 0) {
            tr = rebuild(tr);
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        cout << ans[i] << ' ';
    }
}

signed main() {
#ifdef FELIX
    auto _clock_start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int tests = 1;
    // cin >> tests;

    while (tests--) {
        solve();
    }

#ifdef FELIX
    cerr << "Executed in "
         << chrono::duration_cast<chrono::milliseconds>(
                chrono::high_resolution_clock::now() - _clock_start
            ).count()
         << "ms."
         << endl;
#endif

    return 0;
}

Comments (25)

Write comment?

greateric

12 hours ago, hide # |

← Rev. 2 →

How cooked am I if my first thought to solving B is range update range query

Spoiler

→ Reply

wery0

11 hours ago, hide # ^ |

Not as cooked as me when I solved Div.2 C by directly constructing string of length $$$10^{18}$$$ with persistent treap :D

57378448 (7 years ago, damn)

9 hours ago, hide # ^ |

-6

I still don't know what a treap is :sob:

rex333

11 hours ago, hide # |

How to solve C if the array is not sorted?

joshBurger

Technically the array doesn't need to be sorted, since the condition was for a[i] != a[i-1], not a[i] > a[i-1], meaning that same numbers had to be grouped next to each other. Something like 1 1 1 5 5 3 3 3 2 2 9 9 7 7 7, which you can easily count the number of marked elements for.

For arrays in which same numbers aren't grouped together, for example like 1 3 5 2 3 1 4 3 1 5, you can just treat every element as a different group

8 hours ago, hide # ^ |

Thanks bro

madamadam

did anyone solve problem F using std::rope? My solution is 7 lines, but unfortunately the relatively low time limit and std::rope having a terrible implementation means it TLEs even with periodic rebuilds. (even O(nsqrt(n)) block decomposition implementation is faster)

code

void solve() {
    int n; cin >> n;
    vector<int> a(n); for (auto &x : a) cin >> x;

    rope<int> r; for (int i = 0; i < 2*n; i++) r.push_back(i);
    for(int i = n-1; i >= 0; i--) {
        cout << r[a[i]] << " ";
        r = r.substr(a[i], a[i]) + r.substr(0, 2*n - a[i]);
    }
}

AksLolCoding

6 hours ago, hide # ^ |

+13

Yep, it barely works: 381648337

very nice solution, thank you!

abcd1145

3 hours ago, hide # ^ |

The underlying implementation of std::rope is a persistent balanced tree. It's $$$O(n\log n)$$$ but has a large constant factor.

It sometimes can't even beat the brute force solution.

High_Range

Extremely hard B

VOI27

10 hours ago, hide # |

D was a good problem though. In contest I did not recognize how to transform such a hard problem into an easy one. Great job, authors.

arnab_baishnab

In Problem C, I missed the fact that the array was sorted. I ended up using DSU to connect the gaps, overcomplicating the solution that took more than 60 minutes during the contest. Here's the solution.

monkey

9 hours ago, hide # |

what a cool solution for D... I honestly thought it was subsegment DP or smth

windforce_shafi

The B was very difficult to solve .

rajakrishna

8 hours ago, hide # |

← Rev. 3 →

damm! nice solution for d observing the opertaion on prefix sums very good!!!i did not gain any elo but at first div3 were like heaven to me lots of learning now education div2 are heaven lots of learning hope someday div2 will be heaven then div1 too.... Love your contests and the way you teach in editoriLs BledDest love it !!

refrxn

7 hours ago, hide # |

I would love to learn from someone if they have approaches for D different from the editorial

juan_del_forest

My idea doesn't use prefix sums,

First, lets consider when the answer is -1. As we can see, each operation doesn't change the sum of digits in a number modulo $$$10$$$.

Lets follow this idea a little, we consider some consecutive pairs of digits that we will never do an operation on(in both numbers). These pairs separate both digits into "blocks", that, after applying all operations will become single digits. As we can see, the goal in this task, is to separate those 2 numbersinto the same (maximum) number of blocks, where the blocks have the same sums modulo $$$10$$$ (i mean the first block in s1, has the same mod sum as the first block in s2 and so on).

Let $$$dp(i,j)$$$ be the maximum number of blocks that we can divide the prefix of length $$$i$$$ in $$$s1$$$, and the prefix of length $$$j$$$ in $$$s2$$$, it is easy to calculate this (you would have to consider $$$O(n)$$$ blocks) $$$dp$$$ in $$$O(n^3)$$$ time.

But fortunately, there is an optimization, consider the index $$$i$$$, and the maximum $$$l$$$ such that $$$l \leq i$$$, and $$$\sum_{j = l}^{i}{s_j} \equiv d \pmod{10} $$$, where $$$d \in$$$ { $$$0,1 \dots, 9$$$ } where $$$s$$$ is either $$$s1$$$ or $$$s2$$$, it doesn't matter for this optimization. let $$$l_1$$$ be the maximum index such that $$$l_1 \leq l$$$, and $$$\sum_{j = l_1}^{i}{s_j}$$$, as you can see, $$$\sum_{j=l_i}^{l-1}{s_j} \equiv 0 \pmod{10}$$$, so we can simply consider the smallest block with the sum, and don't worry about the rest.

submission : 381524391

mang-o3

6 hours ago, hide # |

I like how B is rated 881 on clist, because its definitely a 900 level problem. Sure, i mean prefix and suffix arrays were historically 1200 level concepts. But surely theres nothing fishy going on here, right? I guess everyone just got 300 points better

portajohn

I solved B without prefix/suffix arrays, with one greedy loop: 381481048

dang3r

4 hours ago, hide # |

Thanks for the amazing problems, but I like to point out that the problem F constrained with 1.5 second actually lets through a brute force solution with vectorization. Was this intentional? I was shocked to read the problem and finding it easier than B (the wording could have been simpler for B and C).

Soultaker

3 hours ago, hide # |

← Rev. 4 →

Problem 2242E - Product of Closures was fun. I couldn't figure out all the edge cases during the contest, but managed to solve it afterwards with a simpler but less efficient solution that runs in $$$\mathcal{O}(n \log^2 r)$$$ per testcase. With up to 1000 cases per test it's kind of pushing it, but apparently it still runs in under 1 second: 381658269

The idea is simple:

solution for problem E

Let's define $$$f(x, y)$$$ as the product of closures of $$$x$$$ and $$$y$$$ calculated up to length $$$n$$$. We are looking for the minimal $$$f(x, y)$$$ across all pairs $$$x, y$$$ satisfying $$$l ≤ x \lt y ≤ r$$$. Assuming $$$n ≥ \log_2 r ≤ 30$$$ we can calculate $$$f(x, y)$$$ in $$$\mathcal{O}(n)$$$ time. This immediately gives an $$$\mathcal{O}(nr^2)$$$ bruteforce solution just trying all possible pairs (x, y).

To make this faster, the key insight is that we only need to consider a few values of x and y. If we have $$$x_1$$$ and $$$x_2$$$ such that l <= x1 && x1 < x2 && (x1 & x2) == x1 then $$$x_1$$$ is strictly better than $$$x_2$$$, because $$$x_1$$$ has zeroes in all the places $$$x_2$$$ does (but $$$x_2$$$ has at least one 1 where $$$x_1$$$ has a 0), and therefore $$$f(x_1, y) \le f(x_2, y)$$$ for any $$$y$$$. That means we only need to consider values of $$$x$$$ that aren't dominated by a smaller number.

Viewed in a different way, if we have a number $$$x_2 \gt l$$$ and we define $$$x_1$$$ as $$$x_2$$$ with its lowest 1-bit cleared, then if $$$x_1 ≥ l$$$ it dominates $$$x_2$$$ and we don't need to consider $$$x_2$$$. Of course we can apply the same logic to $$$x_1$$$ clearing its lowest bit, and so on, until we end up with a number that has the following form: a prefix of $$$l$$$, followed by a 1-bit where $$$l$$$ has a 0-bit (making $$$x \gt l$$$) and the remaining bits set to zero (otherwise, would clear them to obtain a smaller $$$x \gt l$$$).

For example, when $$$l = 20$$$ (10100 in binary):

x = 000010100 = 20
x = 000010101 = 21
x = 000010110 = 22
x = 000011000 = 24
x = 000100000 = 32
x = 001000000 = 64
etc.

We can stop when $$$x$$$ exceeds $$$r$$$, and given $$$r ≤ 2^{30}$$$ this gives at most 30 values to try. Then for $$$y$$$ we can use the same logic to come up with 29 values to try, for a total of $$$30×29=870$$$ pairs.

I have no idea if this approach was considered and supposed to pass. The main benefit is that you can find this solution by optimizing the bruteforce solution, without doing any of the complicated casework.

keysky

119 minutes ago, hide # |

How can I copy a subtree (e.g. $$$\color{blue}{4}, \color{blue}{5}, \color{blue}{0}, \color{blue}{1}$$$) and move them to two different positions within feasible time complexity in question F.

MaxBlazeIceInk

60 minutes ago, hide # |

Solve E in $$$O(Tn\log^2V)$$$ too,and failed on system test.

I heard that there're only 6 weak pretests in problem E,which was misleading.

#	User	Rating
1	jiangly	3728
2	VivaciousAubergine	3647
3	Kevin114514	3625
4	maroonrk	3555
5	strapple	3515
6	tourist	3439
7	Um_nik	3376
7	turmax	3376
9	Radewoosh	3367
10	qiuzx	3343

#	User	Contrib.
1	Qingyu	163
2	Um_nik	145
3	adamant	142
4	Dominater069	137
5	chromate00	133
5	DNR	133
7	maroonrk	132
7	cry	132
7	maspy	132
10	Proof_by_QED	131

BledDest's blog