Hello 2025 Editorial

#	User	Rating
1	jiangly	3977
2	tourist	3815
3	jqdai0815	3682
4	ksun48	3614
5	orzdevinwang	3526
6	ecnerwala	3514
7	Benq	3483
8	hos.lyric	3381
9	gamegame	3374
10	heuristica	3358

#	User	Contrib.
1	cry	170
2	-is-this-fft-	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	157
6	Dominater069	156
7	adamant	154
8	luogu_official	152
8	awoo	152
10	TheScrasse	147

Thank you for participating! We hope you enjoyed our problems

2057A - MEX Table

Author and developer is dope

Solution

Implementation

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int n, m;
    std::cin >> n >> m;
    std::cout << std::max(n, m) + 1 << "\n";
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
}

2057B - Gorilla and the Exam

Author and developer is dope

Solution

Implementation

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    std::vector<int> cnt = {1};
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
            cnt.back()++;
        } else {
            cnt.emplace_back(1);
        }
    }
    std::sort(cnt.begin(), cnt.end());
    int m = cnt.size();
    for (int i = 0; i < m - 1; i++) {
        if (cnt[i] > k) {
            std::cout << m - i << "\n";
            return;
        }
        k -= cnt[i];
    }
    std::cout << 1 << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;

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

2057C - Trip to the Olympiad

Author is I_love_kirill22 and developer is dope

Solution

Implementation

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int l, r;
    std::cin >> l >> r;
    int k = 31 - __builtin_clz(l ^ r);
    int a = l | ((1 << k) - 1), b = a + 1, c = (a == l ? r : l);
    std::cout << a << " " << b << " " << c << "\n";
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

2057D - Gifts Order

Author and developer is dope, also thanks mupp and KoT_OsKaR for discussing this problem with me

Solution

Implementation

#include <bits/stdc++.h>

using i64 = long long;

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;

    SegmentTree() : n(0) {}

    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }

    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }

    void init(int n_, Info v_ = Info()) {
        init(std::vector<Info>(n_, v_));
    }

    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        int sz = (1 << (std::__lg(n - 1) + 1));
        info.assign(sz * 2, Info());
        std::function<void(int, int, int)> build = [&](int v, int l, int r) {
            if (l == r) {
                info[v] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(v + v, l, m);
            build(v + v + 1, m + 1, r);
            info[v] = info[v + v] + info[v + v + 1];
        };
        build(1, 0, n - 1);
    }

    Info rangeQuery(int v, int l, int r, int tl, int tr) {
        if (r < tl || l > tr) {
            return Info();
        }
        if (l >= tl && r <= tr) {
            return info[v];
        }
        int m = (l + r) / 2;
        return rangeQuery(v + v, l, m, tl, tr) + rangeQuery(v + v + 1, m + 1, r, tl, tr);
    }

    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n - 1, l, r);
    }

    void modify(int v, int l, int r, int i, const Info &x) {
        if (l == r) {
            info[v] = x;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) {
            modify(v + v, l, m, i, x);
        } else {
            modify(v + v + 1, m + 1, r, i, x);
        }
        info[v] = info[v + v] + info[v + v + 1];
    }

    void modify(int i, const Info &x) {
        modify(1, 0, n - 1, i, x);
    }

    Info query(int v, int l, int r, int i) {
        if (l == r) {
            return info[v];
        }
        int m = (l + r) / 2;
        if (i <= m) {
            return query(v + v, l, m, i);
        } else {
            return query(v + v + 1, m + 1, r, i);
        }
    }

    Info query(int i) {
        return query(1, 0, n - 1, i);
    }
};

const int INF = 1E9;

struct Info {
    int min1, min2, max1, max2, ans1, ans2;

    Info() : min1(INF), min2(INF), max1(-INF), max2(-INF), ans1(0), ans2(0) {}

    Info(std::pair<int, int> x) : min1(x.first), min2(x.second), max1(x.first), max2(x.second), ans1(0), ans2(0) {}
};

Info operator+(const Info &a, const Info &b) {
    Info res;
    res.min1 = std::min(a.min1, b.min1);
    res.min2 = std::min(a.min2, b.min2);
    res.max1 = std::max(a.max1, b.max1);
    res.max2 = std::max(a.max2, b.max2);
    res.ans1 = std::max({a.ans1, b.ans1, b.max1 - a.min1});
    res.ans2 = std::max({a.ans2, b.ans2, a.max2 - b.min2});
    return res;
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    std::vector<std::pair<int, int>> t(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        t[i] = {a[i] - i, a[i] + i - n + 1};
    }
    SegmentTree<Info> st(t);
    auto query = [&]() {
        return std::max(st.info[1].ans1, st.info[1].ans2);
    };
    std::cout << query() << "\n";
    for (int i = 0; i < q; i++) {
        int p, x;
        std::cin >> p >> x;
        p--;
        t[p] = {x - p, x + p - n + 1};
        st.modify(p, t[p]);
        std::cout << query() << "\n";
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

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

2057E1 - Another Exercise on Graphs (Easy Version)

Author is I_love_kirill22 and developer is dope

Solution

Implementation

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::array<int, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        int v, u, w;
        std::cin >> v >> u >> w;
        v--, u--;
        edges[i] = {v, u, w};
    }
    std::sort(edges.begin(), edges.end(), [&](const std::array<int, 3> &a, const std::array<int, 3> &b) {
        return a[2] < b[2];
    });
    constexpr int INF = 1e9;
    std::vector<int> value(m + 1);
    std::vector<std::vector<std::vector<int>>> dis(m + 1, std::vector<std::vector<int>>(n, std::vector<int>(n, INF)));
    for (int i = 0; i < n; i++) {
        dis[0][i][i] = 0;
    }
    for (auto edge : edges) {
        int v = edge[0], u = edge[1];
        dis[0][v][u] = dis[0][u][v] = 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[0][i][j] = std::min(dis[0][i][j], dis[0][i][k] + dis[0][k][j]);
            }
        }
    }
    int p = 1;
    for (auto edge : edges) {
        int v = edge[0], u = edge[1], w = edge[2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[p][i][j] = std::min({dis[p - 1][i][j], dis[p - 1][i][v] + dis[p - 1][u][j], dis[p - 1][i][u] + dis[p - 1][v][j]});
            }
        }
        value[p++] = w;
    }
    for (int i = 0; i < q; i++) {
        int v, u, k;
        std::cin >> v >> u >> k;
        v--, u--;
        int low = 0, high = m;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (dis[mid][v][u] < k) {
                high = mid;
            } else {
                low = mid;
            }
        }
        std::cout << value[high] << " \n"[i == q - 1];
    }
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

