Разбор Codeforces Round 1103 (Div. 3)

Разбор

Решение (arsen1y)

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int INF = (int) 1e18;
 
int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int _;
    cin >> _;
 
    while (_--) {
        int n;
        cin >> n;
 
        vector <int> a(n);
        int mx = -INF;
        int mn = INF;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            mx = max(mx, a[i]);
            mn = min(mn, a[i]);
        }
 
        cout << mx - mn + 1 << "\n";
    }
 
    return 0;
}

2236B - Tatar TV Show

Идея: eyfxrby

Подсказка

Разбор

Решение (eyfxrby)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        string s; cin >> s;
        vector<int> cnt(k, 0);
        for (int i = 0; i < n; i++) cnt[i % k] += s[i] - '0';
        bool ok = true;
        for (int r = 0; r < k; r++) {
            if (cnt[r] % 2) {
                ok = false;
                break;
            }
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }
}

2236C - Omsk Programmers

Идея: arsen1y

Подсказка

Разбор

Решение (arsen1y)

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int INF = (int) 1e18;
 
int32_t main() {
    int _;
    cin >> _;
 
    while (_--) {
        int a, b, x;
        cin >> a >> b >> x;
 
        int ans = INF;
        int i = 0;
        while (a != b) {
            if (b > a) {
                swap(a, b);
            }
 
            ans = min(ans, abs(a - b) + i);
            a /= x;
            i++;
        }
 
        ans = min(ans, i);
 
        cout << ans << "\n";
    }
 
    return 0;
}

2236D - Brand New Tatar TV Show

Идея: dvb1r

Подсказка 1

Подсказка 2

Разбор

Решение (dvb1r)

#include <bits/stdc++.h>

using namespace std;
void solve();

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

void solve() {
    int n, k; cin >> n >> k;
    vector<int> A(n);
    for (auto& x : A) cin >> x;
    sort(A.begin(), A.end());
    vector<pair<int, int>> a = {{A[0], 1}};
    for (int i = 1; i < n; ++i) {
        if (A[i] == A[i - 1]) a.back().second++;
        else a.emplace_back(A[i], 1);
    }

    while (a.size() > 0) {
        n = a.size();
        if (a[n - 1].second % 2 == 0) {
            cout << "YES\n";
            return;
        }
        if (n == 1) {
            cout << "NO\n";
            return;
        }
        if (a[n - 1].first - a[n - 2].first <= k) {
            cout << "YES\n";
            return;
        }
        a.pop_back();
    }
}

2236E - Friendly Gifts

Идея: arsen1y

Подсказка 1

Подсказка 2

Разбор

Решение (dvb1r)

#include <bits/stdc++.h>

using namespace std;
void solve();

int main() {
    int t = 1; cin >> t;
    while (t--) solve();
    return 0;
}

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x, --x;
    vector<vector<bool>> able(n, vector<bool>(n));
    for (int i = 0; i < n; ++i) {
        vector<int> us(n);
        int mn = a[i], mx = a[i];
        for (int j = i; j < n; ++j) {
            if (us[a[j]]) break;
            us[a[j]] = 1;
            mn = min(mn, a[j]), mx = max(mx, a[j]);
            if (mx - mn == j - i) able[mn][mx] = 1;
        }
    }
    
    for (int ans = n; ans > 0; --ans) {
        for (int i = 0; i + 2 * ans <= n; ++i) {
            if (able[i][i + ans - 1] && able[i + ans][i + 2 * ans - 1]) {
                cout << ans << '\n';
                return;
            }
        }
    }
    cout << "0\n";
}

2236F1 - Elections in Saransk (easy version)

Идея: eyfxrby

Подсказка 1

Подсказка 2

Разбор

Решение (eyfrxby)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#include <immintrin.h>
 
using namespace __gnu_pbds;
using namespace std;
 
#define eps 1e-7
#define MOD2 119 * (1ll << 23) + 1
#define int long long
#define mp make_pair
#define pll pair <long long, long long>
#define next return
#define skip continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define f first
#define max_of max_element
#define min_of min_element
#define s second
 
// const int MAX_MEM = 4e8;
// int mpos = 0;
// alignas(long long) char mem[MAX_MEM];
// inline void * operator new(size_t n) {
//     if (n & 7) n += 8 - (n & 7);
//     char *res = mem + mpos;
//     mpos += n;
//     return (void *)res;
// }
// void operator delete(void *) {}
 
int scan() {
    int x;
    cin >> x;
    return x;
}
 
string read() {
    string s;
    cin >> s;
    return s;
}
 
const int N = 1e6 + 5, MOD = 1e9 + 7;
int lp[N], a[N], x, n, v[101];
vector<int> pr, divs[N];
 
int bin_pow(int x, int n) {
    int res = 1;
    while (n) {
        if ((n & 1)) res = res * x % MOD;
        n >>= 1;
        x = x * x % MOD;
    }
    return res;
}
 
