Educational Codeforces Round 182 Editorial

Tutorial

Solution (BledDest)

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if sum(a) % 3 == 0:
        print("1 2")
    else:
        print("0 0")

2144B - Maximum Cost Permutation

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> pos0;
    vector<int> used(n);
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        --p[i];
        if(p[i] == -1)
            pos0.push_back(i);
        else
            used[p[i]] = 1;
    }
    if(pos0.size() == 1) 
    {
        int unused = 0;
        for(int i = 0; i < n; i++) if(used[i] == 0) unused = i;
        p[pos0[0]] = unused;
    }
    int l = 0, r = n - 1;
    while(l < n && p[l] == l) l++;
    while(r >= 0 && p[r] == r) r--;
    cout << max(0, r - l + 1) << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

2144C - Non-Descending Arrays

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      if (a[i] > b[i]) swap(a[i], b[i]);
      if (!i || a[i] >= b[i - 1]) ans = (ans * 2LL) % MOD;
    }
    cout << ans << '\n';
  }
}

2144D - Price Tags

Idea: BledDest

Tutorial

Solution (adedalic)

for _t in range(int(input())):
    n, y = map(int, input().split())
    a = list(map(int, input().split()))
    A = max(a) + 1
    cntTags = [0] * A
    for v in a:
        cntTags[v] += 1
    pSum = [0] * A
    for i in range(1, A):
        pSum[i] = pSum[i - 1] + cntTags[i]
    
    ans = -(10**18)
    if A == 2:
        print(n)
        continue
    for x in range(2, A):
        res = 0
        for price in range(1, A):
            l = x * (price - 1)
            r = min(A - 1, x * price)
            if l >= A:
                break
            cnt = pSum[r] - pSum[l]
            res += cnt * price
            res -= y * max(0, cnt - cntTags[price])
        ans = max(ans, res)
    print(ans)

2144E1 - Looking at Towers (easy version)

Idea: Roms

Tutorial

2144E2 - Looking at Towers (difficult version)

Idea: Roms

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int N = 1000043;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}
 
int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}   
 
int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}
 
vector<int> get(const vector<int>& a)
{
    int cur = -1;
    vector<int> res;
    for(auto x : a)
        if(x > cur)
        {
            res.push_back(x);
            cur = x;
        }
    return res;
}
 
struct SegTree
{
    vector<int> f;
    vector<int> t;
    int n;
 
    int getVal(int v, int pos)
    {
        return mul(t[pos], binpow(2, f[v]));
    }   
 
    void push(int v)
    {
        if(f[v] != 0)
        {
            f[2 * v + 1] += f[v];
            f[2 * v + 2] += f[v];
            f[v] = 0;
        }
    }
 
    void resolve(int v, int pos)
    {
        if(f[v] != 0)
        {
            t[pos] = mul(t[pos], binpow(2, f[v]));
            f[v] = 0;    
        }
    }
 
    int get(int v, int l, int r, int pos)
    {
        if(l == r - 1)
            return getVal(v, pos);
        else
        {
            push(v);
            int m = (l + r) / 2;
            if(pos < m)
                return get(v * 2 + 1, l, m, pos);
            else
                return get(v * 2 + 2, m, r, pos);
        }
    }
 
    int get(int pos)
    {
        return get(0, 0, n, pos);
    }
 
    void inc(int v, int l, int r, int pos, int val)
    {
        if(l == r - 1)
        {
            resolve(v, pos);
            t[pos] = add(t[pos], val);
        }
        else
        {
            push(v);
            int m = (l + r) / 2;
            if(pos < m)
                inc(v * 2 + 1, l, m, pos, val);
            else
                inc(v * 2 + 2, m, r, pos, val);
        }
    }
 
    void inc(int pos, int val)
    {
        return inc(0, 0, n, pos, val);
    }
 
    void mulBy2(int v, int l, int r, int L, int R)
    {
        if(L >= R) return;
        if(l == L && r == R)
            f[v]++;
        else
        {
            push(v);
            int m = (l + r) / 2;
            mulBy2(v * 2 + 1, l, m, L, min(R, m));
            mulBy2(v * 2 + 2, m, r, max(L, m), R);
        }
    }
 
    void mulBy2(int l, int r)
    {
        mulBy2(0, 0, n, l, r);   
    }
 
    SegTree(int n = 0)
    {
        this->n = n;
        f.resize(4 * n);
        t.resize(n);
    }
};
 