2057E2 - Another Exercise on Graphs (hard version)

Author is I_love_kirill22 and developer is dope

Solution

Implementation

#include <bits/stdc++.h>

using i64 = long long;

struct DSU {
    std::vector<int> p, sz, h;
    
    DSU(int n = 0) : p(n), sz(n, 1), h(n) { 
        std::iota(p.begin(), p.end(), 0); 
    }

    int leader(int x) {
        if (x == p[x]) {
            return x;
        }
        return leader(p[x]);
    }

    bool same(int x, int y) {
        return leader(x) == leader(y);
    }

    bool merge(int x, int y) {
        x = leader(x);
        y = leader(y);
        if (x == y) return false;
        if (h[x] < h[y]) {
            std::swap(x, y);
        }
        if (h[x] == h[y]) {
            ++h[x];
        }
        sz[x] += sz[y];
        p[y] = x;
        return true;
    }

    int size(int x) { 
        return sz[leader(x)]; 
    }
};

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::array<int, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        int v, u, w;
        std::cin >> v >> u >> w;
        v--, u--;
        edges[i] = {v, u, w};
    }
    std::sort(edges.begin(), edges.end(), [&](const std::array<int, 3> &a, const std::array<int, 3> &b) {
        return a[2] < b[2];
    });
    constexpr int INF = 1e9;
    std::vector<int> value(n);
    std::vector<std::vector<std::vector<int>>> dis(n, std::vector<std::vector<int>>(n, std::vector<int>(n, INF)));
    for (int i = 0; i < n; i++) {
        dis[0][i][i] = 0;
    }
    for (auto edge : edges) {
        int v = edge[0], u = edge[1];
        dis[0][v][u] = dis[0][u][v] = 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[0][i][j] = std::min(dis[0][i][j], dis[0][i][k] + dis[0][k][j]);
            }
        }
    }
    int p = 1;
    DSU dsu(n);
    for (auto edge : edges) {
        int v = edge[0], u = edge[1], w = edge[2];
        if (dsu.merge(v, u)) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dis[p][i][j] = std::min({dis[p - 1][i][j], dis[p - 1][i][v] + dis[p - 1][u][j], dis[p - 1][i][u] + dis[p - 1][v][j]});
                }
            }
            value[p++] = w;
        }
    }
    for (int i = 0; i < q; i++) {
        int v, u, k;
        std::cin >> v >> u >> k;
        v--, u--;
        int low = 0, high = n - 1;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (dis[mid][v][u] < k) {
                high = mid;
            } else {
                low = mid;
            }
        }
        std::cout << value[high] << " \n"[i == q - 1];
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;

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

2057F - Formation

Author is induk_v_tsiane and developer is dope

Solution

Implementation

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    constexpr int LG = 30;
    std::vector<std::array<i64, 4>> events;
    for (int i = 0; i < n; i++) {
        i64 pow = 1, sum = 0;
        i64 dop = 0;
        for (int j = 0; j < LG; j++) {
            if (i - j < 0) {
                break;
            }
            sum += a[i - j];
            i64 L = dop, R;
            if (i - j == 0) {
                R = 2E18;
            } else {
                i64 x = (pow * 4 - 2) * a[i - j - 1] - sum;
                R = x;
                dop = x;
            }
            pow *= 2;
            events.push_back({L, -1, j, sum});
            events.push_back({R, 1, j, sum});
        }
    }
    for (int i = 0; i < q; i++) {
        int x;
        std::cin >> x;
        events.push_back({x, 0, i, 0});
    }
    std::sort(events.begin(), events.end());
    std::vector<int> ans(q); 
    std::vector<std::multiset<i64>> st(LG);
    for (auto item : events) {
        int h = item[0];
        int o = item[1];
        if (o == -1) {
            int j = item[2];
            i64 sum = item[3];
            st[j].insert(sum);
        } else if (o == 1) {
            int j = item[2];
            i64 sum = item[3];
            st[j].erase(st[j].find(sum));
        } else {
            int i = item[2];
            int low = 0, high = 2E9 + 1;
            while (high - low > 1) {
                int mid = (0LL + low + high) / 2;
                int cur = mid;
                i64 pos = 0;
                bool ok = false;
                for (int cnt = 0; cnt < LG; cnt++) {
                    if (st[cnt].empty()) {
                        continue;
                    }
                    i64 neg = *st[cnt].rbegin();
                    pos += cur;
                    cur = (cur + 1) / 2;
                    if (pos - neg <= h) {
                        ok = true;
                        break;
                    }
                }
                if (ok) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            ans[i] = low;
        }
    }
    for (int i = 0; i < q; i++) {
        std::cout << ans[i] << " \n"[i == q - 1];
    }
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

Alternative solution

// Parallel binary search technique optimizes log^3 => log^2
// SegmentTree might be faster then std::multiset
// sl[i] should equals max(a) at the begining cause IDK how to explain but it's obviously important
 
#include <bits/stdc++.h>
#include <algorithm>
 
using namespace std;
using ll = long long;
 
constexpr int W = 31;
constexpr int C = 1'000'000'000;
 
struct Event {
    int x;
    int ind;
    ll s;
 
    bool operator<(const Event& rhs) const { return x < rhs.x; }
};
 
struct SegmentTree {
    int n;
    vector<ll> sgt;
 
    SegmentTree(int n) : n(n), sgt(2 * n, -1) {}
 
    void Change(int i, ll x) {
        for (sgt[i += n] = x; i != 1; i >>= 1) {
            sgt[i >> 1] = max(sgt[i], sgt[i ^ 1]);
        }
    }
 
    int GlobalMax() const { return sgt[1]; }
};
 
vector<int> solve(const vector<int>& a, const vector<int>& q) {
    const int n = a.size(), m = q.size();
 
    vector<ll> ps(n + 1);
    for (int i = 0; i < n; ++i)
        ps[i + 1] = ps[i] + a[i];
 
    vector<ll> min_x(n, 0);
    vector<vector<pair<int, ll>>> change_sum(W);
 
    vector<Event> events;
    events.reserve(2 * n);
    for (int j = 1; j <= W && j <= n; ++j) {
        events.clear();
 
        for (int i = j - 1; i < n; ++i) {
            min_x[i] = max(min_x[i], 1 + ((a[i - j + 1] - 1ll) << (j - 1)));
            ll max_x = i == j - 1 ? 2ll * C : ((ll)a[i - j] << j);
            max_x = min<ll>(max_x, a[i] + C);
 
            if (min_x[i] > max_x) {
                continue;
            }
            const ll xsum = ps[i + 1] - ps[i + 1 - j];
            events.push_back(Event{(int)min_x[i], i, xsum});
            events.push_back(Event{(int)max_x + 1, i, -1});
        }
        sort(events.begin(), events.end());
 
        SegmentTree sgt(n);
        const int k = events.size();
        ll was_max = -1;
 
        for (int i = 0; i < k;) {
            int s = i;
            while (i < k && events[i].x == events[s].x) {
                sgt.Change(events[i].ind, events[i].s);
                ++i;
            }
            ll cur_max = sgt.GlobalMax();
            if (cur_max != was_max) {
                change_sum[j - 1].emplace_back(events[s].x, cur_max);
                was_max = cur_max;
            }
        }
    }
 
    vector<int> sl(m, *max_element(a.begin(), a.end())), sr(m, 2 * C + 1);
 
    vector<int> ord_to_check(m);
    iota(ord_to_check.begin(), ord_to_check.end(), 0);
    for (int iter = 32; iter--;) {
        vector<int> sm(m);
        for (int i = 0; i < m; ++i) {
            sm[i] = sl[i] + (sr[i] - sl[i]) / 2;
        }
        sort(ord_to_check.begin(), ord_to_check.end(), [&](int lhs, int rhs) {
            return sm[lhs] < sm[rhs];
        });
 
        vector<int> ptr(W);
        vector<ll> actual_sum(W, -1);
        for (int i : ord_to_check) {
            const int x = sm[i];
 
 
            ll upper_sum = 0;
            bool nice = false;
            for (int w = 0; w < W; ++w) {
                int& j = ptr[w];
                while (j < change_sum[w].size() && change_sum[w][j].first <= x) {
                    actual_sum[w] = change_sum[w][j++].second;
                }
                upper_sum += 1 + ((x - 1) >> w);
                if (upper_sum - actual_sum[w] <= q[i]) {
                    nice = true;
                }
            }
 
            if (nice) {
                sl[i] = sm[i];
            } else {
                sr[i] = sm[i];
            }
        }
    }
 
    return sl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t = 1;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n), k(q);
        for (int& x : a)
            cin >> x;
        for (int& x : k)
            cin >> x;
 
        auto ans = solve(a, k);
        for (int x : ans)
            cout << x << ' ';
        cout << '\n';
    }
}

