Educational Codeforces Round 196 — Editorial

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

#	User	Contrib.
1	Qingyu	156
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	135
7	adamant	135
9	maroonrk	132
10	cry	130

Tutorial

Solution

t = int(input())
for i in range(t):
    l, r = map(int, input().split())
    if r < 0 or l > 0:
        print(r - l)
    else:
        m = min(r, -l)
        print(max(0, r - l - 2 * m - 1))

2283B - Rhythmic String

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 1;
    for(int i = 0; i < n; i++)
    {
        int cur = 0;
        for(int j = 0; j < n; j++)
            if(a[j] % a[i] == 0)
                cur++;
        ans = max(ans, cur);
    }
    cout << n - 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();    
}

2283C - Big XOR

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;
    int k = 0;
    for(int i = 1; i <= n; i++) k |= i;
    int m = 0;
    vector<int> ans(n, 0);
    for(int i = 1; i <= n; i++) m ^= i;
    int d = 0;
    cout << k << endl;
    while((k >> d) & 1) d++;
    cout << d << endl;
    for(int i = d; i >= 1; i--)
        if(((m >> i) & 1) == 0)
        {
            int x = (1 << (i - 1));
            cout << x << endl;
            ans[x - 1] = 1;
            m ^= x;
            m ^= (x << 1);
        }
    for(int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << endl;
}

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

2283D - Black, Gray and White

Tutorial

Solution (awoo)

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int tc;
    cin >> tc;
    while (tc--){
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        forn(i, n - 1){
            int v, u;
            cin >> v >> u;
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        if (n % 2 == 0){
            cout << n + 1 << '\n';
            continue;
        }
        int ans = n;
        for (int k : {n + 1, n + 2}){
            int u = k == n + 1 ? n / 2 : 0;
            vector<int> clr(n, -1);
            queue<int> q;
            clr[u] = 0;
            int c = 1;
            forn(i, n) if (clr[i] == -1){
                q.push(i);
                clr[i] = c;
                while (!q.empty()){
                    int v = q.front();
                    q.pop();
                    for (int u : g[v]) if (clr[u] == -1){
                        clr[u] = c;
                        q.push(u);
                    }
                }
                ++c;
            }
            bool any = false;
            for (int i = 1; i <= n; ++i) if (k - i <= n && k - i != i)
                any |= clr[i - 1] != clr[k - i - 1];
            if (any)
                ans = k;
        }
        cout << ans << '\n';
    }
}

2283E - Partition of a Binary String

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

const int N = 5043;
const int MOD = 998244353;
int bell[N];
int C[N][N];
int dp[N];

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

void precalc()
{
    for(int i = 0; i < N; i++)
    {
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++)
            C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    }
    bell[0] = 1;
    for(int i = 1; i < N; i++)
        for(int k = 0; k < i; k++)
            bell[i] = add(bell[i], mul(C[i - 1][k], bell[i - k - 1]));
    dp[0] = 1;
    for(int i = 1; i < N; i++)
    {
        if(i >= 2) dp[i] = add(dp[i], dp[i - 2]);
        if(i >= 3) dp[i] = add(dp[i], dp[i - 3]);
    }
}


void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int zero = 0, one = 0, cur = 0;
    int ans = 1;
    int val = 0;
    for(int i = 0; i < n; i++)
    {
        bool neq_adj = false;
        if(i > 0 && s[i] != s[i - 1]) neq_adj = true;
        if(i + 1 < n && s[i] != s[i + 1]) neq_adj = true;
        if(i > 0 && s[i] == s[i - 1])
        {
            ans = mul(ans, dp[cur]);
            cur = 0;
        }
        if(neq_adj)
        {
            cur++;
            val += 2;
        }
        else
        {
            ans = mul(ans, dp[cur]);
            cur = 0;
            if(s[i] == '0') zero++;
            else one++;    
            val++;
        }
    }
    ans = mul(ans, dp[cur]);
    ans = mul(ans, bell[zero]);
    ans = mul(ans, bell[one]);
    cout << val << " " << ans << endl;
}

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

2283F - Minimize the Graph

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);

struct FenwickSum
{
    vector<int> f;
    int n;

