Educational Codeforces Round 192 Editorial

#	User	Rating
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

#	User	Contrib.
1	Qingyu	158
2	maspy	150
3	Um_nik	146
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	DNR	133
8	Dominater069	131
9	Proof_by_QED	130
10	BledDest	129

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;
}

#include <bits/stdc++.h> using namespace std; #define ll long long #define vii(vi) vector<vector<ll>> vi #define vi(v) vector<ll> v #define faur(b,i) for(int i = 0; i<b;i++) #define MOD 1000000007 int main() { int t; cin >> t; while (t--) { int n ; cin>> n; vector<ll>arr(n); faur(n,i){ cin>>arr[i] ;} int cnt = 0; int temp = 0; faur(n,i){ if(cnt == 0){ if(arr[i]!=1){ temp++ ; } else if(temp){ temp --; if(temp==0){cnt = 1; temp = 0;} } else{ if(i){ cnt = 1; } else{ if (arr[1]==3){i++ ;} cnt = 1; } } } else if(cnt == 1){ if(arr[i]==3){ temp++ ; } else if(temp){ temp --; if(temp==0){ if(i != n-1) cnt = 2; } } else{ if(i != n-1) cnt = 2; } } } (cnt==2)?cout<<"yes" : cout<<"no" ; cout<<endl ; } return 0; }

void solve() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> c(n + 1); for (int i = 0; i < n;) { int j = i; while (j < n && a[j] == a[i]) j++; c[j - i]++; i = j; } long long ans = 0; long long s1 = 0, s2 = 0; for (int i = n; i >= 1; i--) { s1 += c[i]; s2 += s1; if (c[i] && k >= s2 && (k - s2) % s1 == 0) { ans++; } } cout << ans << '\n'; }

Comments (59)

Write comment?

greateric

2 months ago, hide # |

← Rev. 2 →

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

Spoiler

→ Reply

wery0

2 months ago, hide # ^ |

+12

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)

-6

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

rex333

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

Thanks bro

Redpanda_x

+15

But in that case you will have to deal with different blocks merging together:

For example take: 2 2 1 2 2 2

After 1 delete op: 2 2 2

After 2 delete op: 2 2

So being sorted is actually needed for this solution to work.

Literalhahaha

perhaps it remain the same,I don't think it needs to change

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

+21

Yep, it barely works: 381648337

very nice solution, thank you!

WeakBlood

does not pass anymore XD 381822292

abcd1145

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

Aryan_ism

5 weeks ago, hide # ^ |

so easy;

VOI27

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.

t.o.i.cyril

6 weeks ago, hide # ^ |

wow

monkey

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

windforce_shafi

The B was very difficult to solve .

mjm_hu

Are You Kidding?!

I wish I was! I struggled a bit with the logic/implementation. Do you have any tips or a cleaner approach for it?

You bet! You can just solve it with a brute-force approach. First, check whether the left segment is feasible. If it is, start checking the middle segment from the end of the left segment. If you still can't find a valid partition, keep extending the left segment and repeat the process until you either find a valid partition or determine that none exists.I wish my approach can hope you , it is O(n^2)(I think)

Darksorcen

7 weeks ago, hide # ^ |

A bit late, but I'm surprised it passed (even in python)

Oh!thank you very much.♥

rajakrishna

← Rev. 4 →

refrxn

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

Ryaminty

My idea is similar to yours by setting dp(i, j) as x where x is the number of blocks after dividing a[0:i] and b[0:j], given that sum(a[0:j])%10=sum(b[0:j])%10. But getting dp(i, j) is a bit different than yours.

It's pretty easy to tell that dp(i, j)=max(dp(i2, j2))+1 where i2<i and j2<j, if you try to do that intuitively it will TLE. but we can optimize by using a segment tree.

Use a segment tree of size j, and segtree[j] is max(dp(i2, j)) for i2<i. We update segtree[j] as max(dp(i, j), segtree[j]) after each iterating through all j for each i. Our final answer will be dp(n-1, m-1). My submission optimized the dp array as 1D but it's probably not necessary.