2057G - Secret Message

Author and developer is I_love_kirill22

Solution

Implementation

#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;

void solve() {
    int n, m; cin >> n >> m;
    vector<string> v(n);
    for (auto& w : v) cin >> w;

    auto col = [](int x, int y) {
        int c = (x+2*y)%5;
        if (c < 0) c += 5;
        return c;
    };
    auto cell = [&](int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= m) return false;
        return v[x][y] == '#';
    };

    array<vector<pi>, 5> colorings;
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
        if (!cell(i, j)) continue;
        colorings[col(i, j)].emplace_back(i, j);

        for (int di = -1; di <= 1; ++di)
        for (int dj = -1; dj <= 1; ++dj) {
            if (abs(di) + abs(dj) != 1) continue;
            if (!cell(i+di, j+dj)) {
                colorings[col(i+di, j+dj)].emplace_back(i, j);
            }
        }
    }

    auto coloring = colorings[0];
    for (const auto& w : colorings)
        if (w.size() < coloring.size()) coloring = w;
    for (auto [x, y] : coloring) v[x][y] = 'S';
    for (auto line : v) cout << line << '\n';
}

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

    int t; cin >> t;
    while (t--)
        solve();
}

2057H - Coffee Break

Author and developer is I_love_kirill22

Solution

Implementation

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using ll = long long;

vector<ll> a, lhs, rhs;
vector<int> st;

vector<ll> get_right_out(const vector<ll>& a, vector<ll>& res) {
    const int n = a.size();
    st.clear();
    res.assign(n+1, 0);

    for (int i = 0; i < n; ++i) {
        ll x = a[i] + res[i];
        st.push_back(i);

        while (x != 0) {
            if (st.empty()) {
                const int len = i + 1;
                const ll cnt = x / (len + 1);
                res[i+1] += cnt * len;
                x -= cnt * (len + 1);

                if (x != 0) {
                    res[i+1] += x;
                    st.push_back(x-1);
                    x = 0;
                }
            } else {
                const int j = st.back();
                if (x > i - j) {
                    res[i+1] += i - j;
                    st.pop_back();
                    x -= i - j + 1;
                } else {
                    res[i+1] += x;
                    st.back() += x;
                    x = 0;
                }
            }
        }
    }

    return res;
}

vector<ll> get_left_out(vector<ll>& a, vector<ll>& b) {
    reverse(a.begin(), a.end());
    get_right_out(a, b);
    reverse(b.begin(), b.end());
    reverse(a.begin(), a.end());
    return b;
}

void solve() {
    int n; cin >> n;
    
    a.resize(n);
    for (ll& x : a) cin >> x;

    get_right_out(a, lhs);
    get_left_out(a, rhs);

    ll ans = 0;
    for (int i = 0; i < n; ++i)
        cout << lhs[i] + a[i] + rhs[i+1] << ' ';
    cout << '\n';
}

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

    int t = 1;
    cin >> t;
    while (t--) solve();
}

#include<iostream> int main() { int l, r; std::cin >> l >> r; // l = 128, r = 132; for (int i = 30; i >= 0; i--) { if (!!(l & (1 << i)) != !!(r & (1 << i))) { std::cout << i << '\n'; return 0; } if (l & (1 << i)) return 0; } }

#include<iostream> int main() { int l, r; std::cin >> l >> r; // l = 128, r = 132; for (int i = 30; i >= 0; i--) { int res = (!!(l & (1 << i)) != !!(r & (1 << i))); if (res > 0) { std::cout << res << " res\n"; std::cout << i << "\n"; return 0; } if (l & (1 << i)) return 0; } return 0; }

