Invitation to ICPC-de-Tryst (ANCC, IIT Delhi)

»

BiggestOtaku

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

+26

Contest clashes with cc starters.

→ Ответить

»

BladeRunner

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

+18

We had initially planned to keep it yesterday but was clashing with a CF contest so all submissions would have been in queue which would have spoiled the experience. Also today is the last day of our Tech Fest, so it had to be conducted today :(

→ Ответить

»

ProofByContradiction_

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

+6

I think starting it at 3:30 Pm would be a good idea.

→ Ответить

»

magga

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

+34

Have mercy on us job peeps man :')

→ Ответить

»

ProofByContradiction_

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

+11

Casually calling me jobless without saying :)

→ Ответить

»

kindasomethin

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

+2

Where's the contest link? when will it be visible??

→ Ответить

»

codevode

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

-16

https://codeforces.me/contestInvitation/2ca92069b86064f34ba695a2ecd35f982a3cf780

Here it is , indeed it was in the WhatsApp group, do upvote

→ Ответить

»

ishika.agrahari

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

← Rev. 2 →

0

team up?

→ Ответить

»

i_love_pushups

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

0

would you like to join in my team? i am also from nsut, first year.

→ Ответить

»

altalt

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

+21

Plese adopt me. I am a fresher too.

→ Ответить

»

NullMeowference

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

← Rev. 2 →

0

Correct me if I am wrong, but for B, do we divide the array into blocks of size 2 * k and find answers in 3 * (k — 1) for each block? So it takes 3(n/k)(k — 1) operations that are less than 3n.

For each block, we find the aggregate for suffixes and prefixes in k — 1 operations for each half and merge answers from each half in at most k — 1 operations again.

→ Ответить

»

MridulAhi

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

+7

How do you find the required value for each subarray of length k using this? The intended idea is to partition the array in block sizes of k, and finding aggregate for each prefix and suffix of the block, after which we can find value for each subarray of length k in at most 1 query.

→ Ответить

»

NullMeowference

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

← Rev. 3 →

0

Same idea. I meant that we divide the array into blocks of 2*k, calculate prefixes of the right half of size k and suffix of the left half of size k, and merge in 1 query for all k-1 arrays for which we don't know the answer. btw, cool contest!

→ Ответить

»

Goku2727

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

← Rev. 3 →

0

Can Someone pls Provide Hints/Solution of A.

→ Ответить

»

MridulAhi

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

+6

Since a diverse subarray contains at most $$$500$$$ distinct numbers, any element’s frequency is at most $$$500$$$ in it. Iterate over $$$r \in [1,n]$$$. Maintain a set $$$\mathcal{S}$$$ that stores the last index where each element in the current prefix $$$[1,r]$$$ appears. Maintain an array of length $$$501$$$ where the entry for $$$y$$$ stores the largest index $$$l'$$$ such that $$$\text{max_freq}[l',r] \ge y$$$. Iterate over ranges of $$$l$$$ with fixed value for distinct numbers ($$$x$$$) in $$$[l,r]$$$ using $$$\mathcal{S}$$$. Take the intersection of this range with the range where $$$\text{max_freq} \le x$$$ and add it to answer. The overall time complexity is $$$O(n \log n + n \cdot \max(a_i))$$$.

code

#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

using namespace std;
using namespace __gnu_pbds;


struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
                // http://xorshift.di.unimi.it/splitmix64.c
                x += 0x9e3779b97f4a7c15;
                x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
                x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
                return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
                static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
                return splitmix64(x + FIXED_RANDOM);
        }
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T rand(T a, T b){
    return uniform_int_distribution<T>(a, b)(rng);
}

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<int> vi;


#define rep(i, a, b) for(int i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long

const ll mod = 998244353;
const ll inf = 1e18;

/* ----------------------------------------------------- GO DOWN ---------------------------------------------------------------------- */





