One of the best educational contests. Thanks atcoder!

What a action packed day tommorow :0

ABC -> CF -> kickstart back to back with around 30 min break in between each of them.

so the recent AtCoder rounds have two extra problems than the regular ones we used to, these two problems have 500, 600 difficulty, maybe it worth increasing the contest time a little?

Hope this contest will bring good luck to me in CSP-S 2021 (1st round) tomorrow :)

P.S. If you don't know what CSP is click here

HardCoder

For me C/D was too hard according to previous :(

Ho to solve D ?

The implemention of E and F was so painful (at least for me) !!!!!

Can someone share a neat implemeantaion of pE?

For me the gap from D to E was big. Solved A-D in like 30 minutes, than did not found any clear idea for E or F.

How to solve G — Propagation?

DELETED

how tf solve A? I have 1 WA and can't get what's wrong...

Why does this not work for G? (35x AC, 2x WA)

Split nodes into "light" (degree $$$\lt \sqrt{m}$$$) and "heavy" (degree $$$\geq \sqrt{m}$$$).

For each node we additionally keep track of all adjacent heavy nodes.

For light nodes, we directly push the result of a query to all of its neighbors after a query.

Additionally for all nodes (heavy or light), when we have a query, we will check for any newer values from heavy neighbors.

Remember to perform a heavy neighbour pull at the end for all nodes before printing the answer.

This takes a total of $$$O(m + (n + q) \sqrt m)$$$ since there can be at most $$$\sqrt{m}$$$ heavy nodes in the graph by definition.

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 2e5 + 5;

int n, m, q, u, v, x, ans[maxn], last_pushed[maxn], last_pulled[maxn];
vector<int> adj[maxn], heavy[maxn];

int is_heavy(int x)
{
    return x * x >= m;
}

void heavy_pull(int x)
{
    for(auto v : heavy[x])
        if(last_pushed[v] > last_pulled[x])
        {
            ans[x] = ans[v];
            last_pulled[x] = last_pushed[v];
        }
}

void light_push(int x)
{
    for(auto v : adj[x])
        {
            ans[v] = ans[x];
            last_pulled[v] = last_pushed[x];
        }
}

void apply(int x, int curtime)
{
    heavy_pull(x);
    last_pushed[x] = last_pulled[x] = curtime;
    if(!is_heavy(adj[x].size()))
        light_push(x);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 0; i < m; i++)
    {
        cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 0; i < n; i++)
    {
        ans[i] = i + 1;
        for(auto v : adj[i])
            if(is_heavy(adj[v].size()))
                heavy[i].push_back(v);
        last_pulled[i] = last_pushed[i] = -1;
    }
    for(int i = 0; i < q; i++)
    {
        cin >> x;
        x--;
        apply(x, i);
    }
    vector<pii> order;
    for(int i = 0; i < n; i++)
    {
        heavy_pull(i);
        cout << ans[i] << " ";
    }
    cout << "\n";
    return 0;
}

lol i hate geometry problems

I need to go debug my E. My basic idea was to represent the board as a bitmask try all 2^16 bitmasks and check a) Do i cover the required cells? b) Are the cells i have connected? (used DSU) c) Does my polygon have any holes? (used DSU) d) Do i have any self intersections (i.e. corners where one pair of opposite diagonals are included and the other pair where there are not)? However, even on the sample, I'm coming up short on the count, so I'm overkilling boards somewhere.

God save me from tasks like this E. Only you and its author know which moat is considered correct.

Can someone help me with D) . I used knapsack . why is it wrong ?

dp[0][0] = 0;

for(ll i=1; i<=n; ++i) {
    for(ll j=1; j<=(x)*(y); ++j) {

       ll cur_y = j / (y + 1);
       ll cur_x = j % (y + 1);

       dp[i][j] = dp[i-1][j];

       if(cur_x >= a[i-1] && cur_y >= b[i-1]) {
         dp[i][j] = min(dp[i][j], dp[i-1][(cur_x - a[i-1])*(cur_y - b[i-1])] + 1);
       }
    }  

}