for _ in range(int(input())): sz , k = map(int,input().split()) arr = list(map(int,input().split())) freq = dict() for a in arr: a = str(a) if (a not in freq): freq[a] = 1 else: freq[a] += 1 final = sorted(freq.values()) ans = len(final) for a in final: if (k-a >= 0): ans -= 1 k -= a else: break print(max(ans,1))

for _ in range(int(input())): sz , k = map(int,input().split()) arr = list(map(int,input().split())) freq = dict() for a in arr: if (a not in freq): freq[a] = 1 else: freq[a] += 1 final = sorted(freq.values()) ans = len(final) for a in final: if (k-a >= 0): ans -= 1 k -= a else: break print(max(ans,1))

Comments (164)

Write comment?

123gjweq2

2 days ago, # |

-80

first

C and D were cool imo

→ Reply

Zhangyl

+27

It looks like b has some typographical errors :)

2 days ago, # ^ |

-10

which is display as"Unable to parse markup [type=CF_MATHJAX]".Is it me?

anshul_57

me as well.

dope

-8

will be fixed soon

HarshitKumarGupta

47 hours ago, # ^ |

Please open up solution links too, currently trying to access the link throws "You are not allowed to view the requested page" error notification.

amirhanordobaev

thank you for opening the new year!

TheShiningSun

Also, we are unable to see the coded solutions.

djm03178

+15

Can anyone help me find out the cause of the difference of these submissions? 299626640 299629236

I'm pretty sure the codes are exactly the same, and on my local MSVC the outputs for the examples are also correct (same as C++23). I don't recognize any UB in my code, so I don't get why C++20 shows a wrong output while C++23 runs as my expectation.

LeoPro

46 hours ago, # ^ |

← Rev. 2 →

+40

Fascinating.

I was able to simplify this down to something like the following (run in customtest under G++20 13.2, 64 bit)

This outputs 7 when 128 and 132 are given as input, and quits quietly if the line // l = 128, r = 132 is uncommented. Haven't seen anything like this before. It seems I should recall something from the very beginning of my journey, where someone once mentioned to me that bitwise operations with signed integers can lead to UB. However, I couldn't find any information about this online.

It would be very interesting to hear from someone more experienced in C++ about this issue.

UPD: Looks like this is a compiler bug. I shared the problem in a local chat, and they showed me the site. The file about C++ 20, parts 7.6.7 and 7.6.11 seem to define correctly bitwise operations both for signed and unsigned integers .

45 hours ago, # ^ |

Wow, so I guess it's high time that I completely move on to C++23. Thank you for the analysis.

ibrm

31 hour(s) ago, # ^ |

I found out something interesting :D

Output on G++20 13.2, 64 bit:

0 res
7

Aspekt_

I put them in VS Code and no differences showed up on comparison. I am sure it has to related to the compiler difference. Because the same submission works in C++17 (299700872). Hope someone can actually answer why this is so.

UPD: Seems Leo has found out the reason for this behaviour.

ezluci

Compiling with #pragma GCC optimize("O0") seems to fix this bug

jakub.zip

I misread problem C and thought I had to maximize a ⊕ b ⊕ c. Anyone knows a solution to this problem instead of the original one?

Pramag_IIITD

idk i haven't tried yet can have edge cases: but my intution was: you can just convert the minimum to maximum to arrays of binary and rev it using tradition mod 2 method store it in separate arrays and reverse it where a has first 0 and b has first 1 is there start from there to make it in range convert all alternate signs of a and b to 0 and 1 and get it together and c can be anything in the range leaving a and b. All together i am saying where 0 of minimum and 1 of maximum in same index as from there you can change the upcoming array and just change a[i] where both have same digit to a[i]=1 and b[i]=0. then convert the array to a and b simultaneously you will always get a and b in the range .

https://codeforces.net/contest/2057/submission/299695296 this worked lmfaooo jakub.zip

HappyMonk

Well I think it will be like take l and r : Write bit form of them , check the most significant bit of them which will be different and of course the "r" have the bit '1' while l will be '0' at that point (Let it call "A") . Now after that point of change set all the bits of "r" to zeroes and set the after bits of "l" to ones . Now the let numbers will be "a" and "b" ... thinking of third number see the xor of earlier two number ... it will be the continuous stream of 11111... from point A . If the third number came having the same bits earlier to "A" of l(or r, as they same) , so it will be in range to [l,r] , now choose the number such way the stream of 11111... is not disturbed which will be that the bit at point "A" will be "0" and if so then it will lies after "b".

Case 1: If "b" is l : The number "c" will be out range : so we will choose the bit of point "A" be "1" and now the "c" will "a+1" as the last bit will be the "1" which will disturbed the bitstream (LSB one) .

Case 2 : If "b" is not l : The "c" will be "l" . How? you can think it after all you are specialist

Example : 1)

r: 1101100010

l: 1101011111

answer : a=> 1101100000 , b=> 1101011111

b is l so c=> 1101100001

xor =>1101011110

Example : 2)

l: 1101011100 answer : a=> 1101100000 , b=> 1101011111

b is not l so c=> 1101011100

elSaf

41 hour(s) ago, # ^ |

Why the solution always exist in this form ? is there any proof or demonstration ?

32 hours ago, # ^ |

Cant prove it , just thinking greedily it may be wrong .

https://youtu.be/g5cdOm04znE?si=3guhFyCdRtbHroD4

Sarvjeet619

26 hours ago, # ^ |

To maximizer a ⊕ b ⊕ c, we need to have max set bits possible, also keeping in mind that only allowed nos. can be in range [l,r].

a-> 11110101
b-> 11101100

XOR both nos. and take the MSB. Here, MSB is 5th bit. Using this info we can generate 2 nos. whose xor will have all the set bits.

2^4 = 16 & 
(2^4)-1 = 15

Now, further doing xor of 16⊕15 with any other no.(not having MSB greater than 5) other than 0 will reduce it.

Hence, here max value of  
a ⊕ b ⊕ c =  16 ⊕ 15 ⊕ 0 = 31

So, max xor can be obtained with 2^k, 2^(k-1) and 0, where k is MSB.

CR7_Clutch

I have been practicing questions from various sheets (CP-31 mostly) got recently introduced to themeCP.

i can solve 800-900 rated questions with little effort but 1000 rated problems do take up my time.