    void add(int i, int x)
    {
        for(; i < n; i |= (i + 1))
            f[i] += x;
    }

    int get(int i)
    {
        int ans = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1)
            ans += f[i];
        return ans;    
    }

    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }

    FenwickSum(int n = 0) : n(n)
    {
        f.resize(n);
    }
};

struct event
{
    int moment;
    int type;
    int idx;
    event(int moment = 0, int type = 0, int idx = 0) : moment(moment), type(type), idx(idx) {};
};

bool operator<(const event& a, const event& b)
{
    if(a.moment != b.moment) return a.moment < b.moment;
    if(a.type != b.type) return a.type < b.type;
    return a.idx < b.idx;
}

void solve()
{
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for(int i = 1; i < n; i++)
    {
        cin >> l[i] >> r[i];     
        l[i]--;
    }

    vector<int> h(n, INF);
    set<int> s;
    for(int i = 0; i < n; i++) s.insert(i);
    for(int i = 1; i < n; i++)              
    {
        int lf = l[i];
        int rg = r[i];
        while(true)
        {
            auto it = s.lower_bound(lf);
            if(it == s.end() || *it >= rg) break;
            h[*it] = i;
            s.erase(it);
        }
    }

    vector<event> events;
    for(int i = 0; i < n; i++)
        events.push_back(event(h[i], 0, i));
    for(int i = 1; i < n; i++)
        events.push_back(event(r[i] - 1, 1, i));

    long long ans = 0;

    FenwickSum f(n + 1);
    for(int i = 0; i < n; i++)
        f.add(i, 1);

    sort(events.begin(), events.end());
    for(auto e : events)
        if(e.type == 0)
            f.add(e.idx, -1);
        else
        {
            int lf = l[e.idx];
            int rg = r[e.idx];
            ans += f.get(lf, rg - 1);
        }

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

2283G - Order Statistics on the Graph

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

const int N = 20;
const int V = 1 << N;
const int Q = int(1e5);

int adj_mask[N];
int idx[N];
int nxt[V];
vector<int> gt[V];
vector<pair<long long, int>> que[N];
int ans[N * Q];
bool used[V];
int cycle_pos[V];
vector<int> cycle;
vector<int> dfs_stack;

vector<int> get_unique(const vector<int>& a)
{
    vector<int> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    return b;
} 

vector<int> get_masks(const vector<int>& a)
{
    int n = a.size();
    auto b = get_unique(a);
    int m = b.size();
    vector<int> masks(m - 1);
    for(int i = 0; i < m - 1; i++)
    {
        int mask = 0;
        for(int j = 0; j < n; j++)
            if(a[j] > b[i])
                mask |= (1 << j);
        masks[i] = mask;
    }
    return masks;
}

vector<int> restore(const vector<int>& a, const vector<int>& masks)
{
    int n = a.size();
    auto b = get_unique(a);
    int m = b.size();
    vector<int> ans(n, b[0]);
    for(int i = 0; i < m - 1; i++)
        for(int j = 0; j < n; j++)
            if((masks[i] >> j) & 1)
                ans[j] = b[i + 1];
    return ans;
}

void dfs(int x)
{
    used[x] = true;
    int depth = dfs_stack.size();
    dfs_stack.push_back(x);
    for(auto y : gt[x])
        if(!used[y])
            dfs(y);
    for(auto [t, i] : que[x])
    {
        if(t <= depth)
            ans[i] = dfs_stack[depth - t];
        else
        {
            long long add = t - depth;
            int pos = (cycle_pos[dfs_stack[0]] + add) % cycle.size();
            ans[i] = cycle[pos];
        }
    }
    dfs_stack.pop_back();
}

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < n; i++)
        cin >> idx[i];
    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        adj_mask[y] |= (1 << x);
    }
    
    vector<long long> t(q);
    vector<vector<int>> a(q, vector<int>(n));
    for(int i = 0; i < q; i++)
    {
        cin >> t[i];
        for(int j = 0; j < n; j++)
            cin >> a[i][j];
    }

    int qid = 0;
    for(int i = 0; i < q; i++)
    {
        auto masks = get_masks(a[i]);
        for(auto mask : masks)
        {
            que[mask].push_back(make_pair(t[i], qid));
            qid++;
        }
    }

    for(int i = 0; i < (1 << n); i++)
    {
        int ni = 0;
        for(int j = 0; j < n; j++)
        {
            int cur_mask = adj_mask[j] & i;
            if(__builtin_popcount(cur_mask) >= idx[j])
                ni |= (1 << j); 
        }
        nxt[i] = ni;
        gt[ni].push_back(i);
    }

    for(int i = 0; i < (1 << n); i++)
    {
        if(used[i]) continue;
        int j = i;
        while(!used[j])
        {
            used[j] = true;
            j = nxt[j];
        }
        int k = j;
        cycle = {};
        do
        {
            cycle_pos[k] = cycle.size();
            cycle.push_back(k);
            k = nxt[k];
        }
        while(k != j);
        for(auto c : cycle) dfs(c);
    }

    qid = 0;
    for(int i = 0; i < q; i++)
    {
        auto masks = get_masks(a[i]);
        vector<int> res;
        for(int i = 0; i < masks.size(); i++)
        {
            res.push_back(ans[qid]);
            qid++;
        }
        vector<int> res2 = restore(a[i], res);
        for(auto x : res2) cout << x << " ";
        cout << "\n";
    }
}

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