int solveF1_AUTHOR() {
    map <int, int> cnt;
    int cur_x;
    int mx = *max_element(a + 1, a + n + 1);
    set <int> setik;
    for (int i = 1; i <= n; i++) {
        int val = a[i];
        cur_x = val;
        while (cur_x > 1) {
            setik.insert(lp[cur_x]);
            cnt[lp[cur_x]]++;
            cur_x /= lp[cur_x];
        }
    }
    int ans = 1;
    for (auto prime: setik) {
        int sum = 1;
        //cout << prime << ' ' << cnt[prime] << '\n';
        ans = (ans * (cnt[prime] + 1)) % MOD;
    }
    return ans;
}
 
 
int32_t main() {
    lp[1] = 1;
    for (int i = 2; i < N; i++) {
        if (lp[i] == 0) {
            pr.push_back(i);
            lp[i] = i;
        }
        for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {
            lp[i * pr[j]] = pr[j];
        }
    }
    int t = scan();
    while (t--) {
        n = scan(); x = scan();
        for (int i = 1; i <= n; i++) a[i] = scan();
        cout << solveF1_AUTHOR() << '\n';
    }
}

2236F2 - Elections in Saransk (hard version)

Идея: eyfxrby

Подсказка 1

Подсказка 2

Подсказка 3

Разбор

Решение 1 (eyfrxby)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#include <immintrin.h>

using namespace __gnu_pbds;
using namespace std;

#define eps 1e-7
#define MOD2 119 * (1ll << 23) + 1
#define int long long
#define mp make_pair
#define pll pair <long long, long long>
#define next return
#define skip continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define f first
#define max_of max_element
#define min_of min_element
#define s second

int scan() {
    int x;
    cin >> x;
    return x;
}

string read() {
    string s;
    cin >> s;
    return s;
}

const int N = 1e6 + 2, MOD = 1e9 + 7;
int lp[N], a[N], x, n, v[N];
vector<int> pr, divs[N];

int MAX_V = -1E9;

int solve_for_prime(int vp) {
    int mx_pref = 0;
    int S = 0;
    for (int i = 1; i <= n; i++) S += v[i];
    S = min(S, 36ll);
    int dp[MAX_V + 1][MAX_V + S + 2];
    int old_pref_sum[MAX_V + 1][MAX_V + S + 2];
    int old_pref_sum2[MAX_V + 1][MAX_V + S + 2];
    memset(dp, 0, sizeof dp);
    memset(old_pref_sum, 0, sizeof old_pref_sum);
    memset(old_pref_sum2, 0, sizeof old_pref_sum2);
    int sum = 0;
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int sum_vp = 0; sum_vp <= S && i > 0; sum_vp++) {
            for (int new_max = 1; new_max <= min(sum_vp, v[i]); new_max++) {
                dp[new_max][sum_vp] += old_pref_sum2[new_max - 1][sum_vp - new_max];
                if (dp[new_max][sum_vp] >= MOD) dp[new_max][sum_vp] -= MOD;
            }
            for (int old_max = 0; old_max <= min(mx_pref, sum_vp); old_max++) {
                dp[old_max][sum_vp] += (old_pref_sum[old_max][sum_vp] + MOD - (sum_vp - min(old_max, v[i]) - 1 < 0 ? 0 :
                                                                              old_pref_sum[old_max][sum_vp - min(old_max, v[i]) - 1])) % MOD;
                //if (dp[old_max][sum_vp] >= MOD) dp[old_max][sum_vp] -= MOD;

            }
        }
        for (int old_max = 0; old_max <= MAX_V; old_max++) {
            for (int j = 0; j <= MAX_V + S; j++) {
                old_pref_sum[old_max][j] = 0;
                old_pref_sum[old_max][j] = (!j ? dp[old_max][j] : old_pref_sum[old_max][j - 1] + dp[old_max][j]);
                if (old_pref_sum[old_max][j] >= MOD) old_pref_sum[old_max][j] -= MOD;
            }
        }
        for (int j = 0; j <= MAX_V + S; j++) {
            for (int old_max = 0; old_max <= MAX_V; old_max++) {
                old_pref_sum2[old_max][j] = 0;
                old_pref_sum2[old_max][j] = (!old_max ? dp[old_max][j] : old_pref_sum2[old_max - 1][j] + dp[old_max][j]);
                if (old_pref_sum2[old_max][j] >= MOD) old_pref_sum2[old_max][j] -= MOD;
                if(i != n) dp[old_max][j] = 0;
            }
        }
        mx_pref = max(mx_pref, v[i]);
    }
    int ret = 0;
    for (int mx = 1; vp + mx <= S && mx <= MAX_V; mx++) {
        ret = (ret + dp[mx][vp + mx]);
        if (ret >= MOD) ret -= MOD;
    }
    return ret;
}

int solveF2_AUTHOR() {
    map<int, int> cnt_pr;
    int cur_x = x;
    while (cur_x > 1) {
        int next_div = lp[cur_x];
        cnt_pr[next_div]++;
        cur_x /= next_div;
    }
    int ans = 1;
    for (auto [prime, cnt]: cnt_pr) {
        MAX_V = -1e9;
        for (int i = 1; i <= n; i++) {
            cur_x = a[i];
            v[i] = 0;
            while (cur_x % prime == 0) {
                v[i]++;
                cur_x /= prime;
            }
            MAX_V = max(MAX_V, v[i]);
        }
        ans = (ans * solve_for_prime(cnt)) % MOD;
    }
    map <int, int> cnt;
    int mx = *max_element(a + 1, a + n + 1);
    set <int> setik;
    for (int i = 1; i <= n; i++) {
        int val = a[i];
        cur_x = val;
        while (cur_x > 1) {
            cnt[lp[cur_x]]++;
            setik.insert(lp[cur_x]);
            cur_x /= lp[cur_x];
        }
    }
    for (auto prime: setik) {
        //if (2 * prime > mx) break;
        int sum = 1;
        if (x % prime != 0) ans = (ans * (cnt[prime] + 1)) % MOD;
    }
    return ans;
}