Can someone lend some resources that might help?

My problem -> I thought Solution of A at an instant but took time trying to prove myself that it will actually work (drawing various scenarios). Same happened with B.

Thanks in Advance for advices :)

garou_rathore_31

myself also new to cp . also want some resources , and peer group to discuss .

I need peer group too lol. But i think post contest discussion on these blogs also helps me a lot (also forces me to spend more time on CF :P )

Trumpsunderwear

I also need peer group, as I am from non-tech background

R.Raj

22 hours ago, # ^ |

hey, can u pls tell how to watch the post contest discussions, like, how to see those streams after they ended as they arent visible once it ends.

bluish

You do not need resources, you need practice.

itsraajjjuuuu

learn basic algo like line sweep prefix sum binarysearch if you know these then practice i guess

yeah but for later as a newbie implementation should be formost priority cuz this time also all A B C was completely implementation based :)

39 hours ago, # ^ |

oh yeah its most important

quater_nion

do CP-31 religiously, and learn from every problem there. I completed the entire 1600 rated list, and it opened gates to many new intuitions and thinking paradigms

36 hours ago, # ^ |

yessirrr CP-31 is best

n0sk1ll

+16

Nice round. Thank you for the wonderful problems.

Behrad.

-44

D should not be a segment tree, solving D in a 2.5hr contest with such easy ABC is the level of high specialist/low expert, and many people at this level don't know segment tree, or they know it at a basic level and don't have enough experience/understanding to solve this kind of segment tree problems where they require a not-so-obvious merging. the problems were good and were at the standard of a Big div1+2 contest, but the fact that D required segment tree and no other solutions existed in such an important contest is disappointing.

tiojuan

you can use sqrt decomposition then

broxxoli

how can we use sqrt decomposition here?

See this: 299683723

I don't know how to solve 2 + 2, it's easy just calculate 2^2 :/

40 hours ago, # ^ |

I agree with you. It is brutal to give a segment tree in a div2D. Maybe it would be more fair to split the task with the easy version not having queries. It would allow divide and conquer approaches.

On the other hand, the number of solves is realistic. The difficulty is appropriate.

_pk_

47 hours ago, # |

C was a very good problem. Thank you.

PaarthJuneja

I learnt two things from this contest:

I can figure out the logic/pseudocode for the question in ~10% of the time I spend on the problem when it should be the opposite. I struggle with writing the code for it.
I suck at bitwise operations. Does anyone here have a good list of questions to practice to get good at basic problems (upto C level?)

do CP-31 sheet it will immensely help and for dsa you can follow striver sheet(topic wise)

_SuguruGeto_

C also can be solved by Ternary Search

JackOfMostTrades

Could you explain your approach please :D.

← Rev. 3 →

Yeah if you know two things

First.You know how Ternary Search works?

Second.Do you know that there is always a triple of numbers l,r and some c where l and r are given numbers?

After watching a 4 min YouTube video, my current understanding is that Ternary search is similar to binary search except that we have two mid values in the search.

As for your second point, I tried making a=r and b=l in the contest, and I kinda "guessed" that there must be a third value that would maximize the pairwise xor sum, and I thought of the 1's complement (starting from the MSB 1 bit of r), and it turned out to give the same pairwise xor sum as in the input example, except that I got values less that L sometimes, and I couldn't think of a better way.

Forgive me for making a long comment.

So you got how my approach works? If not, i'm sorry and could you tell me what you didn't get?Maybe authors approuch will be more understandable

If I got it I would've not asked, but thanks anyways :D (please do not further reply).

choudharyanshul

27 hours ago, # ^ |

can you please explain your approach. i understand that taking two of the numbers as l and r is valid. but what i don't understand is how you reject 1/3rd of the possible values based on the value of the function at mid and mid2

Fleron

can someone explain why my submission is wrong?

https://codeforces.net/contest/2057/submission/299685645

i did exactly what editorial says

I_FloPPed21

at problem c you can choose a as being l , b as being r ,and c as being the value that maximizes the sum , so to calculate c you go decreasingly on bits and if the bits are present in both l and r you have to take it,if it's present in l we have to take it and if its not presesnt in l we just see what would happen if we took this bit and then choose the other smaller one greedily,overall complexity(30^2)

truered

I tried to find c ,but it fails at certain cases. What i thought was c would consists of all set bits that are unset in both a and b for example) if a = 6 and b = 22 , c would be 9.But this fails when c <= l. Can we find c using brute force ? if a is L and b is R.

this is how i did in contest

https://codeforces.net/contest/2057/submission/299670841

i did something similar to find c.

my solution: let k'th bit be the highest bit that is different in l and r. now, case 1: if all bits lower that k'th are opposite in l and r. you have the answer as a=l, b=r and any c such that l <= c <= r, other than a or b.

Case 2: let p'th bit be the highest bit (< k'th) where we have same value set for l and r. here we can construct c as —

for bits > k'th: use same bit value as l (or r).

for bits <= k'th: if i'th bit is same in l and r. for c, set its i'th bit as negation of this value. if i'th bit is different in l and r — if p'th bit is 0 in l (or r), set i'th bit of c to be same as i'th bit of l. else, set i'th bit of c as i'th bit of r

my solution: https://codeforces.net/contest/2057/submission/299666931

aneesh2002

42 hours ago, # ^ |

can you explain the last step ? i get it if its same we set its negation but what to do if its different

34 hours ago, # ^ |

try to construct c for these two examples:

r = 11000 l = 10110

r = 11001 l = 10110

the logic i mentioned above helps maintain c within the range [l, r]

https://codeforces.net/contest/2057/submission/299695296 check this

susvent

← Rev. 5 →

I cheesed C with a randomization algorithm.

It passed systests.

Please hack it.

https://codeforces.net/contest/2057/submission/299661239

V2: https://codeforces.net/contest/2057/submission/299698846

UPD: Hacked by MattTheNub

ay012

whats the main idea for randomization algo to work here ?

JeanBombeur

For E you can forget the binary search altogether by processing queries offline.

For a query (a, b, k), everytime you change the distance d(i, j), check if d(i, j) < k, and the first time this happens, the answer to that query is the value of the edge you're adding.

By storing the lists of queries for each (a, b) sorted by k, you can process all these simply as you modify the graph, and you don't have to store the dp layers.

tkacper

+36