#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/gimme.h" #else #pragma GCC optimize("Ofast") #pragma GCC optimize("O3","unroll-loops") #pragma GCC target("avx,avx2,fma") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define gimme(...) 42 #endif #define int long long #define vl vector<int> #define all(x) (x).begin(), (x).end() #define print(vec) for (auto x : vec) {cout << x << ' ';} cout << endl; #define pb push_back #define f first #define s second #define done '\n' #define Code_By_Faraz ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define Spooder signed #define sz(x) ((int) x.size()) #define yes(x) cout << (x ? "Yes\n" : "No\n"); constexpr long long INF = 4e18; const int Maxn = 5e5 + 67; // ---------------- Main Solution: ---------------- // 101% sure it is WRONG BUT PLZ BE ON WA 1 void Faraz() { int n; cin >> n; int Or = 0; for (int i = 0; i < n; ++i) { Or |= (i + 1); } Or *= 2; vl Ans(n + 1); Ans[n - 1] = 1; for (int i = 32; i >= 1; --i) { if ((Or & (1LL << i)) or (1LL << i) > n) continue; Ans[(1LL << (i - 1))] = 1; Ans.erase(Ans.begin()); print(Ans); return; } int Xor = (Ans[1] ? 2 : 1); for (int i = 2; i <= n; ++i) { if (Ans[i]) Xor ^= (2 * i); else Xor ^= (i); } for (int i = 32; i >= 0; --i) { if ((Or & (1LL << i)) == 0) continue; if (Xor & (1LL << i)) continue; Ans[(1LL << (i - 1))] = 1; Xor ^= (1LL << (i - 1)); Xor ^= (2 * (1LL << (i - 1))); } // if (Xor < Or) gimme(n); Ans.erase(Ans.begin()); print(Ans) } Spooder main() { Code_By_Faraz; #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cout << fixed << setprecision(10); int Test = 1; cin >> Test; while (Test--) { Faraz(); } return 0; }

void solve() { int n; cin >> n; vector<int> p(n + 1, 0); long long tmp = 0; for (int i = n; i >= 1; --i) { long long x = 2LL * i; if ((tmp ^ x) > tmp) { p[i] = 1; tmp ^= x; } else { tmp ^= i; } } for (int i = 1; i <= n; ++i) { cout << p[i] << " \n"[i == n]; } }

void solve(){ int n, ans = 0; cin >> n; vector<bool> a(n + 1); for(int i = 1; i <= n; i++) ans ^= i; for(int i = n; i > 0; i--) if(((ans ^ i) ^ (2 * i)) > ans) a[i] = 1, ans = (ans ^ i) ^ (2 * i); for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << "\n"; }

include <bits/stdc++.h>

using namespace std;

void dfs(vector<vector>&up,vector<vector>&adj,vector&tin,vector&tout, int node,int p,int &timer,int l) { tin[node] = ++timer; up[node][0] = p; for (int i = 1; i <= l; ++i) { up[node][i] = up[up[node][i — 1]][i — 1]; }

for (int u : adj[node]) { if (u != p) { dfs(up,adj,tin,tout,u,node,timer,l); } } tout[node] = ++timer; return;

}