signed main() {

        ios::sync_with_stdio(0);
        cin.tie(0);

        int t;
        cin >> t;

        while (t--) {

                int n;
                cin >> n;
                int a[n];
                for (auto &x : a) cin >> x;

                int ans = 0;
                set<int, greater<int>> s;
                vector<int> first_freq(502, -1);
                vector<int> v[501];
                for (int i = 0; i < n; i++) {
                        int x = a[i];
                        if (sz(v[x])) {
                                s.erase(v[x].back());
                        }
                        s.insert(i);
                        v[x].push_back(i);
                        for (int j = 1; j <= min(sz(v[x]), 501ll); j++) {
                                first_freq[j] = max(first_freq[j], v[x][sz(v[x]) - j]);
                        }
                        int l = i;
                        int f = 1;
                        for (auto u : s) {
                                ans += max(0ll, l - max(u, first_freq[f]));
                                l = u;
                                f++;
                        }
                        ans += max(0ll, l - max(-1ll, first_freq[f]));
                }

                cout << ans << "\n";

        }

       
}

→ Ответить

»

Goku2727

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

0

Thanks;

→ Ответить

»

Tobo

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

0

What's the intended solution of problem C？

→ Ответить

»

ghoul932

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

+10

Greedily remove subtrees of size $$$\geq k$$$ from the bottom of the tree. Tree is decomposed into chains using HLD to maintain subtree sizes. $$$O(n/k)$$$ segment tree operations are needed to find the value for each $$$k$$$ so overall time complexity is $$$O(n\log^2 n)$$$.

→ Ответить

»

NuclearMint

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

+3

Can you explain how this is $$$O(n * log^2 n)$$$ ? , I simulated this obvious greedy using HLD but my complexity seems to be $$$O(n * log^3 n)$$$ because you remove at most $$$O(n * log n)$$$ edges and for each edge HLD update is $$$O(log^2 n)$$$

→ Ответить

»

ghoul932

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

← Rev. 2 →

+10

Only the chain having the root of the removed subtree needs to be updated. When a chain is no longer useful, then add its remaining node count to its parent chain.

code

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define uint unsigned long long
using namespace std;
const int mod=1e9+7;

struct hld {
    int n;
    vector<vector<int>> g;
    vector<int> sz, par, depth, head, pos, rpos;
    hld(int n)
        : n(n), g(n), sz(n), par(n), depth(n), head(n), pos(n), rpos(n) {}
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void build(vector<int> roots = {0}) {
        int k = 0;
        for (int r : roots) {
            dfs_sz(r);
            head[r] = r;
            dfs_hld(r, k);
        }
    }
    void dfs_sz(int v) {
        sz[v] = 1;
        for (int &c : g[v]) {
            if (c == par[v]) continue;
            par[c] = v;
            depth[c] = depth[v] + 1;
            dfs_sz(c);
            sz[v] += sz[c];
            if (sz[c] > sz[g[v][0]] || g[v][0] == par[v]) swap(c, g[v][0]);
        }
    }
    void dfs_hld(int v, int &k) {
        pos[v] = k++;
        rpos[pos[v]] = v;
        for (int c : g[v]) {
            if (c == par[v]) continue;
            head[c] = (c == g[v][0] ? head[v] : c);
            dfs_hld(c, k);
        }
    }
    bool is_anc(int u, int v) {
        return pos[u] <= pos[v] && pos[v] < pos[u] + sz[u];
    }
    int lca(int u, int v) {
        while (!is_anc(head[u], v))
            u = par[head[u]];
        while (!is_anc(head[v], u))
            v = par[head[v]];
        return is_anc(u, v) ? u : v;
    }
};

struct node {
    int maxval;
    int lazy;
    node() : maxval(0), lazy(0) {}
    node(int x,int y) : maxval(x), lazy(y) {}

    friend ostream &operator<<(ostream &os, const node &node1) {
        os << "{ maxval: " << node1.maxval << " lazy: " << node1.lazy<<" } ";
        return os;
    }
};

void merge(int i, vector<node> &st) {
    st[i].maxval = max(st[i * 2].maxval, st[i * 2 + 1].maxval);
}