submission: 383874331

mang-o3

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

CaptainTormentor

That's not greedy that's god level process of elimination in coding

zensei

I also did using greedy but way simpler. Ideas was that for the first block, if you have excess ones for some odd length segment, its better to include the next element in the segment if it is a 3. In general this is a greedy problem only in my opinion. As you only mostly need to construct the first segment rightfully. 2nd and 3rd segment constructions are quite trivial. I initially was constructing first segment by only checking if the number of ones are >= len/2 but it failed on example test case 9. Then I came up with the include 3 logic which was a quick fix to my inital greedy solution. Although yes I do agree with you, this is definitely not a 900 rated problem. Neither is C a 1260 rated problem as shown in CList. I have done many problems and I am pretty sure B is at least 1100-1200 and C is 1400-1500. Here is my submission for B btw:

381477898

dang3r

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).

Neu2daysago

wait how did it get acc?

Revision: i have submitted 30+ solutions on this problem, and quite i say pragma is very weird idk if im right, but im pretty sure it has something to do with "Cache Locality" where code runs faster if it has more "predictive" requests

honestly, crazy work. this type of optimization is scarily useful, but i will not try to master this optimization

NegativeFeedback

+10

I think it doesn't have anything to do with cache locality. The compiler cannot vectorise your loop (Loop Analysis) because of how it is structured, in his code his outer loop is the one iterating over a[i] the inner loop is completely independent (that is for all j = [0 ... i]) it can be done in parallel, the compiler can see this and use Vector Instructions to do it which is fast enough to overcome TLE. Regardless of how you do it (j = [1...i] or j = [0...i]) you will have cache locality because you are accessing elements in a contiguous range.

ohhh, so like working in parallel/pipelining. that makes more sense

vectorization is the handling of predictable instructions to an array/vector that can speed up time complexity. that is easier to think about when i want to save time

thanks for the PositiveFeedback

Hi, The flag prediction stalls the pipeline as overhead. Moreover, you may read about programming Branchless Instructions. cppcon yt is great to start with.

Soultaker

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.

← Rev. 3 →

You can make it run a lot faster using bitset: 381533453

keysky

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

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.

ItsNotMeItsYou

I'm guessing that modulo operations caused so many people to get TLE. I wrote $$$O(Tn\log^2V)$$$ without using modulo operations. And it got AC in 1200 ms: 381493456

You need bitset or good constant optimization to pass

DreamChaser

A clean $$$O(N)$$$ approach for 2242C — Unstable Elements

Every operation changes each block's frequency by $$$+1$$$ or $$$-1$$$. If only blocks with initial frequency $$$\ge i$$$ survive, we define $$$s_1$$$ as the number of active blocks, and $$$s_2$$$ as their baseline total size.

When shifting the index down from $$$i$$$ to $$$i-1$$$, each already surviving block grows by $$$1$$$ and we discover $$$c[i-1]$$$ new blocks, giving the natural recurrence $$$s_1^{(i-1)} = s_1^{(i)} + c[i-1]$$$ and $$$s_2^{(i-1)} = s_2^{(i)} + s_1^{(i-1)}$$$. Since subsequent operations expand all $$$s_1$$$ blocks uniformly, $$$k$$$ is reachable if $$$k \ge s_2$$$ and $$$(k - s_2) \pmod{s_1} == 0$$$.

Feel free to upvote if you found this helpful!

kutkrr

such an elegant solution, how did you come up with this approach

can you suggest some other problems with similar technique

Thanks! The core idea is just observing the invariant: all blocks with an initial size $$$\ge i$$$ must survive and grow together as a single group.

By processing the survival threshold in reverse, we avoid complex forward simulation and just maintain a simple linear state.

For similar techniques, I'd recommend looking into the Contribution to the Sum technique, or problems that use 1D Sweep-line / Frequency Prefix Sums to dynamically maintain global active states.