vector<int> calc(const vector<int>& a, const vector<int>& b)
{
    int n = a.size();
    int m = b.size();
    SegTree tree(m + 1);
    tree.inc(0, 1);
    vector<int> res(n);
    int maxVal = b.back();
    for(int i = 0; i < n; i++)
    {
        int x = a[i];
        if(x > maxVal) continue;
        else
        {
            if (x == maxVal) res[i] = tree.get(m - 1);
            int lf = lower_bound(b.begin(), b.end(), x) - b.begin();
            tree.mulBy2(lf + 1, m + 1);
            if(b[lf] == x)
            {
                int cur = tree.get(lf);
                tree.inc(lf + 1, cur);
            }
        }
    }
    return res; 
}   
 
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    auto left_view = get(a);
    reverse(a.begin(), a.end());
    auto right_view = get(a);
    reverse(a.begin(), a.end());
 
    auto dpL = calc(a, left_view);
    reverse(a.begin(), a.end());
    auto dpR = calc(a, right_view);
    reverse(a.begin(), a.end());
    reverse(dpR.begin(), dpR.end());
 
    int maxVal = *max_element(a.begin(), a.end());
    int ans = 0;
    int sumLeft = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] > maxVal) continue;
        else
        {   
            if(a[i] == maxVal) ans = add(ans, mul(add(sumLeft, dpL[i]), dpR[i]));
            sumLeft = mul(sumLeft, 2);
            if(a[i] == maxVal) sumLeft = add(sumLeft, dpL[i]);
        }
    }
    cout << ans << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) solve();
}

2144F - Bracket Groups

Idea: BledDest

Tutorial

Solution 1 (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const string al = "()";
 
struct aho_corasick {
    static const int AL = 2;
 
    struct node {
        int nxt[AL], go[AL];
        int p, pch;
        int suf, ssuf;
        bool term;
        
        node() {
            memset(nxt, -1, sizeof(nxt));
            memset(go, -1, sizeof(go));
            suf = ssuf = -1;
            term = false;
        }
    };
 
    vector<node> nodes;
    vector<vector<int>> g;
    
    aho_corasick() {
        nodes.push_back(node());
    }
 
    void add(const string& s) {
        int v = 0;
        forn(i, s.size()) {
            int c = al.find(s[i]);
            if (nodes[v].nxt[c] == -1) {
                nodes.push_back(node());
                nodes[v].nxt[c] = nodes.size() - 1;
                nodes.back().p = v;
                nodes.back().pch = c;
            }
            v = nodes[v].nxt[c];
        }
        nodes[v].term = true;
    }
    
    int go(int v, int c) {
        if (nodes[v].go[c] != -1)
            return nodes[v].go[c];
        if (nodes[v].nxt[c] != -1)
            return nodes[v].go[c] = nodes[v].nxt[c];
        if (v == 0)
            return nodes[v].go[c] = 0;
        return nodes[v].go[c] = go(suf(v), c);
    }
    
    int suf(int v) {
        if (nodes[v].suf != -1)
            return nodes[v].suf;
        if (v == 0 || nodes[v].p == 0)
            return nodes[v].suf = 0;
        return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
    }
    
    int ssuf(int v) {
        if (nodes[v].ssuf != -1)
            return nodes[v].ssuf;
        if (v == 0 || nodes[v].p == 0)
            return nodes[v].ssuf = 0;
        int s = suf(v);
        if (nodes[s].term)
            return nodes[v].ssuf = s;
        return nodes[v].ssuf = ssuf(s);
    }
    
    void build_tree() {
        g.resize(nodes.size());
        forn(v, nodes.size()) {
            int u = suf(v);
            if (v != u)
                g[u].push_back(v);
        }
    }
};
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    forn(i, n) cin >> s[i];
    forn(i, n) if (s[i] == "()"){
        cout << -1 << '\n';
        return 0;
    }
    aho_corasick ac;
    forn(i, n) ac.add(s[i]);
    vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.nodes.size(), vector<char>(k + 1)));
    vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.nodes.size(), vector<pair<int, int>>(k + 1)));
    dp[0][0][0] = true;
    forn(i, k) forn(v, ac.nodes.size()) forn(bal, i + 1) if (dp[i][v][bal]){
        forn(c, 2){
            int nbal = bal + (c == 0 ? 1 : -1);
            if (nbal < 0) continue;
            int u = ac.go(v, c);
            if (ac.nodes[u].term || ac.ssuf(u) != 0) continue;
            dp[i + 1][u][nbal] = true;
            p[i + 1][u][nbal] = {v, c};
        }
    }
    int sv = -1;
    forn(v, ac.nodes.size()) if (dp[k][v][0]){
        sv = v;
        break;
    }
    if (sv == -1){
        cout << 2 << '\n';
        vector<string> res(2);
        forn(i, k / 2){
            res[0] += "()";
            res[1] += '(';
        }
        forn(i, k / 2){
            res[1] += ')';
        }
        vector<vector<int>> ans(2);
        forn(i, n){
            bool any = false;
            forn(j, int(s[i].size()) - 1)
                any |= s[i][j] == s[i][j + 1];
            ans[!any].push_back(i);
        }
        forn(i, 2){
            cout << res[i] << '\n';
            cout << ans[i].size() << '\n';
            for (int j : ans[i]) cout << j + 1 << " ";
            cout << '\n';
        }
    }
    else{
        cout << 1 << '\n';
        string res = "";
        int bal = 0, v = sv;
        for (int i = k; i > 0; --i){
            auto [u, c] = p[i][v][bal];
            v = u;
            res += al[c];
            bal -= c == 0 ? 1 : -1;
        }
        reverse(res.begin(), res.end());
        cout << res << '\n';
        cout << n << '\n';
        forn(i, n) cout << i + 1 << " ";
        cout << '\n';
    }
    return 0;
}

