atcoder is top 8 contributer now!

After many many exams in the school, many many students begin their AtCoder tours again :)

Idk how I passed C after 4 WAs, just did some +/- math. Idea was to move diagonally as much as possible and align the x coordinate or y coordinate with the target node.

#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define pii pair<int,pi>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define cusrep(i,a,b,j) for(int i=a;i<b;i+=j)
#define rng(i,a,b) for(int i=a;i<b;i++)
#define rrng(i,a,b) for(int i=a;i>b;--i)
#define ar array

void run_case() {
  ll sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  ll alpha = min(abs(sx-tx), abs(sy-ty));
  ll nx = (sx>=tx) ? sx - alpha : sx + alpha;
  ll ny = (sy>=ty) ? sy - alpha : sy + alpha;

  if(ty%2==0){
      if(abs(tx)%2!=0){
        --tx;
      }
    } else {
      if(abs(tx)%2==0){
        --tx;
      }
  }
  if(sy!=ty){
    if(ty%2==0){
      if(abs(nx)%2!=0){
        --nx;
      }
    } else {
      if(abs(nx)%2==0){
        --nx;
      }
    }
  }
  ll ans = alpha + (1LL*abs(nx - (tx))/2LL) + 1LL*abs(ny - ty);
  cout << ans << "\n";
}
 
int main() {
  fast;
  int t = 1;
  while(t--){
    run_case();
  }
}

what the fck was C

Is there a simpler solution to G than Small to Large merging? Or did people just manage to implement that approach in like 5 mins @_@

can someone please explain the idea behind the 3rd question import math a,b=map(int,input().split()) c,d=map(int,input().split()) t=math.ceil(1.5*abs(b-d))

if t<=abs(a-c) and t!=0: print(int(abs(a-c) -1.5*abs(b-d))//2 + abs(b-d)+1) else: a=abs(b-d) print(a) please explain me why my code is incorrect please

My solution for problem-D is to store last K characters as state. AC

Great contest. D was a really good problem, wish I would've solved E a bit quicker though. Also, How to do C?

how can we get atcoder contest testcase at which our solution got failed...

Anybody who found C,D tougher than E,F or just me?

Solved ABDEFG. So strange.

Anyone can give hints on how to solve D?.

My approach to count all the possibilities such there is atleast 1 subarray of K length that is a palindrome and then the subtract that from 2^q and get the answer, but I couldn't calculate it properly(due to overcounting).

I think problem B's statement could have been made a lot easier to understand.

My code failed for last three testcases in C.Can someone point out where the mistake lies?

ll sx,sy;
cin>>sx>>sy;

ll tx,ty;
cin>>tx>>ty;



ll ans=(abs(ty-sy));

ans+=(max(0LL,((abs(sx-tx)-(abs(ty-sy))))/2));


cout<<ans<<endl;

"Can anyone explain C, please? I should have at least tried d, as I've spent so much time with C, actually, not so much time but significant time. I'm feeling bad about it now."

D is good.

I used small to large in G. But I can't understand what's wrong in my solution. mp[v][c] contains two numbers: the number of vertices of color c in v's subtree and the total length of paths to them.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#pragma GCC optimize("unroll-loops,O3")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define cok cout << (ok ? "YES\n" : "NO\n");
#define dbg(x) cout << (#x) << ": " << x << endl;
#define dbga(x,l,r) cout << (#x) << ": "; for (int ii=l;ii<r;ii++) cout << x[ii] << " "; cout << endl;
#define int long long
#define pi pair<int, int>
const int N = 1e6+9;
int n, ans, a[N], sz[N];
vector<int> vec[N];
map<int, pi> *mp[N];
int add[N];
void dfs(int v, int p = -1) {
    sz[v] = 1;
    pi mx = {-1, -1};
    for (int u: vec[v]) {
        if (u == p) continue;
        dfs(u, v);
        sz[v] += sz[u];
        mx = max(mx, pi{sz[u], u});
    }
    if (mx.se == -1) {
        mp[v] = new map<int, pi>;
        (*mp[v])[a[v]] = {1, 0};
        return;
    }
    mp[v] = mp[mx.se];
    add[v] = add[mx.se] + 1;
    ans += (*mp[v])[a[v]].se + (*mp[v])[a[v]].fi * add[v];
    (*mp[v])[a[v]].fi++;
    (*mp[v])[a[v]].se -= add[v];
    for (int u: vec[v]) {
        if (u == mx.se || u == p) continue;
        for (auto [color, para]: *mp[u]) {
            ans += ((*mp[v])[color].se + (*mp[v])[color].fi * add[v]) * para.fi + (para.se + para.fi * (add[u] + 1)) * (*mp[v])[a[v]].fi;
        }
        for (auto [color, para]: *mp[u]) {
            (*mp[v])[color].fi += para.fi;
            (*mp[v])[color].se += para.se + para.fi * add[u] - para.fi * add[v];
        }
    }
}
signed main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        vec[a].pb(b);
        vec[b].pb(a);
    }
    for (int i = 0; i < n; i++) cin >> a[i];
    dfs(0);
    cout << ans;
}