Thanks man, never heard of the topic you mentioned but I will definately check them out

staines

I think you missed a '}' after 'else cur++;' in solution of C.

Edit: nvm, my bad

jakharpranjal

I solved B using backtracking though i looped through the array finding suitable first partition and for each such half found i would find the second half.

jay_1410

'B' could be solved without prefix or suffix arrays, with few observations.

Few observations for B:

Part 3 can be any suffix of the array (the condition will be always true, because there is no element greater than 3)
Now we only care about Part 1 and Part 2. Part 1 is a the first prefix such that count(1) >= count(2) + count(3). Fix this as Part 1 for now.
Now we will start our Part 2, if we encounter either 1 or 2, we can just conclude our part 2. But if we encounter 3, then we can check if its possible to extend our part 1, such that count(1) >= count(2) + count(3) is still true (somewhat like kadane's algo). Also, if we carefully observe, extending part 1, will add only elements '3'. Because, if my part 2 had either '1' or '2' at the left, then there it self condition count(1) + count(2) >= count(3) will be satisfied, and rest will be Part 3.

submission

Follow-up

I used a similar approach but simplified it even further:

If the array starts with [1, 3], then that is part 1. Otherwise, part 1 is the shortest prefix that satisfies count(1) >= count(2) + count(3).
Part 2 is the next shortest segment that satisfies count(1) + count(2) >= count(3).
Part 3 is the rest of the array. (The only requirement is that the segment is nonempty.)

The logic behind step 1 is that adding a "bad" element to an existing segment only makes sense if that segment had odd length, which allows us to get rid of a bad element "for free" (i.e. without having to compensate for it with a good element later in the segment). But that only happens when the array starts with 1, otherwise part 1 will have even length.

Your solution effectively does the same thing, you just have to notice that with only 3 parts, the sum < 0 && prevsum > 0 clause can only trigger when i == 2 and it requires a[0] == 1 && a[1] == 3.

t.muksunov

For me B was harder than C. Managed to solve C myself after contest, but not B

abhi.seth

I solved B using a different greedy approach 381515455. I felt this method was easier to prove.Just take two functions: f(arr) = c1 — c2 — c3 and g(arr) = c1 + c2 — c3. Since g() = f() + 2*c2 and c2 cannot be negative, we have g(arr) >= f(arr). Assume a solution exists with partitions P1*, P2*, and P3*. If we choose P1 such that the total number of elements in it has the same parity as P1*, then the extra part, say M, has an even number of elements, so f(M) is also even. We can show that f(M) >= -1. Since it is even, f(M) >= 0. Thus, g(M) >= f(M) >= 0, so g(M + P2*) >= 0. Therefore, if P2* satisfies the property, then M + P2* will also satisfy it.

runtime99terror

7 weeks ago, hide # |

is it just me or is D easier than C

DDV_my

How about Div2?

longyitongxue

6 weeks ago, hide # |

The 2242D - Two Digit Strings is pretty interesting. Even using $$$\mathcal O(n)$$$ to find the LCS, I still get WA. I have to to use $$$\mathcal O(n^2)$$$ to pass….

I can prove that my $$$\mathcal O(n)$$$ algorithm is right, so that's pretty interesting you know?

SACHIN263159

11 days ago, hide # |

388067046 An alternative O(K) time and O(1) space approach for Problem A without sorting or arrays:

Instead of storing frequencies and sorting or tracking top elements, we can accumulate a running sum of only the counts strictly greater than 1 during input streaming:

If a count is > 1, its minimum value is 2.
The only impossible configurations occur when there are no elements >= 2 (sum = 0) or exactly one element equal to 2 (sum = 2).
Any sum >= 3 mathematically guarantees either a single element >= 3 (Type 1 overlap) or at least two elements >= 2 (Type 2 pair).

Thus, the entire check reduces to sum >= 3.

BledDest's blog

A clean $$$O(N)$$$ approach for 2242C — Unstable Elements