Solution 2 (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const string al = "()";
 
int main() {
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    forn(i, n) cin >> s[i];
    forn(i, n) if (s[i] == "()"){
        cout << -1 << '\n';
        return 0;
    }
 
    vector<string> ac(1, "");
    forn(i, n) forn(j, s[i].size())
        ac.push_back(s[i].substr(0, j + 1));
    sort(ac.begin(), ac.end());
    ac.resize(unique(ac.begin(), ac.end()) - ac.begin());
 
    vector<char> bad(ac.size());
    set<string> tot(s.begin(), s.end());
    vector<vector<int>> go(ac.size(), vector<int>(2));
    forn(i, ac.size()) forn(j, ac[i].size() + 1){
        bad[i] |= tot.count(ac[i].substr(j));
        forn(t, 2) if (go[i][t] == 0){
            string nw = ac[i].substr(j) + al[t];
            auto it = lower_bound(ac.begin(), ac.end(), nw);
            if (it != ac.end() && *it == nw)
                go[i][t] = it - ac.begin();
        }
    }
 
    vector<vector<vector<char>>> dp(k + 1, vector<vector<char>>(ac.size(), vector<char>(k + 1)));
    vector<vector<vector<pair<int, int>>>> p(k + 1, vector<vector<pair<int, int>>>(ac.size(), vector<pair<int, int>>(k + 1)));
    dp[0][0][0] = true;
    forn(i, k) forn(v, ac.size()) forn(bal, i + 1) if (dp[i][v][bal]){
        forn(c, 2){
            int nbal = bal + (c == 0 ? 1 : -1);
            if (nbal < 0) continue;
            int u = go[v][c];
            if (bad[u]) continue;
            dp[i + 1][u][nbal] = true;
            p[i + 1][u][nbal] = {v, c};
        }
    }
    int sv = -1;
    forn(v, ac.size()) if (dp[k][v][0]){
        sv = v;
        break;
    }
    if (sv == -1){
        cout << 2 << '\n';
        vector<string> res(2);
        forn(i, k / 2){
            res[0] += "()";
            res[1] += '(';
        }
        forn(i, k / 2){
            res[1] += ')';
        }
        vector<vector<int>> ans(2);
        forn(i, n){
            bool any = false;
            forn(j, int(s[i].size()) - 1)
                any |= s[i][j] == s[i][j + 1];
            ans[!any].push_back(i);
        }
        forn(i, 2){
            cout << res[i] << '\n';
            cout << ans[i].size() << '\n';
            for (int j : ans[i]) cout << j + 1 << " ";
            cout << '\n';
        }
    }
    else{
        cout << 1 << '\n';
        string res = "";
        int bal = 0, v = sv;
        for (int i = k; i > 0; --i){
            auto [u, c] = p[i][v][bal];
            v = u;
            res += al[c];
            bal -= c == 0 ? 1 : -1;
        }
        reverse(res.begin(), res.end());
        cout << res << '\n';
        cout << n << '\n';
        forn(i, n) cout << i + 1 << " ";
        cout << '\n';
    }
    return 0;
}

Comments (45)

Write comment?

Rudraksh

7 months ago, hide # |

is there any way to solve problem D in $$$O(n \sqrt{n})$$$, no right?

→ Reply

gevak

7 months ago, hide # ^ |

There is indeed: https://mirror.codeforces.com/contest/2144/submission/338809275

virinci

Looks $$$O(n \cdot \log n)$$$ to me. No way $$$O(n \cdot \sqrt{n})$$$ would pass because my $$$O(n \cdot \log n \cdot \log n)$$$ TLEd.

0mar

← Rev. 2 →

$$$O(n^2)$$$ with heuristics passes. Should be possible to hack it though if anyone is interested.

https://mirror.codeforces.com/contest/2144/submission/338807854

BledDest

+13

I think this is $$$O(n \sqrt{n})$$$ at worst. The if-statement containing the inner loop for $$$j$$$ is started only $$$O(\sqrt{n})$$$ times because you run it only if $$$count_i \gt cnt0$$$, and you update $$$cnt0$$$ with $$$count_i$$$. Since the sum of all $$$count_i$$$ is at most $$$n$$$, then $$$count_i$$$ will be greater than $$$cnt0$$$ only $$$O(\sqrt n)$$$ times.

Maybe it's possible to prove even better complexity.

upd wait, I was wrong. I can't prove that the sum of $$$count_i$$$ is $$$O(n)$$$, but I can prove that it's $$$O(n \log n)$$$. This would result in a complexity of $$$O(n \sqrt{n \log n})$$$.

chromate00

+49

I think you will be astonished when you realize that $$$2\cdot (\log_2 n)^2 \gt \sqrt{n}$$$ for all $$$2 \le n \le 500\,000$$$

astonished indeed

That still o(nlogn) bro

Seems you are right. Didn't though about complexity really, thought that it just will work.

Noobish_Monk

+23

Problem E2 can be solved without any data structure more advanced than Fenwick tree (which supports increasing some value by $$$1$$$ and get a prefix sum of values).

$$$dp_i$$$ is the number of subsequences on prefix till $$$i$$$ such that the last element picked is $$$a_i$$$ and it's a record. Then $$$dp_i = \sum_{j \lt i: a_j = previousRecord} dp_j 2^{no. \ k: j \lt k \lt i, a_k \le a_j}$$$.

Let's introduce two arrays $$$le_i$$$ and $$$pr_i$$$. $$$le_i$$$ is the number of positions $$$j \le i: a_j \le a_i$$$ for $$$pr_i$$$ we would replace $$$a_i$$$ with the previous record.

Then $$$dp_i = \sum_{j \lt i: a_j = previousRecord} dp_j 2^{pr_i - le_j}$$$

$$$\frac{dp_i}{2^{pr_i}} = \sum_{j \lt i: a_j = previousRecord} \frac{dp_j}{2^{le_j}}$$$

So one can just maintain the sum of $$$\frac{dp_j}{2^{le_j}}$$$ for all records.

$$$le_i$$$ and $$$pr_i$$$ can be calculated with Fenwick tree.

338782926

Snowdust

Hey Noobish_Monk, if you don't mind, could you explain this code ... only explaining the filling of pref[ ] part will be enough ( You can assume, I know Monotonic stack stuff, Fenweek tree and Coordinate compression ). Thank you!

PokemonMaster

For D:

First attempts. After fixing a value of x I tried to get the answer “almost in O(1)” — somehow compute the total new prices and the printing penalty in one go. In practice, without grouping items by their target price p, you keep losing track of what you’re adding to revenue vs. what you’re paying for extra labels. A full rescan over all items costs O(n) per x, which is too slow.

Think like a sieve. I remembered the Sieve of Eratosthenes: the work on step i is about N/i, so the total is N log N. Same philosophy here: on step x you process buckets — contiguous price ranges of width x. There are about A/x buckets. If you pre-aggregate once (prefix sums) so each bucket costs O(1), then the total over all x is A * (1/2 + 1/3 + …) = A log A. The analogy is simple: the sieve marks multiples; we “mark” contiguous ranges. In both cases, organizing work by natural groups gives you a harmonic series instead of chasing impossible O(1) per step.

$$$\log n$$$ is not real, it can't hurt you.

Got bit by it cause my solution for D was $$$O(n \cdot \log n \cdot \log n)$$$.

ishowguts

-30

Title: Appeal: False Plagiarism Flag for Submission 338775909 (Problem 2144D) Hey MikeMirzayanov awoo adedalic Neon Roms BledDest, My handle is ishowguts. Submission 338775909 for problem 2144D was flagged as coinciding with submission 338766632, but I wrote all the code myself offline in VS Code with no collaboration. Development timeline & evidence: * First save: September 15, 2025 at 9:03 PM IST * Last save: September 15, 2025 at 9:54 PM IST * All file “last modified” timestamps in my local workspace reflect this period * I never uploaded or shared my code on any public IDE or platform during development * I implemented each function and logic block manually in this session  Please manually review both my code and the other submission. If you need any more evidence, I am ready to provide it.awoo Thank you for your time and understanding. 

You are not fooling anyone. And, file stats can be spoofed. Your account is too new, and rising too fast. You submissions from previous contests are skipped too. So, stop spamming in each thread.

P.S. I think CF should, optionally, allow linking to IDs on other CP platforms to prove authenticity.

-18

This is my 2nd I'd and for the authenticity part just check my codes and if you notice that something is fishy you can dm me or in the next contest maybe we can hop on discord call and solve the questions in front of you, so please don't comment without knowing the full picture and for the last skipped question i submitted the same code of my main account in this account as unrated at that time I didn't knew that even unrated contest also gets skipped, and when u check for official submissions ull not see any skipped submissions. Thank u.

nabhya_p

bro just quit it your code for E1 is basically unreadable almost no one other than some insanely high rated people write code like that, how hard is it learn some basics of CP and then give the contests honestly?

-32

1st of all u shut up i aint talking to you and please stop stalking my profile get a job lil nega, and for the learning basics for cp any day i can make a account and get to 1500-1600 easily and so please stay otta this

Alts are against the CF rules. Refer to https://mirror.codeforces.com/blog/entry/124418
Really, dude? Did you look at both the submissions? All you did was rename some variables and make the formatting worse, somehow, and replaced '\n' with an endl.
if(!(cin >> T)) return 0; what does this even do?
The other account is clearly a temp account, probably made just to help others cheat.
I see you have dabbled in several different programming languages. Python, C, Go, Rust, C++, etc.

Why are you trying so hard on this lost cause? Did you want that Expert so bad?

-15

I understand the skepticism, but if I were truly trying so hard to reach Expert by cheating, I would have done so from the very beginning and not waited until now. Also, if I’d been cheating all along, I wouldn’t have been caught on just this one problem—especially since it’s not among the harder problems. My rapid improvement and this single false flag reflect automated detection quirks, not dishonest behavior.

The line

cpp if(!(cin >> T)) return 0; is a simple input guard to exit if reading T fails in custom tests.which many competitive programmers use, I spent ~50 minutes coding this solution (timestamps provided). Any similarity comes from the standard DP approach required here. I’m happy to share my full VS Code workspace metadata or do a live session to prove my process. I only ask for the manual review allowed by the appeal process.

-12

and for the alts account at that time i didnt actually knew that making 2nd id is prohibited as many of my uni friends had 2-3 ids at that time, and i did got banned for that particular reason and didnt raised my voice after i got to know

lew2018

Cheater don't need to explain.... It just makes you look like a joker.

Luckwet

Am I the only one who eventually came up with an O(N) solution for C, but doubted its correctness because N <= 100?

m_manasc

Me too, eventually decided to just submit and check.

esh_war2

how to do C? Other ways different from tutorial way.

code_guitar_master

4 months ago, hide # ^ |

I used DP — https://mirror.codeforces.com/contest/2144/submission/356308309

invoker._

Was it just me, or did C feel a bit harder than D? C’s implementation looks straightforward, but the proof that dp[i] = 2 * dp[i+1] || d[i] = d[i+1] felt a bit tricky to reason out.

AntennaeVY

I just reasoned the possible cases when deciding to swap or not to swap two elements and always calculate only those that lead to a non-decreasing sequence in both arrays https://mirror.codeforces.com/contest/2144/submission/339440995

Mrkimedo

Why it take yall so long to post the editorial bruh im tryna get educated its an eeucational round twin

mrinmoy66sadhukhan

it ok.. they try their best.. :)