bool is_ancestor(int u, int v,vector&tin,vector&tout) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }

int find_lca(int u, int v,int l,vector<vector>&up,vector&tin,vector&tout) { if (is_ancestor(u, v,tin,tout)) return u; if (is_ancestor(v, u,tin,tout)) return v; for (int i = l; i >= 0; --i) { if (!is_ancestor(up[u][i], v,tin,tout)) u = up[u][i]; } return up[u][0]; }

bool fun(int total,int target,int st,vector<vector>&up,vector&tin,vector&tout,int l) { while(1) { int end=total-st; if(st>=end) { break; }

int lca=find_lca(st,end,l,up,tin,tout); int l1=find_lca(target,st,l,up,tin,tout),l2=find_lca(target,lca,l,up,tin,tout); if(l1==target&&l2==lca) { return true; } int l3=find_lca(target,end,l,up,tin,tout); if(l3==target&&l2==lca) { return true; } st++; } return false;

}

signed main() { int t;cin>>t; while(t--) { int n;cin>>n; vector<vector>adj(n+1); for(int i=1;i<n;i++) { int u,v;cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); }

if(n%2==0) { cout<<n+1<<endl; } else { int l=ceil(log2(n)); vector<vector<int>>up(n+1,vector<int>(l+1,0)); vector<int>tin(n+1,0),tout(n+1,0); int timer=0; dfs(up,adj,tin,tout,1,1,timer,l); int st=1,a=1,st1=2; if(fun(n+1,(n+1)/2,st,up,tin,tout,l)) { cout<<n+1<<endl; } else if(fun(n+2,a,st1,up,tin,tout,l)) { cout<<n+2<<endl; } else if(fun(n,n,st,up,tin,tout,l)) { cout<<n<<endl; } else { cout<<n+1<<endl; } }

}

} ```````````` // This is solution using LCA .

Comments (22)

Write comment?

ireallyhatethis

13 hours ago, hide # |

← Rev. 4 →

G can be solved with simple brute force over all 2^N masks + binary lifting lol

Code

#include <bits/stdc++.h>

const int LOG = 60;

void cook() {
    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<int> k(n), in(n);

    for (int &x : k) std::cin >> x;

    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        --u; --v;
        in[v] |= 1 << u;
    }

    int S = 1 << n;
    std::vector<std::vector<int>> up(LOG, std::vector<int>(S));

    for (int mask = 0; mask < S; mask++) {
        for (int v = 0; v < n; v++)
            if (__builtin_popcount((unsigned)(mask & in[v])) >= k[v])
                up[0][mask] |= 1 << v;
    }

    for (int j = 1; j < LOG; j++)
        for (int mask = 0; mask < S; mask++)
            up[j][mask] = up[j-1][up[j-1][mask]];

    while (q--) {
        long long t;
        std::cin >> t;

        std::vector<std::pair<int, int>> a(n);

        for (int i = 0; i < n; i++) {
            std::cin >> a[i].first;
            a[i].second = i;
        }

        std::sort(a.begin(), a.end());

        std::vector<int> ans(n);
        int mask = 0, done = 0;

        for (int i = 0; i < n;) {
            int j = i, x = a[i].first;

            while (j < n && a[j].first == x)
                mask |= 1 << a[j++].second;

            int cur = mask;

            for (int b = 0; b < LOG; b++)
                if (t >> b & 1LL)
                    cur = up[b][cur];

            int add = cur & ~done;

            while (add) {
                int v = __builtin_ctz((unsigned)add);
                ans[v] = x;
                add &= add - 1;
            }

            done |= cur;
            i = j;
        }

        for (int i = 0; i < n; i++)
            std::cout << ans[i] << " \n"[i == n - 1];
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    cook();
    return 0;
}

and an alternative approach for C would be, we just need to choose which numbers from 1 to N to double so that the XOR of the resulting array is at least twice the bitwise OR of the original array