With this offline approach we can optimize the E1 solution from editorial down to O(n^4/64) using bitsets, which easily fits in E2 time limit.

bitset

43 hours ago, # ^ |

+12

nice

UltraMate

can so explain why my submission(problem b) is wrong?

https://codeforces.net/contest/2057/submission/299644013

ashays

read this: https://codeforces.net/blog/entry/101817

balllightning37

Several python solutions from I've seen (including mine) for problem B have TLE'd on test case 17. What is the cause of this?

apollo07

Potential use of unordered_map in C++ or (Python) dictionary has led to hash collisions

stup_bitch

You mean they made special test for unordered_map? I always thought that unordered_map can be only like 5 times slower, if it's not some "special" test.

MathGuy1729

Someone probably succesfully hacked someone by causing hash collisions, and all succesful hacks end up in system testing.

philip.hy.xu

I found that changing the keys of my dictionary (e.g. multiplying by a big constant) solved the issue.

faroukfaiz

21 hour(s) ago, # ^ |

Thanks! Simply multiplying by 2 seems to fix it for python.

Before: 299823842
After: 299825408

Bnahmad23

Hmmm, IDK why I approached D the way I did, segment tree would've been much simpler and faster especially since I used the same logic for my solution.

However, it's weird that $$$O(n * \sqrt{n})$$$ struggled to pass. In the end, it squeezed in just enough to pass when I changed the block size from $$$\sqrt{n}$$$ to $$$550$$$ which is also weird. Any ideas?

Here's the submission 299683723

poituk

My submission is faster 299666269. Why do you use multiset?

25 hours ago, # ^ |

I honestly don't know, it just happened LOL

Tho it's not adding to the complexity in big O, it's a heavy constant factor.

It's still interesting that increasing the block size actually made it fit.

cfcboc239

20 hours ago, # ^ |

you are aiming not for O(sqrt(n)* n * logn) but for O(sqrt(nlogn)) Sorry, my english very bad

5 hours ago, # ^ |

Can you explain further?

because as I see it I'm aiming for O(n * (log(n) + sqrt(n))

hardik_jn_7

can anybody tell why it is giving TLE?(B problem) https://codeforces.net/contest/2057/submission/299631565

Bambo0st

35 hours ago, # ^ |

Use map instead of unordered_map

Soultaker

15 hours ago, # ^ |

Wow, that's really silly. Isn't std::unordered_map supposed to be faster than std::map? Otherwise, what's the point?

edit: apparently std::unordered_map is vulnerable to hash collision attacks, see this excellent post by neal: https://codeforces.net/blog/entry/62393 (so it's not that unordered_map is slower in general, it's just that it's vulnerable to specific hacks).

Both map and unordered map have high constant factor and are very heavy structures.

Also map is more consistent in complexity where it's log(n) * constant while unordered map have undefined behaviour which can make queries take O(n).

I'm not sure if this is scientifically correct but that's what I learned from practice idk.

gaby

https://codeforces.net/contest/2057/submission/299695552

For b this shud work ryt it's just nlogn but tle for testcase 14

You got it cause of the unordered_map (everyone who used unordered_map got TL, even python coders).

kaylent13

Got the same. Unordered_map for ints should be exactly O(1), shouldn't it?

It is O(n) in worst case. And that worst case is where your solution failed. Try using map instead and it will probably work. Blog link for the same

nnv-nick

Solution code for D doesn't match the editorial. Editorial says that it's enough to store answer, minimum and maximum of $$$a_i - i$$$, but in the solution there are some $$$max1, max2, min1, min2$$$ stored in the node

Serial_Coder

If you observe carefully, we can create 2 separate test cases to be solved:

In the range (l, r), al is the minimum element, and ar is the maximum element. This can be solved by changing the array to: ai-i, and final answer be given as (ar-r)-(al-l).
In the range (l, r), al is the maximum element, and ar is the minimum element. This can be solved by changing the array to ai+i, and final answer be given as (al+l)-(ar+r).

This 2 cases can be modeled in separate segtrees, or storing the information in the same segtree.

Yep, I've upsolved it already, just pointing out an incorrect editorial

Oz121

Can you explain how you implemented this? In particular, after you build the two segtrees, how do you query the answer? I think it's just querying the max difference between two elements where the max element appears after the min one (or vice versa), but not sure how to code this.

adel54321

Why using unordered_map in problem B gave TLE on testcase 14!!!!

Replacing it with map worked...

my solution passed prestests, but failed in system testing.. this is awful

I_love_kirill22

Because unordered_map is not implemented in the best way in C++.

You can read more about that here

thanks..

I already found this amazing post and was reading it and it seems to work.

Does it mean that we should always use map in cpp in competition?

While using unordered_map with custom hash worked for problem B, it doesn't seem to be faster than the map implementation in any sense

ghostVS

Solutions using default unordered_map in c++ generally get hacked because the hash function is fixed and specific test cases could be made in order to create lots of collisions which changes the find tc to O(n) from O(1). For a random custom hash, specific test cases for collisions can't be created.

kitosforos

In Python, I feel very comfortable, but I don't have the same ease with C++, and I’m not sure how to achieve it—I guess it’s just a matter of practice. This was my third contest, and I managed to solve the first two problems using Python. However, during the system testing, the second problem resulted in a time limit exceeded, even though my algorithm was correct :(. Any advice on transitioning to C++?

henryyyh

You got TL not because you used python, but because you used dictationary. Potential use of unordered_map in C++ or (Python) dictionary has led to hash collisions.

d-light

Does this not affect HashMaps in Java?

I understand. But, now taking in general, is it possible to solve all the problems in python with the same algorithm that are solved in C++?

A lot of tasks (usually starting with div2D) cannot be solved in Python, but they can be done in C++. Sorry my english is very bad

timg8710

For E2, using DP and binary search is overcomplicated. We don't need to use either by processing the queries offline, resulting in much easier code.

https://codeforces.net/contest/2057/submission/299696265

macaquedev

Can you please elaborate on how your solution works? At the moment, all I can understand is that you're sorting queries and running Floyd-Warshall at the beginning, and then after sort(edges.begin(), edges.end()) I'm a bit lost.

https://codeforces.net/blog/entry/138119?#comment-1235154

11DE784A

Performance Query: Codeforces Problem

Description

I implemented two similar solutions for a problem, but I’m encountering unexpected behavior regarding their performance.