int32_t main() {
    for (int i = 2; i < N; i++) {
        if (lp[i] == 0) {
            pr.push_back(i);
            lp[i] = i;
        }
        for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {
            lp[i * pr[j]] = pr[j];
        }
    }
    int t = scan();
    while (t--) {
        n = scan(), x = scan();
        for (int i = 1; i <= n; i++) a[i] = scan();
        cout << solveF2_AUTHOR() << '\n';
    }
}

Решение 2 (Treks)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>
#include <experimental/random>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using str = string;
const ll INF = 1e18, MOD = 1e9 + 7;
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;
#define int long long

void solve();

vector<int> P;
const int Mx = 1e4;

signed main() {
    vector<bool> us(Mx);
    for (int i = 2; i < Mx; ++i) {
        if (!us[i]) {
            P.push_back(i);
            for (int j = i * i; j < Mx; j += i) {
                us[j] = true;
            }
        }
    }
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll q = 1;
    cin >> q;
    while (q--) {
        solve();
        cout << "\n";
    }
}

void solve() {
    int n, x;
    cin >> n >> x;
    map<int, int> cnt;
    for (auto w: P) {
        if (w * w > x) {
            break;
        }
        while (x % w == 0) {
            x /= w;
            cnt[w]++;
        }
    }
    if (x > 1) {
        cnt[x]++;
    }
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    map<int, vector<int>> w1;
    for (int i = 0; i < n; ++i) {
        for (auto w: P) {
            if (w * w > a[i]) {
                break;
            }
            int sum = 0;
            while (a[i] % w == 0) {
                a[i] /= w;
                sum++;
            }
            if (sum > 0) {
                w1[w].push_back(sum);
            }
        }
        if (a[i] > 1) {
            w1[a[i]].push_back(1);
        }
    }
    int Ans = 1;
    for (auto [id, e]: w1) {
        int mx = 0;
        for (auto s: e) {
            mx = max(mx, s);
        }
        vector<vector<int>> dp(cnt[id] + 1, vector<int>(mx + 1));
        dp[0][0] = 1;
        for (auto w: e) {
            vector<vector<int>> dp1(cnt[id] + 1, vector<int>(mx + 1));
            for (int i = 0; i <= w; ++i) {
                for (int j = 0; j <= cnt[id]; ++j) {
                    for (int k = 0; k <= mx; ++k) {
                        if (j + min(i, k) <= cnt[id]) {
                            dp1[j + min(i, k)][max(i, k)] += dp[j][k];
                            dp1[j + min(i, k)][max(i, k)] %= MOD;
                        }
                    }
                }
            }
            swap(dp, dp1);
        }
        int s = 0;
        for (int i = 0; i <= mx; ++i) {
            s += dp[cnt[id]][i];
        }
        s %= MOD;
        Ans *= s;
        Ans %= MOD;
        cnt[id] = 0;
    }
    for (auto s: cnt) {
        if (s.second > 0) {
            Ans = 0;
        }
    }
    cout << Ans;
}

2236G - Criterion in Burlandia

Идея: dvb1r

Подсказка 1

Подсказка 2

Подсказка 3

Подсказка 4

Разбор

Решение 1 (dvb1r)

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
void solve();
 
int main() {
    int t = 1;
    cin >> t;
    while (t --> 0) solve();
    return 0;
}
 
struct Graph {
    vector<int> tin, tout, d;
    vector<vector<pair<int, ll>>> up;
 
    int timer;
 
    void dfs(int v, const vector<vector<int>>& g, const vector<int>& arr, int p = -1) {
        tin[v] = timer++;
        up[0][v] = {p, arr[v]};
        for (int l = 1; l < 20; ++l) {
            if (up[l - 1][v].first == -1) {
                up[l][v] = {-1, 0};
                continue;
            }
            up[l][v].first = up[l - 1][up[l - 1][v].first].first;
            up[l][v].second = up[l - 1][up[l - 1][v].first].second + up[l - 1][v].second;
        }
        for (int u : g[v]) {
            if (u == p) continue;
            d[u] = d[v] + 1;
            dfs(u, g, arr, v);
        }
        tout[v] = timer;
    }
 
    Graph(const vector<vector<int>>& g, const vector<int>& a) : tin(g.size()), tout(g.size()), d(g.size()), up(20, vector<pair<int, ll>>(g.size())) {
        timer = 0;
        dfs(0, g, a);
    }
 
    bool anc(int p, int v) {
        return tin[p] <= tin[v] && tout[p] >= tout[v];
    }
 
    int getLenVertical(int u, int v) {
        if (!anc(u, v)) swap(u, v);
        assert(anc(u, v));
        return d[v] - d[u] - 1;
    }
 
    pair<int, ll> LA(int v, int k) {
        if (k <= 0) return {v, 0};
        ll sum = 0;
        for (int i = 0; i < 20; ++i) {
            if (k >> i & 1) sum += up[i][v].second, v = up[i][v].first;
        }
        return {v, sum};
    }
 
    int LCA(int u, int v) {
        if (anc(u, v)) return u;
        for (int l = 19; l >= 0; --l) {
            if (up[l][u].first == -1 || anc(up[l][u].first, v)) continue;
            u = up[l][u].first;
        }
        return up[0][u].first;
    }
 
    bool lower(int a, int b) {
        return tin[a] < tin[b];
    }
};
 
ll sum(int r) { return r * 1ll * (r + 1) / 2; }
 