The key observation is that we only need to double powers of two. Their effects on the XOR allow us to construct the exact target value

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

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

    int k = 0, m = 0;

    for (int i = 1; i <= n; i++) {
        k |= i;
        m ^= i;
    }

    int d = 0;
    while ((k >> d) & 1)
        d++;

    vector<int> ans(n, 0);

    for (int i = d; i >= 1; i--) {
        if (((m >> i) & 1) == 0) {
            int x = (1 << (i - 1));

            ans[x - 1] = 1;

            m ^= x;
            m ^= (x << 1);
        }
    }

    for (int x : ans)
        cout << x << " ";
    cout << '\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;

    while (t--) {
        cook();
    }

    return 0;
}

→ Reply

IanISam

6 hours ago, hide # ^ |

The brute force in-question,

Although main thing is that even though binary lifting was one of the intended solutions actually passing it under the time contraint is difficult.

SachinnSadvelkarr

thanks for the solutions sir!

ibrm

F can be solved just using lazy segment trees 397403664.

KnownAsJason

12 hours ago, hide # |

I had nearly an identical solution to E in my head lmao.

bina

9 hours ago, hide # |

Combination of 2 distinct dps on E was amazing!

Faraz

8 hours ago, hide # |

← Rev. 2 →

Hello! My approach for problem C was as follows:

First, calculate 2 * OR of all elements. We now need to set the MSB (Most Significant Bit) in our XOR, which is present in 2 * OR. We also know that if the previous MSB of the OR was at position (x), it will now be at (x + 1) (since multiplying by 2 left-shifts all set bits). Therefore, we can double the (N)-th element since it has the largest MSB, left-shifting it sets the MSB of 2 * OR in our XOR. Let (X = 2 * OR). We iterate from the highest bits downward. If a bit is set in (X) but not in our XOR, then obv we have will try to Set it cuz even if we set all the smaller bits still X will be > Since Sum of all bits from 0..i (2 ^ 0 + 2 ^ 1.. 2 ^ i < 2 ^ (i + 1) )Doubling an element equal to 1LL << (i — 1) (2 ^ (i — 1)) left-shifts its bit, which sets that bit in our XOR, so we update the XOR accordingly.

Here is my solution: 397390036

Code:

The main reason I'm posting this is to ask: is my code hackable? I mistakenly wrote Ans[N — 1] = 1 instead of Ans[N] = 1 (I accidentally mixed up 0-based and 1-based indexing) and it got AC during contest.

Ayanami_Rei_

I have a greedy approach for Problem C.

Greedy: Process numbers from large to small

Key observation The bitwise OR of all integers from 1 to n is always a number consisting entirely of consecutive 1-bits. Let L be the highest set bit of n. Then k = (1 << (L + 1)) — 1, and 2*k has all bits from position 1 to L+1 set to 1 (using 0-based indexing). Also, every chosen value is at most 2*n, so the final XOR is smaller than 2^(L+2). Therefore, we only need to make bits 1 through L+1 of the final XOR equal to 1. The result will automatically be either 2*k or 2*k+1.
Greedy strategy Process i from n down to 1, maintaining tmp, the XOR of all processed elements. For each i:

If replacing i with 2*i makes tmp larger, choose 2*i.
Otherwise, keep i unchanged.

In code:

if ((tmp ^ (2 * i)) > tmp) {
    p[i] = 1;
    tmp ^= (2 * i);
} else {
    tmp ^= i;
}

Why does this work? Group the numbers according to their highest set bit. For a group containing numbers in the range [2^q, 2^(q+1)-1], doubling any number in this group makes its highest set bit exactly q+1. The comparison tmp ^ (2*i) > tmp has a simple meaning:

If bit q+1 of tmp is 0, doubling i makes the XOR larger, so we double it and turn this bit into 1.
If bit q+1 is already 1, doubling i makes the XOR smaller, so we keep i unchanged. Since we process numbers in descending order, the first number in each group will set bit q+1 to 1 if necessary. All remaining numbers in that group are kept unchanged, so they cannot affect this bit. After finishing a group, its corresponding bit is guaranteed to be 1. Moreover, all numbers in subsequent groups are smaller. Neither their original values nor their doubled values can affect any previously fixed higher bit. Thus, we can greedily fix all required bits from high to low, guaranteeing that the final XOR is at least 2*k.

