Contest Topic Predictions for ABC:

A will be brute force.

B,C and D will be a Graph/Segment Tree/Advanced DP Problem/BS on answers/Sweepline.

E,F and G will be advanced data structures, MST, ternary search, NP Hard and 3 SAT problem.

Are there any Chinese?

I couldn't solve problem B any more! Because my maths is terrible, I couldn't imagine those cubiods' location!

Is F a known problem? I was sure I'd find code for it somewhere online but could only find a paper on it.

This solution for F gives WA for 2 test cases,can anyone help?

This was a great contest, enjoyed all problems and this is my first time solving A-F. B was a bit annoying tho.

This contest was easier than usual, hmmm?

Oh my god

There is an original problem

My logic for E was as follows: The optimal path will start from a leaf and end at another leaf. Let's say the two optimal leaves are a and b, and their LCA (lowest common ancestor is) c, then all the edges in the tree will be traversed twice except the ones between a and c, and b and c. Hence we want to maximise the sum of those edges.

For this I iterated over all the vertices assuming them as LCA and found out the maximum value of highest depth. See my code for more details: https://atcoder.jp/contests/abc361/submissions/55306890

But I'm getting Wrong Answer on 5 test cases. Can anyone help me find out the issue here?

Update: Found the error. I needed to use multiset instead of set

D cooked me ,time to focus on implementation

how to solve d?

how to do f?

Why this time abc361 have a same problem with luogu(an oj in China)?

The same problem in luogu: https://www.luogu.com.cn/problem/P9118

There is a discuss in luogu recently: https://www.luogu.com.cn/discuss/845537

Is F based on Mobius Function? I believe F is Inclusion-Exclusion, but could not figure out which values to include/exclude in time.

There's an exactly same problem from the National Olympics in Informatics (Spring Contest, 2023) in China, even the samples are same (original sample #3->sample #1, original sample #4->sample #3). Is it a concidence?

https://www.luogu.com.cn/problem/P9118 You know that F is an known problem,but you don't know that this problem is a pro version of F.

Solved ABCD，problem B is funny

Is there an explanation as to why G isn't commonly included in official editorials?

I noticed a strange behaviour in c++ today while writing code for problem D. When I use & sign before "it" in the code, the output is some gibberish like "��q{xU"

    ll n = 16;
    string s = "BBBWBWWWBBWWBW..";
    queue<pair<ll,string>>q;
    q.push({n,s});
    while(!q.empty()){
        ll sz = q.size();
        while(sz--){
            auto &it = q.front();
            q.pop();
            ll pos = it.first;
            string str = it.second;
            cout<<"str = "<<str<<endl;
        }
    } 

But when I remove the & sign, I get the expected output "BBBWBWWWBBWWBW..". Can someone explain what is this and why is this happening ?

If anyone could tell me the idea for G that would be great. I tried the following:

First, we clearly just want to find all enclosed areas. Let pair<int, int> f[i] denote the coordinates of the i-th stone. Then, we connect a (bidirectional) edge from $$$u$$$ to $$$v$$$ if |f[u].first-f[v].first|<=1 and |f[u].second-f[v].second|<=1. Then, an enclosed area is analogous to a cycle in this graph. If we have a cycle $$$a_1, a_2, \dots, a_n$$$ in this graph, we can calculate the number of lattice points enclosed by the polygon formed by f[a[1]], f[a[2]], ..., f[a[n]] by using Pick's Theorem. We can calculate the area using shoelace and "reverse engineer" the number of lattice points enclosed by the polygon using Pick's Theorem. Summation of this should give us the answer.

This, however, is giving WA. If anyone could correct me, that would be greatly appreciated.

Many thanks to yuto1115 for sharing an amazing solution of G — Go Territory (*ˊᗜˋ*)/ᵗᑋᵃᐢᵏ ᵞᵒᵘ*

hey guys. how to solve F?

I got 2 WA on F, i am not sure whether it is not the correct solution or it is just the precision problem.

#include<bits/stdc++.h>

long long n;
int mem[10000002];

long long qp(long long p, long long q) {
	long long r = 1, b = p;
	while (q) {
		if (q & 1) r = r * b;
		b = b * b;
		q >>= 1;
	}
	return r;
}

long long f(long long x) {
	if (x == 0) return 0;
	if (x <= 1e7) {
		if (mem[x]) return mem[x];
	}
	long long res = 0;
	for (int i = 2; i <= 61; i ++) {
		
		long long l = floor(pow((long double)x, (long double)1.0 / i) + 1e-9);
		res += l - f(l);
	}res ++;
	if (x <= 1e7) mem[x] = res;
	return res;
}

signed main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0); std::cout.tie(0);
	mem[1] = 1;
	std::cin >> n;
	std::cout << f(n);
	return 0;
}

Is there any way to know what would their CF rating be?