1st Code

299628021

Converts each element of the array to a string using a = str(a) before processing it in the freq dictionary.

2nd Code

299696582

Directly uses the elements as integers without converting them to strings.

Observation

1st Code: Runs successfully without TLE, even for larger test cases.
2nd Code: Gives TLE at test case 17.

Expectation

I expected the 2nd Code to be faster because: 1. It avoids the overhead of string conversion (str(a)). 2. Integer keys in dictionaries should perform better due to faster comparisons and reduced memory usage.

Confusion

Why is the 1st Code faster in this case?
Is there something specific about the input data or Python’s dictionary implementation that might favor string keys over integer keys?
Any insights into this would be greatly appreciated. Thank you!

LMeyling

+26

About E1. Why is E1 in the set when the constraints are so tight that some intended complexity solutions don't pass? Mine was $$$O(n^3 logn)$$$ takes 5600ms in the mashup, 4200ms in C++20), which is fine not to pass, in my opinion. But some $$$O(n^3)$$$ solutions are not passing as well, for example (funnily enough, this passes on C++23). For me, this just led to spending a lot of time trying to optimize constants (an almost correct time complexity) instead of thinking about how to solve E2.

Also, the constraints were not even tight enough to kill bitset, so I am curious why $$$n = 400$$$ was chosen.

TrendBattles

Well, mine was kinda similiar to the TLE submission but yeah, I did get pass even with C++17. I guess it's about the implementation now.

kingsmaker

could you please explain you code https://codeforces.net/contest/2057/submission/299668054 especially why is the dfs done in such a weird way

Natsuzora

38 hours ago, # ^ |

My $$$O(n^3\log n)$$$ sol passed both E1 and E2 (E2 needed some constant optimization though)

xennygrimmato

What was your $$$O(n^3\log{n})$$$ idea?

Jelefy

299676764 I did some research and it turns out that the complexity is indeed $$$O(n^4)\sim O(n^4\log n)$$$ but the constant is too small to be hacked ... so forget about it (maybe someone else can construct a stronger test)

Got TLE for B with two approaches: 299696692 299635098 What could be wrong?

fbrunodr

Unordered_map; use map instead

nonrice

It's TLE because you used unordered_map instead of map. Here is your code accepted just by changing unordered_map to map: 299701332

You can read more on the problem here: https://codeforces.net/blog/entry/62393

In the future just use map instead of unordered map, unless you absolutely need unordered map.

drexdelta

46 hours ago, # |

+13

Sadly, nobody got 2025 rank in today's contest :( .

In the editorial for E1 it says

d′[i][j]=min{d[i][j],d[a][i]+d[b][i],d[b][i]+d[a][i],}

shouldnt it be d'[i][j]=min(d[i][j],d[a][i]+d[b][j],d[b][i]+d[a][j]}?

28 hours ago, # ^ |

thanks, fixed

sayglenn

299701558

Hey, could anyone figure out why my solution TLEs? It runs in O(nlogn) time with the single sort, which is the same complexity as the solution.

lakshyasinghal006

I propose a solution for 3rd one.. it seems simpler to me.. please give your opinions -

Take a = l, b = r.
Find the 1st different bit in l and r.
Then take complement of rest of part of l and r and store resulting number in cl and cr respectively.
Now if cl < r, c = cl, Else if cl = r, c can be any number between l and r Else c is cr.

LM2357

Does this AC though?

I hope so.. bcz I derived it on paper.. but didn't code yet

om.nom

30 hours ago, # ^ |

But why take a = l and b = r? What's the proof?

24 minutes ago, # ^ |

ughh.. it's because partial complement of at least one of l or r lies between l and r and the third number can be anything to maximise the some so we chose it to be the remaining of l and r. Proof of this is simple, try urself( I'm too lazy to explain the whole thing :( )

Neeki

45 hours ago, # |

-20

Wtf segment tree problem in D? It is bad

sy-kid

My code 299683214 passed on pretests and gave tle on final tests, and now it is again passing 299704642.

Can it be reviewed? I_love_kirill22 induk_v_tsiane dope

AnwarAuto

Can anyone help me figure out where I go wrong in my solution ? https://codeforces.net/contest/2057/submission/299683979 I basically try to maintain the maximum, the minimum, and their respective indexes, along with the value of a segment for max difference. The value becomes something like max(left value, right value, abs (left max — right min) — abs (l1-r1) , abs(left min — right max) — abs (l2-r2)) where li ri are indexes of the maximum and minimum

golions

I had a different solution for E1/E2, maybe it is easier to understand for some people.

E1: For every query, check if each edge can be the answer. To do so efficiently, for every edge going from u to v with weight w, precompute the the arrays udist and vdist, where udist[x] equals minimum # of edges with weight >= w needed to go from u to x, and same for vdist[x]. This can be done with 2M djikstras, so complexity of precomutation is O(M^2 log N). Checking if an edge can be the answer can be done in O(1) by checking if udist[a] + vdist[b] < k or udist[b] + vdist[a] < k. Total complexity is O(M^2 log N + MQ). MQ part might be bad complexity but it is just some array lookups so very low constant factor. Submission: 299661500

E2: Same thing as E1 except observe that the edge of the answer must be on the MST. This means for every query you only need to check O(N) edges. You also only have to do the precomputation step for O(N) edges. Use djikstras on dense graphs (O(N^2 + M) = O(N^2)), so complexity of precomputation is O(N^3). Total complexity is O(N^3 + NQ). Submission: 299706362

AminAnv1

Look at this test for problem E1:

model solution prints "1" but answer and your soluton is "100". Am I wrong?

44 hours ago, # |

main and tourist prints "1" but answer is "100". Am I wrong?

+29

The input must guarantee that any path from vertex $$$a$$$ to vertex $$$b$$$ contains at least $$$k$$$ edges. In your case, the path $$$1 - 2 - 3$$$ contains only $$$2$$$ edges, which is less than $$$k$$$.

no_fst

40 hours ago, # |

I'm curious about why my submissions got TLE:

E1: https://codeforces.net/contest/2057/submission/299716714 I also see one of my friend's submission, he wrote the same thing as me, but he got accepted. https://codeforces.net/contest/2057/submission/299642675

If it's because of my large constant, I don't think this is fair.

yhy001

38 hours ago, # |

-14

ABC were too easy, but D was an interesting segment tree problem