ll sumSeg(int l, int r) {
    return sum(r) - sum(l - 1);
}
 
void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<int> parent(n), d(n);
    auto dfs = [&](auto& self, int v, int p = -1) -> void {
        parent[v] = p;
        for (int u : g[v]) {
            if (u == p) continue;
            d[u] = d[v] + 1;
            self(self, u, v);
        }
    };
    dfs(dfs, 0);
 
    vector<int> compressed_parent = parent;
    vector<vector<int>> cG(n);
    for (int v = 0; v < n; ++v) {
        vector<int> path;
        while (compressed_parent[v] > 0 && a[compressed_parent[v]] == 0) {
            path.emplace_back(compressed_parent[v]);
            compressed_parent[v] = compressed_parent[compressed_parent[v]];
        }
        for (auto& x : path) compressed_parent[x] = compressed_parent[v];
        if (a[v] == 0 || !v) continue;
        cG[compressed_parent[v]].emplace_back(v);
    }
 
    vector<int> next_collision(n), sum_collision(n);
    for (int v = 0; v < n; ++v) {
        if (!a[v]) continue;
        next_collision[v] = v;
        int xr = a[v], sm = a[v];
        while (xr == sm && next_collision[v] > -1) {
            next_collision[v] = compressed_parent[next_collision[v]];
            if (next_collision[v] == -1) break;
            xr ^= a[next_collision[v]];
            sm += a[next_collision[v]];
        }
    }
 
    for (int v = 0; v < n; ++v) {
        if (!a[v]) {
            if (!v) next_collision[v] = -1;
            else next_collision[v] = next_collision[compressed_parent[v]];
        }
        sum_collision[v] = d[v];
        if (next_collision[v] > -1) sum_collision[v] -= d[next_collision[v]];
        else sum_collision[v]++;
    }
 
    Graph def(g, sum_collision);
    Graph compressed(cG, sum_collision);
 
    while (q--) {
        int u, v; cin >> u >> v;
        --u, --v;
        if (def.lower(v, u)) swap(u, v);
        int z = def.LCA(u, v);
 
        int cv = (a[v] || !v ? v : compressed_parent[v]), cu = (a[u] || !u ? u : compressed_parent[u]), cz = (a[z] || !z ? z : compressed_parent[z]);
 
        ll ans = 0;
 
        vector<int> L, R, Lspaces = {0}, Rspaces = {0};
 
        if (compressed.d[cv] > compressed.d[cz] + 23) {
            int unt = compressed.LA(cv, compressed.d[cv] - (compressed.d[cz] + 23)).first;
            auto [to, sm] = def.LA(v, d[v] - d[unt]);
            ans += sm, v = to;
        }
 
        if (compressed.d[cu] > compressed.d[cz] + 23) {
            int unt = compressed.LA(cu, compressed.d[cu] - (compressed.d[cz] + 23)).first;
            auto [to, sm] = def.LA(u, d[u] - d[unt]);
            ans += sm, u = to;
        }
 
        while (u != z) {
            int to = compressed_parent[u];
            if (def.anc(to, z)) to = z;
            L.emplace_back(u);
            Lspaces.emplace_back(def.getLenVertical(u, to));
            u = to;
        }
        while (v != z) {
            int to = compressed_parent[v];
            if (def.anc(to, z)) to = z;
            R.emplace_back(v);
            Rspaces.emplace_back(def.getLenVertical(v, to));
            v = to;
        }
        L.emplace_back(z);
        std::reverse(R.begin(), R.end());
        std::reverse(Rspaces.begin(), Rspaces.end());
        for (auto& x : R) L.emplace_back(x);
        for (auto& x : Rspaces) Lspaces.emplace_back(x);
        int j = 0, xr = 0, sum = 0;
        ll cnt = 0;
        for (int i = 0; i < L.size(); ++i) {
            while (j < L.size() && xr == sum) {
                xr ^= a[L[j]], sum += a[L[j]];
                cnt += Lspaces[j] + 1;
                j++;
            }
            if (xr != sum) cnt--;
            ans += sumSeg(cnt - Lspaces[i], cnt);
            if (xr != sum) cnt++;
            xr ^= a[L[i]], sum -= a[L[i]];
            cnt -= Lspaces[i] + 1;
        }
        cout << ans << '\n';
    }
}

Решение 2 (Treks)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>
#include <experimental/random>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using str = string;
const ll INF = 1e18, MOD = 1e9 + 7;
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;
#define int long long

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll q = 1;
    cin >> q;
    while (q--) {
        solve();
        //cout << "\n";
    }
}

vector<vector<int>> g;
vector<int> a;
int h;
vector<bool> us;
int cnt1;
vector<int> T;

void dfs1(int v, int pr) {
    T.push_back(v);
    cnt1++;
    for (auto to: g[v]) {
        if (to != pr && !us[to]) {
            dfs1(to, v);
        }
    }
}

int dfs(int v, int pr) {
    bool p = true;
    int cnt = 1;
    for (auto to: g[v]) {
        if (to != pr && !us[to]) {
            auto u = dfs(to, v);
            if (u > cnt1 / 2) {
                p = false;
            }
            cnt += u;
        }
    }
    if (p && (cnt1 &mdash; cnt) <= cnt1 / 2) {
        h = v;
    }
    return cnt;
}

int E = 0;

vector<int> ans;
vector<vector<int>> mn;
vector<int> col;
vector<int> sz;
vector<int> W;

