Educational Codeforces Round 182 Editorial

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3408
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

#	User	Contrib.
1	Qingyu	154
2	nik_exists	151
3	maspy	149
4	AmShZ	146
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	135
9	maroonrk	133
10	cry	130

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 (35)

Show archived | Write comment?

Rudraksh

14 months ago, hide # |

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

→ Reply

gevak

14 months ago, hide # ^ |

There is indeed: https://codeforces.me/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://codeforces.me/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?

Alts are against the CF rules. Refer to https://codeforces.me/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?

-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

13 months ago, hide # ^ |

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

code_guitar_master

10 months ago, hide # ^ |

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

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

Tadas

12 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?

10 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

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

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

awoo's blog