UPD: submission

UPD2: I found issue, AC

If C has a million haters I'm one of them. If C has a hundred haters I'm one of them. If C has one hater it's me. If C has zero haters I have died. If the world is against C I am with the world, if the world is for C I am against the world.

E was stack and $$$\text{O(N)}$$$ ? (Asking cuz constraints had 2e5)

void solve() {
    int n;
    cin >> n;
    vector<int> h(n), dif(n);
    inc(i, n) cin >> h[i];
    stack<pair<int, int> > st;
    st.push({1e9 + 1, 0});
    inc(i, n){
        auto val = st.top().first;
        if(val < h[i]){
            while(val < h[i]){
                st.pop();
                val = st.top().first;
            }
        }
        dif[i] = st.top().second;
        st.push({h[i], i+1});
    }

    vector<ll> final(n + 1);
    for(int i = 1; i<=n; ++i){
        final[i] = final[dif[i-1]] + (1LL*h[i-1]*(i - dif[i-1]));
    }

    for(int i = 1; i<=n; ++i) cout << final[i] + 1 << " ";
    cout << "\n";
    return;
}

So typical problem G. Maybe it will be better to swap some orders of the problem.

Could you guys just STOP making "greedy in grid" problems such as C plz? :(

how can we get atcoder contest testcase at which our solution got failed...

https://www.luogu.com.cn/problem/P7840

this is the original problem of F?

This problem is same as F!

C was exactly same as https://codeforces.me/contest/1421/problem/D. Just consider the right point of tiles (moving between left and right didn't encounter any cost), and those right points forms the hexagon.

It can be solved via linear algebra, no need to go into greedy

Problem F has appeared here previously : https://www.luogu.com.cn/problem/P7840

However, Luogu is a website that currently mainly used in China. So I think it is a coincidence. I only point out for notice.

Here is the translation by Copilot:

• There are $$$n$$$ servers.
• Each server has a busyness level denoted by $$$v_i$$$.
• The servers are connected using $$$n−1$$$ network links.
• Each server has a connection count $$$d_i$$$.

The total running time of the server network is given by the expression:

The goal is to minimize this value.

Didn't Atcoder check for if there have been the same problem？？？

This problem from Luogu same as today's G.

And this problem is from the year 2021.

Why inclusive-exclusive algorithm doesn't work in problem D?

Top 10 contribution!

I wonder how to prove that greedy algorithm is correct for problem F. Would anyone like to share your ideas? Thanks a lot.

I see some solutions using Small to Large technique, so I'd like to share 5 problems (in increasing order of difficulty) for someone who is not familiar with this topic and want to learn it.

Plain Small to Large

1. Distinct Colors
2. Confuzzle
3. It is a Tree : Subtask 2

Small to Large + Advanced DP

1. Count Paths
2. Leaf Color

For problems from BOJ, either use Google Translate or add the problem to Vjudge and use the inbuilt translator option.

In conclusion,

C : https://codeforces.me/contest/1421/problem/D

D : https://onlinejudge.org/external/16/p1633.pdf

F : https://www.luogu.com.cn/problem/P7840

G : https://www.luogu.com.cn/problem/P4103

what can I say

Can anyone explain Problem G ?