void dfs(int v, int pr, vector<int> s, int an, int o, int mx) {
    sz[v] = o;
    col[v] = E;
    W[v] = W[pr];
    for (int i = 0; i < 20; ++i) {  
        mn[v][i] = mn[pr][i];
    }
    for (int i = 0; i < 20; ++i) {
        if ((a[v] >> i) & 1) {
            if (mn[v][i] != INF) {
                W[v] = min(W[v], o);
            }
            mn[v][i] = min(mn[v][i], o);
            mx = max(mx, s[i]);
            s[i] = o;
        }
    }
    an += o &mdash; mx;
    ans[v] = an;
    for (auto to: g[v]) {
        if (to != pr && !us[to]) {
            dfs(to, v, s, an, o + 1, mx);
        }
    }
}

vector<vector<pair<int, int>>> que;
vector<int> ANS;

void rec(int v) {
    T.clear();
    cnt1 = 0;
    dfs1(v, -1);
    dfs(v, -1);
    v = h;
    us[v] = true;
    mn[v] = vector<int>(20, INF);
    int S = E;
    W[v] = INF;
    for (auto to: g[v]) {
        if (!us[to]) {
            E++;
            vector<int> s(20, 0);
            dfs(to, v, s, 0, 1, 0);
        }
    }
    ans[v] = 0;
    ++E;
    col[v] = E;
    for (auto x: T) {
        for (auto [y, id]: que[x]) {
            if (col[x] != col[y] && col[x] > S && col[y] > S) {
                ANS[id] = ans[x] + ans[y];
                if (x == v) {
                    int MN = min(W[y], sz[y] + 1);
                    for (int i = 0; i < 20; ++i) {
                        if ((a[v] >> i) & 1) {
                            MN = min(MN, mn[y][i]);
                        }
                    }
                    ANS[id] += MN;
                } else if (y == v) {
                    int MN = min(W[x], sz[x] + 1);
                    for (int i = 0; i < 20; ++i) {
                        if ((a[v] >> i) & 1) {
                            MN = min(MN, mn[x][i]);
                        }
                    }
                    ANS[id] += MN;
                } else {
                    vector<pair<int, int>> upd;
                    for (int i = 0; i < 20; ++i) {
                        if (mn[x][i] != INF) {
                            upd.push_back({mn[x][i], i});
                        }
                    }
                    int e = min(W[y], sz[y] + 1);
                    for (int i = 0; i < 20; ++i) {
                        if ((a[v] >> i) & 1) {
                            e = min(e, mn[y][i]);
                        }
                    }
                    sort(upd.begin(), upd.end());
                    int p = 0;
                    bool flag = true;
                    for (int i = 0; i < upd.size(); ++i) {
                        if (upd[i].first >= W[x]) {
                            ANS[id] += (W[x] &mdash; p) * e;
                            flag = false;
                            break;
                        }
                        ANS[id] += (upd[i].first &mdash; p) * e;
                        if ((a[v] >> upd[i].second) & 1) {
                            flag = false;
                            break;
                        }
                        e = min(e, mn[y][upd[i].second]);
                        p = upd[i].first;
                    }
                    if (flag) {
                        ANS[id] += (min(W[x], sz[x] + 1) &mdash; p) * e;
                    }
                }
            }
        }
    }
    for (int i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (!us[to]) {
            rec(to);
        }
    }
}


void solve() {
    int n, q;
    cin >> n >> q;
    sz.clear();
    W.clear();
    W.resize(n);
    sz.resize(n);
    ans.clear();
    ANS.clear();
    ANS.resize(q, -1);
    mn.clear();
    ans.resize(n);
    mn.resize(n, vector<int>(20));
    a.clear();
    us.clear();
    us.resize(n);
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    g.clear();
    col.clear();
    col.resize(n);
    que.clear();
    que.resize(n);
    g.resize(n);
    for (int i = 0; i < n &mdash; 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        que[x].push_back({y, i});
    }
    rec(0);
    for (int i = 0; i < q; ++i) {
        if (ANS[i] == -1) {
            exit(-1);
        }
        cout << ANS[i] << "\n";
    }
}

n,k=map(int,input().split()) arr=list(map(int,input().split())) arr.sort() quantity=1 value=arr[n-1] for i in range(n-2,-1,-1): if arr[i]==value: quantity+=1 else: if not quantity%2 or value-arr[i]<=k: return "YES" else: value=arr[i] quantity=1 if quantity%2: return "NO" else: return "YES"

// https://codeforces.me/problemset/problem/2236/D // priyathama #include<bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--){ int n,k; cin >> n >> k; vector<int> a(n); map<int,int> mp; vector<int> stones; for(int i=0;i<n;i++){ cin >> a[i]; mp[a[i]]++; } for(auto &val:mp){ stones.push_back(val.first); } /* My thought process During Contest And where i Complicated it My thoughts given range and we should find valid so it is segementree we can also use dq Mistake Once traversed Forward Mistake Two A E D Traversing BackWard is Correct */ n=stones.size(); vector<int> dp(n); // dp[i] = 0 or 1 // if dp[i] == 0 that says if we start by removing ith index stone we will loose bool found=false; // this dq stores the indx of values <=x+k and it is a winning pos // deque<int> dq; int latest=-1; for(int i=n-1;i>=0;i--){ // while(dq.size() && stones[dq.front()]>stones[i]+k){ // dq.pop_front(); // } // it is better to store the index which is the most latest // other wise it tles as k grow and deque grows // so this is my mistake // while() if(i+1<n){ if(stones[i+1]-stones[i]>k){ // this says if we pick ith stone // then the other person cant pick then we win if(mp[stones[i]]%2){ latest=i; dp[i]=1; } } }else{ if(mp[stones[i]]%2){ latest=i; dp[i]=1; } } // other case if we remove this and the latest is <=x+k and that is if(latest!=-1){ if(stones[latest]>stones[i]+k){ // we remove this and the opponent need any winning index but it is not there so we win if(mp[stones[i]]%2) dp[i]=1; } } } for(int i=0;i<n;i++){ // cout << dp[i] << ' '; if(dp[i]==0){ found=true; } } if(found){ cout << "YES" ; }else{ cout << "NO" ; } cout << '\n'; } }