void push(int i, vector<node> &st) {
    st[i * 2].maxval += st[i].lazy;
    st[i * 2 + 1].maxval += st[i].lazy;
    st[i * 2].lazy += st[i].lazy;
    st[i * 2 + 1].lazy += st[i].lazy;
    st[i].lazy = 0;
}

void modify(int i, int lx, int rx, int l,int r, int v,vector<node> &st) {
    if (l >= rx || r <= lx)
        return;
    if (lx >= l && rx <= r) {
        st[i].maxval += v;
        st[i].lazy += v;
        return;
    }
    push(i,st);
    int m = (lx + rx) / 2;
    modify(i * 2, lx, m, l, r, v,st);
    modify(i * 2 + 1, m, rx, l, r, v,st);
    merge(i,st);
}

pair<int,int> first_right_more(int i, int lx,int rx, int l,int r, int v, vector<node> &st) {
    if (st[i].maxval < v || l >= rx || r <= lx)
        return {-1,-1};
    if (rx - lx == 1)
        return {lx,st[i].maxval};
    push(i,st);
    int m = (lx + rx) / 2;
    pair<int,int> res = first_right_more(i * 2 + 1, m, rx, l, r, v,st);
    if (res.first != -1)
        return res;
    return first_right_more(i * 2, lx, m, l, r, v,st);
}

void print_vec(vector<node> &x) {
    for (int i = 0; i < x.size(); i++) {
        cout << x[i] << " \n"[i == x.size() - 1];
    }
    cout << endl;
}

void solve() {
    int n;
    cin >>n;
    hld h(n);
    for(int i=0;i<n-1;i++) {
        int u,v;
        cin >>u>>v;
        u--,v--;
        h.add_edge(u,v);
    }
    if (n==1) {
        cout <<1<<"\n";
        return;
    }
    h.build();
    vector<pair<int,int> > chains;
    for(int i =0;i<n;i++) {
        if (h.sz[h.rpos[i]]==1) {
            chains.push_back({h.sz[h.head[h.rpos[i]]],h.rpos[i]});
        }
    }
    //sort in decreasing order of size
    sort(chains.begin(),chains.end(),greater<pair<int,int>>());

    int l1  = 1;
    while(l1<n)
        l1*=2;
    vector<node > st(2*l1,{-mod,0});
    for(int i=0;i<n;i++)
        st[l1+i].maxval = h.sz[h.rpos[i]];
    for(int i=l1-1;i>0;i--)
        merge(i,st);
    vector<int> ans(n+1,0);
    // print_vec(st);
    for(int k1=1;k1<=n;k1++) {
        assert(chains.size()>=1);
        while(chains.back().first<k1)
            chains.pop_back();
        vector<pair<pair<int,int>,int> > changes;
        for(int j = chains.size()-1;j>=0;j--) {
            while(true) {
                int from = h.pos[h.head[chains[j].second]];
                int to = h.pos[chains[j].second];
                assert(from<=to);
                pair<int,int> res = first_right_more(1,0,l1,from,to+1,k1,st);
                if (res.second < k1) {
                    break;
                }
                modify(1,0,l1,from,to+1,-res.second,st);
                changes.push_back({{from,to+1},res.second});
                ans[k1]++;
            }
            int head_child_left = first_right_more(1,0,l1,h.pos[h.head[chains[j].second]],h.pos[h.head[chains[j].second]]+1,-mod*mod,st).second;
            int dec = h.sz[h.head[chains[j].second]]-head_child_left;
            int next = h.par[h.head[chains[j].second]];
            int from = h.pos[h.head[next]];
            int to = h.pos[next];
            modify(1,0,l1,from,to+1,-dec,st);
            changes.push_back({{from,to+1},dec});
        }
        for(auto x:changes)
            modify(1,0,l1,x.first.first,x.first.second,x.second,st);
    }
    int a =0;
    for (int i=1;i<=n;i++) {
        a += ans[i];
    }
    cout <<a<<"\n";


}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) {
        solve();
    }
}

→ Ответить