Implementation:

Here, p[i] = 1 means choosing 2*i; otherwise, we choose i.

PiggyPump

7 hours ago, hide # |

Come on, people were complaining how C was harder than D. I clearly disagree, you needed to know how to binary lift and rip an LCA to solve D effectively.

For C, as long as you knew how to type ^, then you could solve C.

HCCoder

7 hours ago, hide # ^ |

D is very basic, while C requires more thinking though you don't need to know hard algos

2 hours ago, hide # ^ |

You don't need binary lifting for D tho?

Analysisss

6 hours ago, hide # |

Another implementation of C is to greedily multiply the numbers, starting with the largest.

daishuwei2007

Wow, noticed the std for A is Python :). But I think maybe the last line print(max(0, r - l - 2 * m)) is missing a - 1 according to the tutorial formula. Is this a new anti-plagiarism feature, or just a cute little typo? ovo

BledDest

4 hours ago, hide # ^ |

Whoops, I accidentally uploaded the wrong version of A. Thank you for noticing, fixed it.

arkabanerjee863

If you are noob like me, you will make the whole xor basis first then try to maximise xorsum greedily :(

Code : 397392370

ACE_fireFist12

3 hours ago, hide # |

Damn the editorial approach for D is so much better i used LCA + difference tree (idk the name i just wrote difference array for tree) the algo itself was simple just a lot of preprocessing the color tree thing is way more beautiful

PassingShadow

are the educational rounds of codeforces is tougher than usual div 2?

Ciallos

Well, I found myself forget to turn off sync_with_stdio and use endl instead of '\n', leading to two TLE of D :(

Pri8899

2 hours ago, hide # |

I think this round was way too easy compared to the others. I solved 2 problems without a single failure.

MASRAFI_MaSni

Solution of problem D using LCA ```````` //This is the code

rustem.memmedli.

78 minutes ago, hide # |

thanks for the lightning-fast editorial chef!

Adree

19 minutes ago, hide # |

Problem C soln(different way) :- ****

An Elegant O(N) Approach Using Branch Labeling (Subtree Tracking)

I wanted to share my approach for this problem because I found a way to solve it optimally in O(N) time by smartly choosing tree roots and tracking which branch every node belongs to.

Here is the breakdown of the logic:

1. The Base Case (Even N) If N is even, the answer is always simply N + 1. No traversal is needed.

2. The Odd Case (Testing Candidates) If N is odd, the answer will be one of three candidates: N, N + 1, or N + 2. Instead of doing something complex, we can just test these three candidate values of K in ascending order. Since we want to update our answer if a valid state is found, looping K from N to N + 2 naturally leaves us with the highest valid candidate.

For each candidate K, we pick a very specific root to hang the tree from: * If K = N, root = N * If K = N + 1, root = (N / 2) + 1 * If K = N + 2, root = 1

3. The "Second Parent" (Branch Labeling) Technique Once we select the root for our candidate K, we need to check if there is a valid pair of nodes (i, target) where target = K — i, such that they lie in different branches connected to the root.

To do this efficiently, I used a second_parent array: * I iterate through all immediate children of the root. * For each child, I run a DFS to traverse its entire subtree. * During this DFS, every node in that subtree is tagged with that specific child as its second_parent (essentially labeling which main branch of the root it belongs to).

4. The Validation Step After the tree is fully labeled, validating the candidate K takes just O(N) time: * Iterate through all possible nodes i from 1 to N. * Calculate the required pair: target = K - i. * If the target is valid (1 <= target <= N and target != i), we just check their labels: if (second_parent[i] != second_parent[target]). * If they have different branch labels, they don't share the same immediate branch from the root, meaning we found a valid pair for this K! We update our answer me = K.

Complexity: Because we only test 3 candidates when N is odd, we run a standard DFS and a simple linear scan 3 times. * Time Complexity: O(N) * Space/Memory: O(N) for the adjacency list and the second_parent array.

You can check out my implementation here: Submission #397399210

Hope this helps anyone looking for a clean linear-time solution! Let me know if you have any questions about the routing logic.

BledDest's blog

include <bits/stdc++.h>

An Elegant O(N) Approach Using Branch Labeling (Subtree Tracking)