--a

In problem C editorial:

Why do bits more significant than kth bit do not affect the outcome?

Why does taking x as divisible by 2^k , x-1 & any number not these 2 all in the range [l, r] give maximum answer.

The first paragraph is pretty clear, but how it relates to the next 2 paragraphs is not.

akshaykhandelwal

37 hours ago, # |

+11

E2 can be solved in O(N^3) without the extra term of qlogN by precomputing answers to all possible queries on the go — https://codeforces.net/contest/2057/submission/299682395

This allows to answer any number of queries (say 5e7) in the given TL.

umesh_konduru

24 hours ago, # ^ |

that's pretty elegant

Defylogicguy

I think B is easier than A cuz it only requires implementation.

skibidi_sort

36 hours ago, # |

solved B passed pre test woke up to tle due to using erase method in vector . I dont like this pre test thing

35 hours ago, # |

Someone explain C like I am 8 years old.

Chandraprakash_Pandey

34 hours ago, # |

This Contest was Div1 or Div2? How do we get to know if a contest is div 1 or div2 if not mentioned in contest name?

robinyqc

16 hours ago, # ^ |

In this case, the contest announcement would clarify the rating.
For example, in this contest, they said "The round will be rated for all participants."

82 minutes ago, # ^ |

oh okay Thanks!

phoenix_vasu

In Problem B, using unordered_map passed the pretests but caused TLE on test 11. Switching to map resolved the issue, and the solution was accepted. Can someone explain why ?

submission with unordered_map : https://codeforces.net/submissions/phoenix_vasu# submission with map : https://codeforces.net/submissions/phoenix_vasu# The only difference between these 2 code is unordered_map and map

MisterGir

read this blog link

AhmetKaan

33 hours ago, # |

I solved D by finding maximum subarray sum on the difference array

can you elaborate how you did it using difference array and why used difference array as such ?

First, think a descending array. Since the first element is the maximum you need to take it and while you are taking the elements one by one by iterating to the right, the minimum will decrease as the difference, and since you took one new element the number of elements you have chosen will increase and your answer will decrease by 1. So, when you select a new element your answer increases by (difference-1).

To generalize, when you select the subarray with maximum sum the left and right borders of it are the maximum and the minimum element in the optimal subarray.

The maximum can be the left border and the right border so to cover it I found the maximum subarray sum in the difference array by subtracting 1 from every element, and I also found the maximum subarray sum by complementing its elements and subtracting 1 from them. We need to subtract 1 from the elements because when you select one more element you need to subtract 1 because the score is (maximum-minimum-number_of_elements) I think you may better understand by trying some cases on the paper. Please feel free if you have a question.

fanboys

Why did the problem 2057B - Gorilla and the Exam I cannot use unordered_map, I got TLE when using using it

Liuxizai

+42

ML of G is too tight I think. The 2e6 data range and the 256 MB space literally made no sense.

Daemon_

32 hours ago, # |

Can anyone explain to me, why using "arr = [int(x) for x in input().split()]" instead of arr = input().split() results in execution time becoming more than 10 times slower.

299755424 --> slower one 299754131 --> faster one

Kolyanchick

because python is stupid language

← Rev. 4 →

I take it back =) This problem occurs in all languages and is caused by the peculiarities of hash tables

gardengnome

The issue is not the code that you quote in your comment, but rather that you then add these values to a Counter. If you add them as an int, this is subject to hash exploits, more info here for example. However inserting them as str avoids these issues. This is a common reason for TLEs, and (almost?) everybody comes across this issue at some point. The aforementioned blog briefly discusses how to avoid getting hacked.

28 hours ago, # |

there is a mistake in E1: $$$\textrm{d}'[i][j] = \min { \textrm{d}[i][j], \textrm{d}[a][i] + \textrm{d}[b][\not{i} \ j], \textrm{d}[b][i] + \textrm{d}[a][\not{i}\ j], }$$$

upd: it fixed

giokit

27 hours ago, # |

I have done Problem C with a idea that l and r can be contained in an answer,and after that I use dfs to find another integer,and it gets ac,could anyone please tell my why this ieda works well?

SNOJ

Has anyone Happy New Year! question D without segment tree? For example, with sqrt?

ChickenInKitchen

I did it with sqrt decomposition check my submission

8 hours ago, # ^ |

thanks!

Karim__2

26 hours ago, # |

this is not allowed ,this user is hiding his submissions .

https://codeforces.net/contest/2057/submission/299609972

case3

23 hours ago, # ^ |

The guy (maybe) doing something fishy but that is some cool shit.

MAKMED1337

During the round I got WA3 299664488. However my solution was failing due to OOB, and codeforces returned WA, instead of RTE, here is a fixed version 299794827. I was breaking my head for it :(.

RiShi_RaJ14

24 hours ago, # |

I am surprised you have 2100+ rating but why you are still at pupil , is there an error on CF ?

16 hours ago, # |

How to reduce the time complexity from O(E^2) where E = n(n-1)/2 on problem E2

My submission

Kcits970

9 hours ago, # |

For the solution code for D, what is the purpose of subtracting $$$n-1$$$ from the second value of the pair?

The code still gets accepted when I replace

t[i] = {a[i] - i, a[i] + i - n + 1};
...
t[p] = {x - p, x + p - n + 1};

with

t[i] = {a[i] - i, a[i] + i};
...
t[p] = {x - p, x + p};

Seems like an unnecessary operation, unless I'm missing something.

6 hours ago, # ^ |

It may be more intuitive for some people, as $$$x+p-n+1$$$ effectively means "take the reverse index of the position (that being $$$n-1-p$$$), and subtract from $$$x$$$, making this in some sense the same thing as $$$x-p$$$, just in reverse. It doesn't change the solution, as it's a constant change for each value in the array and you always take the difference of $$$2$$$ values in the array.

6 hours ago, # |

won't the E1's solution fail at the below testcase. It should be giving 11 as the answer but is giving 1.

The problem statement guarantees that for every query $$$(a, b, k)$$$, any path from $$$a$$$ to $$$b$$$ contains at least $$$k$$$ edges. In your given test case, this isn't satisfied: you have a query $$$(1, 4, 4)$$$, yet there is a path from $$$1$$$ to $$$4$$$ using only $$$3$$$ edges ($$$1-2-3-4$$$). Therefore, your given test case isn't valid.