n,k=list(map(int,input().split())) arr=list(map(int,input().split())) arr.sort() quantity=1 value=arr[n-1] for i in range(n-2,-1,-1): if arr[i]==value: quantity+=1 else: if not quantity%2 or value-arr[i]<=k: return "YES" else: value=arr[i] quantity=1 if quantity%2: return "NO" else: return "YES"

Комментарии (56)

Написать комментарий?

dvb1r

5 месяцев назад, скрыть # |

Автокомментарий: текст был обновлен пользователем dvb1r (предыдущая версия, новая версия, сравнить).

→ Ответить

Auto comment: topic has been updated by dvb1r (previous revision, new revision, compare).

Ledbes

Немного запоздали с разбором..

5 месяцев назад, скрыть # ^ |

+13

Да, приносим свои извинения. Частично это связано с тем, что полигону было плоховато

furt1ve

+23

я бы не стерпел

GomerDoGo

G is beautiful

ekatva_5

Don't take this the wrong way, but this is the first time I saw you saying something nice

something nice

Hyder1102

What is the solution 2 for F2...?

← Rev. 2 →

What's the solution2 for F2?

eyfxrby

wdym?

this is a solution with a similar idea from our tester, only the logic of others works differently

dp logic, sorry

gevak

In F2 I tried to build up a DP solution, but all attempts ended up with too big complexity. I was exciting to see the tutorial. However, complexity in tutorial is:

O(A⋅log(ai)2⋅n)

I.e. 7 * 18 * 18 * 500'000 = 1'134'000'000. Looks too much, isn't it? I wish a constraint for n could be 100'000 instead of 500'000. With 500'000 the main skill to solve this problem is bravery :)

where did you get the number 2 in this expression? and n <= 100000

Oh, Im sorry. I understood what the 2 is)

Ah, I misread the statement. Saw 500'000 twice and missed that n is <= 100'000. Thanks.

aryanc403

My video and text editorial for all problems is available here https://codeforces.me/blog/entry/154479

Pacific.exe

Nice editorial! For problem D, I also found a great alternative solution in Python that achieves $$$O(N \log N)$$$ Time but optimizes the auxiliary space to $$$O(1)$$$ by processing the sorted array in a single reverse pass, avoiding the extra memory of a pair vector.

Here is the breakdown for anyone interested:

Core Idea:

Instead of compressing the array beforehand, we can sort it and iterate backward (from the largest element to the smallest). We maintain the frequency (quantity) of the current maximum value on the fly.

As we slide to the left:

If the current maximum's count is even, Arseniy can pick it, and Egor wins by parity.

If the count is odd, we check if we can bridge it with the next distinct smaller element. If the gap between them is <= k, Arseniy can pick that smaller element, forcing Egor to clear the maximums and win.

If the gap is > k, this maximum block becomes a "dead end". Since it's odd and cannot be bridged, it's a losing state for Egor. We mentally discard it, reset our frequency counter, and treat the next distinct element as our new maximum.

CODE IN PYTHON : ~~~~~ import sys input=sys.stdin.readline def solve():

t=int(input())

for _ in range(t):

print(solve())

~~~~~

dserrrrr

f2 is really nice implementation wise, tutorials for both f1 and f2 are great aswell, i just wish f2 would also include the proof for max(...)+v_pr(x)=summ(...).

Look at number as a product of it's prime factors. E.g. 12 = 2 * 2 * 3. Concentrate on a single prime, e.g. on 2. So, for each number we should only know how many 2's it contains.

LCM of several numbers will contain the amount of 2's equals to the biggest amount of 2's among these numbers. E.g. LCM(4, 8, 16, 2) = 16, here 16 = 2 * 2 * 2 * 2, i.e. contains 4 2's.

The product of numbers contains the amount of 2's equal to the sum of amounts for each number. E.g. 4 * 8 * 16 * 2 = 2 ^ 10, i.e. 2 + 3 + 4 + 1 = 10.

We must conform x * LCM(...) = product(...)

let v(y) = amount of 2's in y. Thus we must conform v(x) + v(LCM(...)) = v(product(...)) As shown above, v(LCM(...)) = max amount of 2's and v(product(...)) = sum of amount of 2's.

marcus06

i think it is trivial

tanyachutani

I am stuck as a newbie since long, please guide me on how can I improve ?

sveerv

Bro i saw your profile i am also stuck on newbie. But still i think i have some points on which you can improve if you want.

you must do problem till at least 1200 rated you are only trying 800 ones you must increase your difficulty.
you can also select div2 , div3 , edu. , and div1 + div2 in contest filter tab and try to do till B in (div2, edu.,div1 + div2) and till C in div3 in past contest. it will help to improve i think. 3.Once you get familiar you can increase difficulty and/or number of question in past contest.

mjm_hu