why c constraints so low if solution is so fast?? I was hoping to see a brute force solution. I like those.

I think there is typo in C editorial.. answer is 2^m.. where m tells number of type 1 pairs not number of segment of type 2 pairs.

sarvagya2545

My solution for E1 was slightly different than the one given in the editorial: 339030512

Is it possible to come to an optimization for E2's constraints using this E1 solution?

Celebrate

A bruteforce check can also pass F.

code

Allen.123

There is a typo in the solution of E1: calculaye -> calculate

zemayne

Can someone help me with problem C, please?

Editorial of the problem C says, "Let's initially swap the elements in those pairs where ai>bi; the answer will not change (since the 2^n subsets of indices we are considering will yield the same results after such a transformation, just in a different order)."

Why will the answer not change if I initially swap the elements???? Editorial doesn't say anything about it.

Wait, I think I have found something:

We can develop a relation between the set of indices of original(before swapping) state and transformed(after swapping) state.

T = S △ F

Here:

T = Any set of good indices of transformed array.

S = Any set of good indices of Original array.

F = set of swapped indecis.

△ = Symetric Difference.

and also: S = T △ F

Let say we can find(let's say by brutforce) all the valid subsets of good indeces for the original arrays a and b, which will make the arrays a and b sorted. We are representing each of them by S.

Now, after swapping all F indecis, the arrays a and b are now sorted in non-decreasing order. And now subset of good indecis is the one which will not make the array a and b unsorted. We are representing each of these subsets of indecis by T.

Now see the following example: Let, a = [2, 1, 3, 5, 4]

b = [1, 3, 3, 4, 6]

Here, F = [1 4]

After swapping index 1 and 4:

a = [1 1 3 4 4]

b = [2 3 3 5 6]

Let S = {1,3,4}, a set of good indices for original arrays a and b.

According to the relation: T = S △ F

= {1,3,4} △ {1, 4}

= {3}

So, T = {3} is a good subset of indecis for transformed arrays a and b. If we just swap the index 3 in transformed arrays a and b, it will not change the sorting order of the transformed arrays a and b. So for each valid subset of good index of original array a and b, we will find a valid index for the transformed a and b.

We can also go back from transformed subset of index to original subset of index. Let say we have a valid subset of good index for transformed a and b, and that is T = {3}. Now we want to know what the original good subset of index for this one is:

S = T △ F
  = {3} △ {1, 4}
  = {1,3,4} 
  = this is an original good subset of index.

So if we can just find number of good subset of indeces of the transformed a and b, that will be the answer.

gu0zisheng2011

-8

Nice Round,so much useful tricks!

Rastoool

Sanid

6 months ago, hide # |

Does Anyone have the tutorial for the solution of 2144C - Non-Descending Arrays using dynamic programming?

Tadas

5 months ago, hide # |

I have a few questions about C editorial. It's stated that "the answer is $$$2^m$$$ , where m is the number of segments of type 2 pairs.", but I think it's misleading as single type 1 pair is independent and can contribute to the result with $$$*2$$$ multiplier, so it's not only about type 2 segments? I don't quite understand the explanation for $$$2^{n-k}$$$ (merges), but the inverted calculation in solution code is more explanatory: $$$2^{k+1}$$$, where extra $$$1$$$ power is for the starting position (we can choose any order) and $$$k$$$ here is the number of such $$$i$$$ such that $$$a_i \geq b_{i - 1}$$$ (we can choose any order for $$$i$$$ position, but subsequent $$$i+1$$$ if it's type 1 pair is dependent on this chosen order and must adapt accordingly, we have no freedom there).

Also, is the following reasoning for "the answer will not change (since the $$$2^n$$$ subsets of indices we are considering will yield the same results after such a transformation, just in a different order)." part correct: we assume that all swaps start from ordered state (all $$$a_i \leq b_i$$$) and answer uniqueness rely on that if there are two swaps for the same position in the end, the result is that there were no swaps performed for $$$i$$$, i.e. the thing that we performed some operations at the beginning doesn't matter because we can revert them and this leads to same answer count?

4 months ago, hide # |

For C, what about the case when a = 4 3 b = 5 7

Then there is no subset of indices after which the array would be in non descending order, but you say a subset would always exist how?

prateekbhaisora

3 months ago, hide # ^ |

The constraint is given on the input. The inputs are created in such a way that at least one good subset exists.

Ohh ,Yeah I did not check that

CSRRS

3 months ago, hide # |

dp solution for C https://mirror.codeforces.com/contest/2144/submission/358841645

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

awoo's blog