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;
}

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

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.

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.

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

my submission

can someone hacks me with my submission? I first find all points with at least 4 degrees and use union-find set to find the maximum number with 4 degrees in the subgraph and then calculate the ans.

#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
using ll = long long;
using u64 = unsigned long long;
using ld = long double;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define fill(x, y) memset(x, y, sizeof(x))
#define si(x) ((int)(x).size())
#define dbg(x) cerr << #x << ": " << (x) << " "
#define debug(x) cerr << #x << ": " << (x) << endl

#define PI (ld)2 * acos(0.0)
#define MOD 998'244'353
#define MOD2 1'000'000'007

#define endl '\n'
#define YES cout << "YES" << endl; return
#define Yes cout << "Yes" << endl; return
#define yes cout << "yes" << endl; return
#define YE cout << "YES" << endl
#define Ye cout << "Yes" << endl
#define NO cout << "NO" << endl; return
#define No cout << "No" << endl; return
#define no cout << "no" << endl; return
#define IPSB cout << -1 << endl; return

const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;

#define int ll

class DSU {
  public:
	vector<int> parent, rank, size;

	DSU(int n) {
		parent.resize(n);
		rank.resize(n, 1);
		size.resize(n, 1);
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}

	int find(int x) {
		if (parent[x] != x) {
			parent[x] = find(parent[x]);
		}
		return parent[x];
	}

	void unite(int x, int y) {
		int xr = find(x), yr = find(y);
		if (xr == yr)
			return;
		if (rank[xr] > rank[yr]) {
			parent[yr] = xr;
			size[xr] += size[yr];
		} else if (rank[xr] < rank[yr]) {
			parent[xr] = yr;
			size[yr] += size[xr];
		} else {
			parent[yr] = xr;
			rank[xr]++;
			size[xr] += size[yr];
		}
	}

	int get_size(int x) {
		return size[find(x)];
	}
};

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

	vector<int> degree(N, 0);
	vector<pair<int, int>> edges;

	for (int i = 0; i < N - 1; i++) {
		int A, B;
		cin >> A >> B;
		A--;
		B--; // 0-based index
		edges.emplace_back(A, B);
		degree[A]++;
		degree[B]++;
	}

	vector<bool> is_high_degree(N, false);
	int flag = 0;
	for (int i = 0; i < N; i++) {
		if (degree[i] >= 4) {
			is_high_degree[i] = true;
			flag = 1;
		}
	}

	DSU dsu(N);
	bool has_cluster = false;

	for (auto [A, B] : edges) {
		if (is_high_degree[A] && is_high_degree[B]) {
			dsu.unite(A, B);
			has_cluster = true;
		}
	}

	if (!has_cluster) {
		if (flag == 0) {
			cout << -1 << endl;
		} else {
			cout << 5 << endl;
		}
	} else {
		int max_size = 1;
		map<int, int> component_size;
		for (int i = 0; i < N; i++) {
			if (is_high_degree[i]) {
				int root = dsu.find(i);
				component_size[root] = dsu.get_size(root);
				max_size = max(max_size, component_size[root]);
			}
		}
		int ans = max_size * 3 + 2;
		assert(ans <= N && max_size >= 2);
		cout << ans << endl;
	}

	return;
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
/*
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
*/
	int ttest = 1;
//	cin >> ttest;
	while (ttest--) {
		solve();
	}
//	cerr << "Time:" << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << " ms" << endl;
	return 0;
}

I think problem C is harder than problem D. Problem D is very easy.

Can someone please point out what's the problem with below logic of E.

Make a reversed graph of the original one. Run a multi-source BFS for each pair (i, j) on both G and reversed G. Move i to next_i following edge (i, next_i) in G and move j to next_j following edge (j, next_j) in reversed G when label of these two edges are the same. Once hitting i == j or C[i][j] != '-' means shortest path is found.