4 месяца назад, скрыть # ^ |

thanks bro , it is really a nice advice for me (crying emoji)

dirty_fingers

First, stop stressing about rating.

Borachii

hey bro , I am also new to codeforces , if u wanna pratice together we can ? I mean like we can share resources , help with problem approcah , cause i need some firend online or offline doest matter who can pratice with me on codeforces .

vasuganesha1

In my opinion problem F2 constraint should be lower it causes confusion whether the given solution will pass or not

jpm

Its so easy to overthink on E and go down a rabit hole which actually works.

My solution used DSU to find the good segments and a DP with some weird ass states. link here: https://codeforces.me/contest/2236/submission/378557786

molybdenum

Can you explain your intuition and approach?

Sharp-Ghost

Am I the only one who used a dp and fenwick tree on D?

Here is my submission 378392641

Sai_nikhilchakravarthi

Mee i used Dp with Deque But it Gave TLE after Pretests

geminos

In C, you can also simply put all variations of a through division in vector A, and all variations of b through division in vector B, that is: A = {a, a / x, a / x^2, a / x^3, ...} and B = {b, b / x, b / x^2, b / x^3, ...}. After that, brute force both vectors and find the pair which leads to optimal number of steps: i + j + diff(A[i], B[j]). Since a, b <= 1,000,000,000 and x >= 2, it is guaranteed that |A|, |B| <= 31.

unorz

did the same thing asw, but brute force is nou

jagorrim

F2 is great

In the editorial and solution of G, I couldn't get the "compressed tree" part. I think the Hint4, which states that, "Reduce the problem to a path of length at most 2∗log(A)" is signalling the same thing. Can someone please explain this part.

dooglius

The idea is that the compressed tree consists only of the vertices with nonzero masks (and the root). You can do this via DFS by keeping track of the lowest nonzero ancestor: the edges of the compressed tree are edges from each nonzero node (in the full tree) to its lowest nonzero ancestor. The level ancestor queries happen in the compressed tree.

Problem 2236D: Python O(N \log N)$$$ Time / O(1)$$$ Auxiliary Space Single-Pass Solution

This approach avoids allocating additional memory for a pair vector, which keeps the auxiliary space complexity at O(1). For those who simply want to look at the code and analyze it, I recommend skipping the explanation of the code’s logic, as it is intended for those who want to dissect and understand it. I do, however, encourage you to read it so that you can understand this logic.

EXPLANATION:

Hey coders! For those of you who are stuck, I’ve got a great alternative solution based on the same mathematical logic of parity. First, let’s take our array and sort it — complexity O(N \log N). You might ask, why? Because, remember, several numbers repeat themselves. The idea is to group them so we can count them and avoid misreporting the data, since the number of times a number repeats is very important. To make this as educational as possible, let’s use this example, which we’ll work through step by step:

N ->13 K -> 2

array -> 2223344477777

Let’s start by explaining the logic. Imagine if we only have one number that repeats an even number of times, e.g., 999999. If our famous Arseniy plays here, IT IS 100 PERCENT GUARANTEED that Egor will win no matter what position Dabir plays. Why? Let’s denote D as Dabir and E as Egor. Let’s show how the game plays out:

999D99 -> E99D99 -> ED9D99 -> EDED99 -> EDED9D -> EDDED“E”D BOOM Egor wins! Not surprising at all since the number is even!

Let’s take the case where the number is odd: 999.

D99 -> D9E -> D“D”E BOOM Dabir wins. The rule is that if it’s an odd number, then he can’t win.

But you’d say LOLLLL Pacific.exe thinks it’s an application in this case 223333 with K=5. If D plays D23333 and E plays DE3333, he still hasn’t won because he can still play 3 (K=5, so (3-2) < 5).

Guys, you’re right — you’ve won — but remember, we’ve sorted the array. This means that the maximum value in the array is guaranteed not to overlap with any other value. For example:

1122777 with K=2.

Are you telling me that if D takes the element 7, it can then take 2? REMEMBER, YOUNG CODERS: you can only take a number y such that y — x (our previous element, which here is 7 and we’ll denote as x) must be in the interval from 0 to K inclusive, i.e., 0 <= y — x <= K.

So we’ll focus on the maximums; let’s take this case: 1334444 with K =any value. If D plays a 4, then they’re forced to play only 4, and boom — the parity logic breaks down, guaranteeing that E wins. The problem is that if this number is odd, then he cannot play 4 because it is guaranteed to be a loss, as in the example 133444.

The idea is that we can still win by playing the term immediately before it; for example, if we play 13[3444] ->, this forms an even number, so he can win because D plays 3, and so on, and E wins. The only condition is that the previous term must be played first, because if the larger one is played, then this one can no longer be played, so we lose. So here it must satisfy 0 <= 4 — 3 <= K; in this case, it is indeed possible because K = 5.

So here it must satisfy 0 <= 4 — 3 <= K; in this case, that’s perfectly possible because $K = 5. However, if $4 — 3 > K, then it doesn’t work, and so choosing 4 would result in a dead block because it can’t be combined with another. We therefore remove this dead block and reapply (mentally) this logic by taking the other maximum, that is, the last element just before this maximum.

Let’s go back to the example mentioned at the very beginning:

Let’s start the loop from the end, that is, from the last 7, down to the very first element, which is 2. If we go down from there to the first 4 from the end, we will have had 5 seven in total. If D plays here, it is guaranteed that E loses because it is odd. Is it possible to create an even block with the element before it? That is, 2223344[4,7,7,7,7,7]? No, because 7-4 > 2, so it’s impossible to play in the 7 zone — it’s fatal — so we mentally remove it.