if(dp[n][x*y] == mod){
    cout << -1 << "\n";
    return;
}

cout << dp[n][x*y]  << endl;

How to solve D, I got the easy $$$O(n^{4})$$$ dp, optimized it like hell for it to pass. What was the $$$O(n^{3})$$$ idea?

Please someone explain why this comparator doesn't work? for C.

bool co(const string s,const string t){
  p=sz(s),q=sz(t);
  i=0;
  while(i<min(p,q) and mp[s[i]]==mp[t[i]])i++;
  if(i<min(p,q) and mp[s[i]]<mp[t[i]])return true;
  return false;
}

This is my code for problem D, can somebody give me a counter test for this code? I got 40/50 test passed at atcoder.

void solve() {
	int n, x, y;
	read(n, x, y);
	vector<pair<int, int>> v(n);
	for(auto& p : v)
		read(p.first, p.second);
	const int mxN = 650;
	vector<vector<int>> dp(mxN + 1, vector<int>(mxN + 1, n + 10));
	dp[0][0] = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = mxN; j >= v[i].first; --j) {
			for(int k = mxN; k >= v[i].second; --k) {
				dp[j][k] = min(dp[j][k], dp[j - v[i].first][k - v[i].second] + 1);
			}
		}
	}
	int ans = n + 10;
	for(int i = mxN; i >= x; --i)
		for(int j = mxN; j >= y; --j)
			ans = min(ans, dp[i][j]);
	if(ans > n)
		cout << "-1\n";
	else
		cout << ans << "\n";
}

problem D — can anyone guide me where my logic getting wrong? top-down implementation

#include <bits/stdc++.h>
using namespace std;
int inf = 400;
vector<pair<int,int>> vec;
vector<int> dp;
int mintiffin(int n, int x, int y){
        if(x<=0&&y<=0) return 0;
        if(n<0) return inf;
        if(dp[n]>=0) return dp[n];
        int j = mintiffin(n-1,x-vec[n].first,y-vec[n].second)+1;
        int i = mintiffin(n-1,x,y);
        //cout << i << " " << j << endl;
        dp[n]  = min(i,j);
        return  dp[n];
}

void solve(){
    int n;cin>>n;
    int x,y;cin>>x>>y;
    vec.resize(n);
    dp.resize(n,-1);
    for(int i=0;i<n;i++){
        cin>>vec[i].first>>vec[i].second;
    }

    mintiffin(n-1,x,y);
    int mn = 400;
    for(int i=0;i<n;i++){
       mn = min(mn,dp[i]);
    }
    if(mn==400){
        cout << -1;
    }else{
        cout << mn;
    }
}

int main(){
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ; cout.tie(0) ;
    cout.precision(20);
    

 
   int T=1; //cin>>T;
    while(T--){
        solve();
        if(T)cout << endl;
    }
    return 0;
}

I immediately related to Xenia and tree the moment I read problem G. Kudos to the authors for a really educative problem.

How to solve Problem G?

I feel like E is a little easier than D, because I think D is related to DP while E is related to brute-force.

After some observations, you can figure out the solution to E, but for a beginner coder like me, I just couldn't figure out a way to solve D.

Even though I didn't solve E in time, I still feel happy that it's at least solved in the end.

Here's my video during the contest.

Pretty boring, expected better from an ABC round :/

Alternate solution to $$$G$$$: We keep a bucket of size $$$\leq \sqrt{M}$$$ that stores {vertex, update_value} pairs that we haven't updated in the graph yet. When the size of this bucket becomes $$$\sqrt{M}$$$, then we iterate through every element in it and update the whole graph correspondingly. When we add a new vertex to the bucket, then search through each element in the bucket and find its updated value based on that. Total time complexity should be $$$O(N + Q\sqrt{M})$$$ or something, but my code is still TLEing on some cases. Is it because of using ordered_set?