If this ABC as shit as the last ABC, I will ban you.

it seems blogs of ABC get less and less upvotes even get downvotes.

upd: this round is worse than last one again.

Wish no more AI Best Contest plz.

painful

Why ABC G. is so hard?

Problem E is very similar to [POI 2009] Bytie-boy's Walk.

In POI, it shows us that E can be solved with time complexity $$$O(n^2V+nm)$$$. ($$$V=26$$$, $$$m$$$ is the number of edges).

Why this gives TLE for E in 2 test cases ?

vector<vector<vector<ll>>>helper(100, vector<vector<ll>>(26));
vector<vector<vector<ll>>>revHelper(100, vector<vector<ll>>(26));
vector<string>arr(100);
ll dp[101][101][209];

ll getMinLength(ll start,ll end,ll len){
    if(start==end){
        return 0;
    }
    if(arr[start][end]!='-'){
        return 1;
    }
    if(dp[start][end][len]!=-1){
        return dp[start][end][len];
    }
    ll ans = 1000;
    if(len>205){
        return ans;
    }
    for(char ch='a';ch<='z';++ch){
        for(ll start1:helper[start][ch-'a']){
            for(ll start2:revHelper[end][ch-'a']){
                ans = min(ans,2+getMinLength(start1,start2,len+2));
            }
        }
    }
    return dp[start][end][len] = ans;
}

void solve(bool printTestcase){
    ll n;
    cin>>n;
    for(ll i=0;i<n;++i){
        cin>>arr[i];
    }
    char ch;
    for(ll i=0;i<n;++i){
        for(ll j=0;j<n;++j){
            ch = arr[i][j];
            if(ch!='-'){
                helper[i][ch-'a'].push_back(j);
                revHelper[j][ch-'a'].push_back(i);
            }
        }
    }
    ll temp;
    memset(dp,-1,sizeof(dp));
    for(ll i=0;i<n;++i){
        for(ll j=0;j<n;++j){
            if(i==j){
                cout<<0<<" ";
                continue;
            }
            temp = getMinLength(i,j,0);
            if(temp>=1000){
                cout<<-1<<" ";
            }
            else{
                cout<<temp<<" ";
            }
        }
        cout<<endl;
    }
}           

How to solve E?