And let’s apply the same logic to 4: we count the number of 4s — boom, it’s odd because there are 3 fours. If it had been even, we could simply win by playing 4. The question is: is it possible to combine it with the element before it to form an even zone that’s also valid? Let’s test 2223[3444] (we’ve MENTALLY removed the other part) — it’s indeed even, but is it valid? Let’s check: 0 < 4 — 3 < K(2) — well, so it’s valid, so here E can totally win.

Do you see the power of parity, fellow coders?

THE CODE IN PYTHON : ~~~~~ import sys

def calcul(): n,k=list(map(int,input().split())) arr=list(map(int,input().split())) arr.sort() quantity=1 value=arr[n-1] for i in range(n-2,-1,-1): if arr[i]==value: quantity+=1 else: if not quantity%2 or value-arr[i]<=k: return "YES"

else:
            value=arr[i]
            quantity=1
if quantity%2:
    return "NO"
else:
    return "YES"

input=sys.stdin.readline

t=int(input()) for _ in range(t): print(calcul()) ~~~~~

Here is the code in a better format : ~~~~~

import sys

def calcul():

print(calcul())

NewbieXCX

I think D is interesting because it is like DP on DAG. This is a good contest!

depoo.

I implemented the G just using LCA

"Aure Farming!!!""

I implemented G just using lca not like all weak grandmasters who just implemented it using HLD

"Aura Farming!!!!"

VGCos

For problem D, why does my submission TLE on test 12? This test came from a successful hack and I even tried running the test case on vscode and my code passed it nearly instantly.

Here is my submission 378441055

Here is the submission where the hack came from 378425504

tridev06052009

solution for f2 using Polynomial Generating Function. TC= O (36^2 log N)
Link =(https://codeforces.me/contest/2236/submission/379129951)

parthkoul_

can someone please share some problems based on invariance — like problem B.

ryuzen

I tried a lot to find bug in the code but, could not find any. However just declaring vis1 outside the loops gives the correct answer. Could you please review it once.

Correct Code

Link: 379312920

// कर्मण्येवाधिकारस्ते मा फलेषु कदाचन ।
// मा कर्मफलहेतुर्भूर्मा ते सङ्गोऽस्त्वकर्मणि ॥
// नीरसतां परिश्रमं च आलिंगयन्तु, केवलं अदम्य-अनुशासनेन 
// एव निपुणता सच्चिदानन्दस्य ब्रह्माण्डस्य तालान् उद्घाटयति। ॥
#include <bits/stdc++.h>

using namespace std;

#define int long long

#ifdef LOCAL
#include "pr.h"
#else
#define pr(...) {}
#define debarr(a, n) {}
#define debmat(mat, row, col) {}
#endif

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

  vector<int> a(n);

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

  int half = (n + 1) / 2 + 5;
  vector vis(n + 5, vector<bool> (half)); // {startValue, len}
  vector<int> vis1(n + 5, -1);
  int ans = 0;

  for (int i = 0; i < n; i++) {
    int l = a[i], r = a[i];
    for (int j = i; j < n; j++) {
      if (vis1[a[j]] == i) break;
      vis1[a[j]] = i;
      l = min(l, a[j]), r = max(r, a[j]);
      int len = r - l + 1;
      if (r - l == j - i) {
        vis[l][len] = true;
        if ((l + len <= n && vis[l +  len][len]) || (l - len >= 0 && vis[l -  len][len])) ans = max(ans, len);
      }
      if (len >= half) break;
    }
  }

  cout << ans << "\n";

}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int tt = 1;
  cin >> tt;

  for (int t_ = 1; t_ <= tt; t_++) {
    solve();
  }

  return 0;
}

Code with Bug

Link: 379312870

// कर्मण्येवाधिकारस्ते मा फलेषु कदाचन ।
// मा कर्मफलहेतुर्भूर्मा ते सङ्गोऽस्त्वकर्मणि ॥
// नीरसतां परिश्रमं च आलिंगयन्तु, केवलं अदम्य-अनुशासनेन 
// एव निपुणता सच्चिदानन्दस्य ब्रह्माण्डस्य तालान् उद्घाटयति। ॥
#include <bits/stdc++.h>

using namespace std;

#define int long long

#ifdef LOCAL
#include "pr.h"
#else
#define pr(...) {}
#define debarr(a, n) {}
#define debmat(mat, row, col) {}
#endif

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

  vector<int> a(n);

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

  int half = (n + 1) / 2 + 5;
  vector vis(n + 5, vector<bool> (half)); // {startValue, len}
  int ans = 0;

  for (int i = 0; i < n; i++) {
    vector<bool> vis1(n + 5);
    int l = a[i], r = a[i];
    for (int j = i; j < n; j++) {
      if (vis1[a[j]]) break;
      vis1[a[j]] = true;
      l = min(l, a[j]), r = max(r, a[j]);
      int len = r - l + 1;
      if (r - l == j - i) {
        vis[l][len] = true;
        if ((l + len <= n && vis[l +  len][len]) || (l - len >= 0 && vis[l -  len][len])) ans = max(ans, len);
      }
      if (len >= half) break;
    }
  }

  cout << ans << "\n";

}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int tt = 1;
  cin >> tt;

  for (int t_ = 1; t_ <= tt; t_++) {
    solve();
  }

  return 0;
}