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.

Plz dont organise contest by Denso hereafter. Bring Back Suntory contests.

If I still can't solve till I open problem D, I may really cry.

GL & HF

Hope E.

Are there any Chinese?

qpqp

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

B and C were bad, and I am surprised to see those many submissions on them. I really feel the dumbest.

D cooked me ,time to focus on implementation

how to solve d?

how to do f?

luck for me,is can be ac! (problem D)

#include <bits/stdc++.h>
#define pii pair<int, int>
#define int long long
#define rep(i, j, n) for (int i = (int)(j); i <= (int)(n); i++)
#define endl '\n'
using namespace std;
const int Mod = 1e9 + 7;
inline int add(int a, const int &b){ a += b &mdash; Mod; a += (a>>31) & Mod; return a; }
inline void usub(int &a, const int &b){ a -= b; a += (a>>31) & Mod; }
inline int sub(int a, const int &b){ a -= b, a += (a>>31) & Mod; return a; }
inline void umul(int &a, const int &b){ a = (int)(1ll * a * b % Mod); }
inline int mul(const int &a, const int &b){ return (int)(1ll * a * b % Mod); }
int qpow(int b, int p){ int ret = 1; while(p){ if(p & 1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
// priority_queue<pii, vector<pii>, less<pii>> q;
char c[20],c1[20];
int n;
int aws=100000000000000000;
int vis[20];
bool j(){
	rep(i,1,n){
		if(c[i]!=c1[i]){
			return false;
		}
	}
	return true;
}
void dfs(int p,int lay){
	if(j()){
		aws=min(aws,lay);
	}
	if(lay>8){
		return;
	}
	rep(i,lay-1,n-1){
		if(c[i]!='.'&&c[i+1]!='.'&&vis[i]==0){
			swap(c[i],c[p]);
			swap(c[i+1],c[p+1]);
			vis[i]=1;
			dfs(i,lay+1);
			vis[i]=0;
			swap(c[i],c[p]);
			swap(c[i+1],c[p+1]);
		}
	}
}
void solve() {
	cin>>n;
	int ct1=0,ct2=0,ct3=0,ct4=0;
	rep(i,1,n){
		cin>>c[i];
		ct1+=(c[i]=='B');
		ct2+=(c[i]=='W');
	}
	rep(i,1,n){
		cin>>c1[i];
		ct3+=(c1[i]=='B');
		ct4+=(c1[i]=='W');
	}
	if(ct1==ct3&&ct2==ct4){
		n++;
		c[n]='.';
		c1[n]='.';
		n++;
		c[n]='.';
		c1[n]='.';
		dfs(n-1,0);
		cout<<(aws == 100000000000000000 ? -1:aws);
	}
	else{
		cout<<-1;
	}
}
int32_t main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// int t;
// cin >> t;
// while (t--){
	solve();
//}
	return 0;
}
//

What is wrong with this solution in C?

#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <iostream>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define all(x) x.begin(),x.end()
using namespace std;
void paveway(){
    long long n , k; cin >> n >> k; vector<long long> a(n); 
    long long mn = 10000000000 , mx = -10000000000;
    for(long long i = 0; i < n; i++) cin >> a[i];
    sort(all(a));
    if(!( k %  2)){
        for(ll i = (k / 2)-1; i < (n - (i + 1)); i++){
            mn = min(mn , a[i]);
            mx = max(mx , a[i]);
        }
        cout << mx - mn << endl ;
    }else{
        for(long long i = (k/2)+1;i < (n - ((k/2))); i++){
            mn = min(mn , a[i]);
            mx = max(mx , a[i]);
        }
        cout << mx - mn << endl;
    }
}
int main (){ 
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	long long t = 1;
	//long long t; cin >> t;
	for(;t--;)
	paveway();
return 0;
}

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

The problem F is an original problem.A lot of people do it.

Solved ABCF, D and E were harder than F

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

can anyone please help me with this: https://atcoder.jp/contests/abc361/submissions/55314240? I'm getting WA on two tests, even though my code passed for 1 and 1e18

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

This is the code for question B, only one test point did not pass. Can anyone provide me with a set of hack data?

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <stack>

#define endl "\n"
typedef long long LL;

using std::cin;
using std::cout;
using std::getline;

using std::max;
using std::min;
using std::sort;

using std::vector;
using std::string;
using std::stringstream;
using std::queue;
using std::priority_queue;
using std::map;
using std::stack;

struct Node {
    int x, y, z;
};

vector<Node> pii;

int main() {
    int x, y, z, a, b, c;
    int xx, yy, zz, aa, bb, cc;
    cin >> x >> y >> z >> a >> b >> c;
    xx = x;
    yy = y;
    zz = z;
    aa = a;
    bb = b;
    cc = c;
    pii.push_back({x, y, z});
    pii.push_back({a, y, z});
    pii.push_back({x, y, c});
    pii.push_back({a, y, c});
    pii.push_back({a, b, c});
    pii.push_back({x, b, c});
    pii.push_back({x, b, z});
    pii.push_back({a, b, z});
    cin >> x >> y >> z >> a >> b >> c;
    pii.push_back({x, y, z});
    pii.push_back({a, y, z});
    pii.push_back({x, y, c});
    pii.push_back({a, y, c});
    pii.push_back({a, b, c});
    pii.push_back({x, b, c});
    pii.push_back({x, b, z});
    pii.push_back({a, b, z});
    bool ok = false;
    if (a == aa && b == bb && c == cc && x == xx && y == yy && z == zz) ok = true;
    int cccc = 0;
    for (int i = 0; i < 8; i ++) {
        Node now = pii[i];
        if (now.x > min(x, a) && now.x < max(x, a) && now.y > min(y, b) && now.y < max(y, b) && now.z > min(z, c) && now.z < max(z, c)) {
            ok = true; 
        }
    }
    if ((xx < a && yy < b && zz < c && aa >= a && bb >= b && cc >= c) || (x < aa && y < bb && z < cc && a >= aa && b >= bb && c >= cc)) ok = true;
    x = xx;
    y = yy;
    z = zz;
    a = aa;
    b = bb;
    c = cc;
    for (int i = 8; i < 16; i ++) {
        Node now = pii[i];
        if (now.x > min(x, a) && now.x < max(x, a) && now.y > min(y, b) && now.y < max(y, b) && now.z > min(z, c) && now.z < max(z, c)) {
            ok = true; 
        }
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

/*

*/

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.

Lol, I didn't expect this to work, but F is brute force!

F Brute Force

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

E is this problem

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?

I don't know why Atcoder promotes its contests within Codeforce

#include <bits/stdc++.h>
using namespace std;
const int N = 1e9 + 5;

#ifndef ONLINE_JUDGE
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void dfs(int u, int parent, vector<pair<int, int>> adj[], vector<int>& dist, vector<long long>& weight) {
    for(auto& pair : adj[u]) {
        int child = pair.first;
        int wt = pair.second;
        if(child == parent) {
            continue;
        }
        dist[child] = dist[u] + 1;
        weight[child] = weight[u] + wt;
        dfs(child, u, adj, dist, weight);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<pair<int, int>> adj[n + 1];
        long long totalWeight = 0;
        for(int i = 0; i < n - 1; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
            totalWeight += w;
        }
        vector<int> dist(n + 1);
        vector<long long> weight(n + 1);
        dfs(1, -1, adj, dist, weight);
        int oneEnd = -1; 
        long long mxDist = -1;
        for(int i = 1; i <= n; i++) {
            mxDist = max(mxDist, dist[i]);
        }
        int mxWeight = -1;
        for(int i = 1; i <= n; i++) {
            if(mxDist == dist[i]) {
                if(weight[i] > mxWeight) {
                    oneEnd = i;
                    mxWeight = weight[i];
                }
            }
        }
        fill(weight.begin(), weight.end(), 0);
        dfs(oneEnd, -1, adj, dist, weight);
        mxWeight = -1;
        for(int i = 1; i <= n; i++) {
            mxWeight = max(mxWeight, weight[i]);
        }
        cout << (long long)(2 * totalWeight - mxWeight) << "\n";
    }
    return 0;
}

Probelm: E I dont know why is this failing for 7 test cases. Can anyone please help...