man how i do the c better than this ? Sorry my english is bad :(

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

typedef long long ll;

#define f first
#define s second

bool temWA(string str){
    for(int i = 0; i < str.length() - 1; i++){
        if(str[i] == 'W' && str[i+1] == 'A') return true;
    }

    return false;
}


int main(){
    string str; cin >> str;
    
    while(temWA(str)){
        for(int i = 0; i < str.length() - 1; i++){
        if(str[i] == 'W' && str[i+1] == 'A'){
            str[i] = 'A';
            str[i+1] = 'C';
        }
    }
    }

    cout << str << endl;
}

I don't know if problems like A and B should be even in a beginner contest! Atcoder became more reliant on speed more than anything else. Problem E was pain ngl

Anyone could please provide a testcase for my submissión for problem D? I failed just two cases :')

My submission

Thanks in advance

after contest i tried with o3-mini it solves E in one shot after giving my intuition. my TLE code : https://atcoder.jp/contests/abc394/submissions/63054891 o3-mini code: https://atcoder.jp/contests/abc394/submissions/63064525

today's problem set was nice but D was way more easier than C for me

Why is this wrong for F Alkane?

while (!q.empty())
{
    ll node = q.front();
    q.pop();
    component_size++;

    for (auto neighbor : adj[node])
    {
        if (!visited[neighbor])
        {
            visited[neighbor] = true;
            q.push(neighbor);
        }
    }
}
return component_size;

for (int i = 0; i < n - 1; i++)
{
    ll u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

vector<ll> degree(n + 1);
for (int i = 1; i <= n; i++)
{
    degree[i] = adj[i].size();
}

vector<ll> four, leaf;
for (int i = 1; i <= n; i++)
{
    if (degree[i] == 1)
    {
        leaf.push_back(i);
    }
    else if (degree[i] == 4)
    {
        four.push_back(i);
    }
    else
    {
        adj[i].clear();
    }
}

vector<bool> visited(n + 1, false);
ll ans = 0;

for (int i = 0; i <= four.size(); i++)
{
    if (!visited[i])
    {
        ll sizeofcomp = bfs(i, adj, visited);
        ans = max(ans, sizeofcomp);
    }
}
if(four.size()==0)
{
    cout << -1 << endl;
    return;
}
cout << ans << endl;

ll t=1;
while (t--)
{
    solve();
}
return 0;

The problems in ABC contests are becoming increasingly easier, making rankings largely dependent on the speed of coding.

e.g. slower 10 min will get nearly 1000 rank down

Me,too. Why is this wrong for F Alkane?

I use Tree dp and classification discussion，but WA;

Who can give me a sample ,or find my mistake.

Thanks!

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
vector<ll> v[200050];
ll du[200050];
vector<ll> st[200050];
map<ll,ll> mp[200050];
bool cmp(ll c,ll d)
{
	return c>d;
}
ll dfs(ll fa,ll now)
{
	if(mp[fa].count(now))
	{	
		return mp[fa][now];
	}
	if(du[now]>=4)
	{
		st[now].clear();
		for(ll it:v[now])
		{
			if(it!=fa)
			{
				ll k=dfs(now,it);
				st[now].push_back(k);
			}	
		}
		sort(st[now].begin(),st[now].end(),cmp);
		ll res=0;
		ll m=st[now].size();
		for(ll i=0;i<=m-1&&i<=3;i++)
		{
			res+=st[now][i];
		}
		return mp[fa][now]=res+1;
	}
	else
	{
		return mp[fa][now]=1;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin>>n;
	ll x,y;
	for(ll i=1;i<=n-1;i++)
	{
		cin>>x>>y;
		v[x].push_back(y);
		du[x]++;
		v[y].push_back(x);
		du[y]++;
	}
	ll maxx=-1;
	for(ll i=1;i<=n;i++)
	{
		if(du[i]>=4)
		{
			maxx=max(maxx,dfs(0,i));
		}
	}
	cout<<maxx;
	return 0;
}``

For Problem F: My code is working on 1-39 testcases, and WA on 40-59, please find error...

Your code here...
void dfs(ll x, vector<bool>& vis,vector<set<ll>>& graph,ll& c)
{
    c++;
    vis[x]=true;
    for(ll i:graph[x])
    {
        if(!vis[i])
        {
            dfs(i,vis,graph,c);
        }
    }
}

void solve()
{
    ll n;
    cin>>n;
    vector<set<ll>> num(n+1);
    for(ll i=1; i<n; i++)
    {
        ll a,b;
        cin>>a>>b;
        num[a].insert(b);
        num[b].insert(a);
    }

    queue<ll> q;
    for(ll i=1; i<=n; i++) if(num[i].size()==1) q.push(i);

    ll ans=0;

    while(!q.empty())
    {
        ll x = q.front();
        q.pop();
        ll p = *num[x].begin();
        ll s = num[p].size();
        if(s==1)
        {
            num[x].erase(p);
            num[p].erase(x);
        }else if(s==2)
        {
            num[x].erase(p);
            num[p].erase(x);
            q.push(p);
        }else if(s==3)
        {
            num[x].erase(p);
            num[p].erase(x);
        }else if(s>4)
        {
            num[x].erase(p);
            num[p].erase(x);
        }
    }
    vector<bool> vis(n+1,false);
    for(ll i=1; i<=n; i++)
    {
        if(num[i].size()==0) continue;
        else
        {
            ll c=0;
            dfs(i,vis,num,c);
            cout<<c<<"\n";
            return;
        }
    } 
    cout <<"-1\n";

} 

Problems suddenly got considerably hard starting from E. I breezed through A~D in 20 minutes, and spent 60 minutes to solve E.

How to solve G? I figured that the optimal route will pass through a floor f such that when considering only buildings with heights >=f, the source and destination would belong to same connected component.

To find this value of f for each query, I thought I could do a binary search but then maintaining the UnionFind structure would take O(N) per query, which is too slow. Another approach I thought of was to solve offline by adding each building one-by-one in decreasing order but then needing to check all Q queries after each addition is again too slow.

In ABC394 I played this match in the same room as CHI_LI I went to the toilet after making the E question He stole my code and made almost no changes Don't ban me I'm also a victim

G is not good. Extremely straightforward idea, but pain in the ass to implement, not what I expect from atcoder contests. Rest of the problems were alright tbh.

Is there some easier to understand solution for E compared to the editorial ?

Great contest. Could not solve E and F. Didn't even tried G but had fun. Problems are good. Thank you AtCoder team.

Hi can anyone tell me what is wrong in my F submission

I am trying to only consider the nodes whose degree>=4 and for these trees trying to calculate the number of nodes i can pick up so that all the nodes have degree <=4

https://atcoder.jp/contests/abc394/submissions/63070024

Can someone from the future tell me how to solve E and F