I don't know why I was accidentally added to the polygon of this contest before it started, but luckily I have retired, so it doesn't affect me much.

very interesting

StO

E2 is amazing!

no dp[i] stores the min number of balls that can be kept.

The solution is that we can construct the sets $$$s_1,s_2,s_3,...,s_k$$$, such that $$$s_i\subset s_{i+1}$$$.

So we only care about when each element is added to the set.

refer to the standard solution for better understanding

Orz

We can save the min $$$dp_j$$$ such that $$$a_{j+1}=x$$$ for all x.

If we keep the $$$i-th$$$ ball , then the value is $$$dp(i−1)+1$$$.

If we erase $$$(j+1,j+2,j+3,...,i)-th$$$ bals , then the value is $$$\min\{dp(j)|a[j+1]=a[i],j+1 \lt i\}$$$.

On the announcement

If x|y != x , then y has a bit that x doesn’t have

Because if we pick the correct centroid the answer is correct

Thanks for your feedback!

Asuka Orz

Do I get TON

Thanks!

How to solve B

orz

Is 0:35 too late for sleeping ? (Seems like a lot of Chinese people go to sleep after 0:00 , you can try to take a nap at noon to avoid drowsiness)

I solved D using a simple dfs . But the time complexity may be wrong .

https://atcoder.jp/contests/arc155/submissions/38465395

He_Ren orz

I don't think he's finished writing it, it might just be part of it :)

The problems are good .

F1 is is brute force . You can implement it with map in O(nlog^2n).

It's all about comparing the number of people who write B wrongly in their room.

About Problem J :

I think MikeMirzayanov can find out the person abusing coach mode .

I hope there will be no anime in the problem description.

Why the mirror is delayed ?

Fixed now!

How can I participate the mirror . Why it said "There's no active contest for you (yet)." ?

Receive it now !

I hope Div1 D will be harder next time .

I haven't received :(

Hello , why it says "compilation error!!!" when only warnings exist .

When will the rating be updated?

That is common in China :(

This is a private online judge.

But if there is no evidence that the problem was intentionally copied, the round is unlikely to be unrated .

On question F, I mistakenly thought that 1 is also a prime number, and I didn't have time to revise it in the end.

I haven't received any message from Huawei , how do I claim my prize?

Problem F is a good problem!

Problem E is very boring and complicated to implement.

Many people used random solution.So it will be unfair to people with fewer submissions.

What does the question mark in the leaderboard mean?

How to get my prize?

Choose one spanning tree of the graph , and do some greedy solution on the tree.

When will the system test start？

Can this submission for problem F be hacked?

Can this submission for problem F be hacked?

I wish MikeMirzayanov could solve this issue .

Why the submissions were rejudged?

This is not final test data.

https://codeforces.me/blog/entry/106586?#comment-950389

FST now :(

I mean the connected components formed by same color.

Random algorithm .

By the way , The $$$O(n\times \sqrt{nlog_2n})$$$ solution may be easier to implement.

The connected components are trees.

Problem F is boring and hard to implement :(

Is problem E a famous problem ? djq_fpc solved it in 10min ...

Amazing approach.

By the way, after I observe your recurrence I think there is a more simple way to explain it .

Let F[A][B][C] be the answer of "a=A,b=B,c=C". Then consider add a character after the current string , ignoring the influence of the last three characters F[A][B][C] can be written as F[A-1][B][C]+F[A][B-1][C]+F[A][B][C-1] .

But you need to subtract the cases that last three characters are "abc"/"bca"/"cab" and these string has never appeared in all but the last three.

If A=B=C=1 ,then you need to subtract 3.

If A+B+C>3 then the restriction is "The fourth-to-last character cannot be the third-to-last character -1" , there are two possibilities to choose the third-to-last character . So you need to subtract F[A-1][B-1][C-1]*2.

Thanks :)

A different solution to Div1 D:

$$$Construct(L,R)$$$ is a function that finds the edges in the component of [L,R] ([L,R] is connected).

You can construct as follows:

Let $$$z$$$ be the largest number satisfies $$$z \lt R$$$ and $$$[L,z]$$$ is connected.

Let $$$x$$$ be the largest number satisfies $$$x\leq z$$$ and $$$[x,R]$$$ is connected.

There is a useful property :

• There is no segment $$$[l',r'],(l'\in [L,z],r'\in (z,R))$$$ that is connected.

Then if you construct $$$[L,z]$$$ first , the only influence to $$$[L,R]$$$ are the segments $$$[y,R],(L\leq y\leq z)$$$

If $$$[z+1,R]$$$ is connected then the rest of construction is easy:

1. $$$Construct[z+1,R]$$$
2. Connect $$$R$$$ and $$$x$$$

If $$$[z+1,R]$$$ is not connected . Then $$$[z+1,R]$$$ can be split into some connected components $$$[l_1,r_1],[l_2,r_2]...[l_k,r_k],[l_{k+1},r_{k+1}]$$$.

The solution is also not hard:

1. $$$Construct[l_i,r_i]$$$ for every $$$i$$$.

2. Connect $$$r_1,r_2,r_3...r_{k-1}$$$ and $$$R$$$.

3. Connect $$$r_k$$$ and $$$x$$$.

4. Connect $$$R$$$ and $$$x$$$.

In fact the last two part can be implemented together.Submission: 165734051

F can be solved with "Entropy" (https://en.wikipedia.org/wiki/Entropy_(information_theory)) .

You can split the positions into some groups , and each group includes at most B elements .

You find the positions of 'F' of each group independently , and use Entropy to find the optimal choice . which can be solved in $$$O(2^{2B})$$$ for each group .

Solution: 164420897 ,(B=12, and the number of queries is about 520 for n=1000).

My solution to F:

F is two sat . You can make some variable : (a[i]<=x) is true or false , (a[i]>=x) is true or false.

Why the number of possible numbers is $$$O(n+a_n)$$$?

Pretests for D are very weak .

Maybe you will receive an email after removing the cheaters.

Yes

P2 :

First , you need to calculate the scc of the graph. (If one scc has only one vertex , then it is impossible to win ).

Second , if there is a vertex whose out degree is 1 , then merge the vertex and the vertex it can go to .

Keep doing the second step until every vertex's out degree is not equal to 1.

Each query is to check whether u,v is the same vertex.

/**
 *    author:  gary
 *    created: 25.03.2022 21:43:48
**/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define rep(a,b) for(int a=0;a<b;++a)
#define LL long long
#define PB push_back
#define POB pop_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
const int MAXN=1e5+10;
vector<int> rg[MAXN],g[MAXN];
set<int> s[MAXN],rs[MAXN];
int n,m,vis[MAXN],ok[MAXN],fa[MAXN];
stack<int> sta;
void dfs1(int now){
    vis[now]=1;
    for(auto it:g[now]) if(!vis[it]) dfs1(it);
    sta.push(now);
}
void dfs2(int now,vector<int> &v){
    vis[now]=1;
    v.PB(now);
    for(auto it:rg[now]) if(!vis[it]) dfs2(it,v);
}
int root(int x){return fa[x]=(fa[x]==x? x:root(fa[x]));}
queue<int> q;
bool inq[MAXN];
int called[MAXN];
void domerge(int u,int v){
    rs[v].erase(u);
    if(rs[u].size()<rs[v].size()){
        for(auto it:rs[u]){
            rs[v].insert(it);
            s[it].erase(called[u]);
            s[it].insert(called[v]);
            if(s[it].size()==1&&!inq[it]) q.push(it);
        }
    }
    else{
        for(auto it:rs[v]){
            rs[u].insert(it);
            s[it].erase(called[v]);
            s[it].insert(called[u]);
            if(s[it].size()==1&&!inq[it]) q.push(it);
        }
        called[v]=called[u];
        rs[v].swap(rs[u]);
    }
    fa[u]=v;
}
int main(){
    scanf("%d%d",&n,&m);
    vector<mp> edge;
    rb(i,1,m){
        int u,v;
        scanf("%d%d",&u,&v);
        edge.PB(II(u,v));
        g[u].PB(v);
        rg[v].PB(u);
    }
    rb(i,1,n) if(!vis[i]) dfs1(i);
    memset(vis,0,sizeof(vis));
    while (!sta.empty()){
        int now=sta.top();
        sta.pop();
        if(!vis[now]){
            vector<int> comp;
            dfs2(now,comp);
            if(comp.size()>1){
                for(auto it:comp) ok[it]=1;
            }
        }
    }
    rb(i,1,n) if(ok[i]) q.push(i);
    while (!q.empty()){
        int now=q.front();
        q.pop();
        for(auto it:rg[now]) if(!ok[it]) ok[it]=1,q.push(it);
    }
    for(auto it:edge){
        int u,v;
        tie(u,v)=it;
        if(ok[u]&&ok[v]){
            s[u].insert(v);
            rs[v].insert(u);
        }
    }
    rb(i,1,n) fa[i]=i,called[i]=i;
    rb(i,1,n) if(s[i].size()==1) inq[i]=1,q.push(i);
    while (!q.empty()){
        int now=q.front();
        inq[now]=0;
        q.pop();
        if(root(now)!=now) continue;
        if(s[now].size()==1&&root(now)!=root(*s[now].begin())) domerge(root(now),root(*s[now].begin()));
    }
    int Q;
    scanf("%d",&Q);
    while (Q--){
        int u,v;
        scanf("%d%d",&u,&v);
        if(!ok[u]||!ok[v]) putchar('B');
        else if(root(u)==root(v)) putchar('B');
        else putchar('H');
    }
    putchar('\n');
    return 0;
}

The number of possible MST is at most n-1.

That is :

sort the sequence .

There is a number k :

for all i<=k, there is an edge (i,n) .

for all i>k ,there is an edge (1,i)

You can specify that the length of the path is exactly 40 or 39 by continuing moving up at the lca.

const int MAXN=2e5+50;
int n,l,h[MAXN],fa[MAXN];
LL prod[MAXN][41];
vector<int> g[MAXN];
void dfs(int now,int pre){
    fa[now]=pre;
    for(auto it:g[now]) if(it!=pre) dfs(it,now);
}
int main(){
    rep(i,MAXN) rep(j,41) prod[i][j]=1;
    scanf("%d%d",&n,&l);
    rb(i,1,n-1){
        int u,v;
        scanf("%d%d",&u,&v);
        u+=40;
        v+=40;
        g[u].PB(v);
        g[v].PB(u);
    }
    n+=40;
    rb(i,1,40){
        g[i].PB(i+1);
        g[i+1].PB(i);
    }
    rb(i,41,n) scanf("%d",&h[i]);
    dfs(1,0);
    int Q;
    scanf("%d",&Q);
    while (Q--)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1){
            int x,d,w;
            scanf("%d%d%d",&x,&d,&w);
            x+=40;
            d=40-d;
            while (d<=40&&x){
                (prod[x][d]*=w)%=l;
                x=fa[x];
                d++;
            }
        }
        else{
            int x;
            scanf("%d",&x);
            x+=40;
            LL p=h[x];
            int d=0;
            while (d<=40&&x){
                (p*=prod[x][40-d])%=l;
                if(d<=39)
                (p*=prod[x][39-d])%=l;
                x=fa[x];
                d++;
            }
            printf("%lld\n",p);
        }
    }
    return 0;
}

If the initial graph is a DAG or has no negative edge ,then the min cost flow can be solved in O(flow*N*log(n)) using Dijkstra. I think it is not rare in cp.

Both D and E are hard to implement .

I do the greedy solution from small to big , and create many useless values in the map . It can be $$$O(n\log^2n)$$$ in the worst case.

The pretests ....

Will you please explain it ?

You can find that when the pair (x,y) is optimal , only if $$$\forall_{x \lt i \lt y} w_i \gt max(w_x,w_y)$$$.

the number of such pair is $$$O(n)$$$.

I have a different solution to F (I'm not sure if it is correct):

Share my solution here :

Problem F is nice .

But I wrote the dfs order as index ,and debug for about 40 minute (how can this pass the first 12 tests ???).

And I found this silly mistake in the last 30 seconds ..

I only found this (in Chinese).

https://codeforces.me/contest/1630/problem/F

If you use a bitmask to maintain the young diagram . You can know the number of sequence which LIS is k (k<=m) in O(n2^m).

my solution: https://atcoder.jp/contests/abc237/submissions/28953647

Ex and div1f of last round are exactly the same problem.(After building the graph)

For problem E . It seems that many problem requiring finding a path to any node in the tree can be turned into find the path to the ending nodes of "diameter" of the tree (the diameter here can be the sum of length,max ...). And the ending nodes of diameter can be easily maintain by segment tree.

I first saw this trick here : https://codeforces.me/contest/1434/problem/D

An interesting thing is that I first read the statement wrongly . I mistakenly think we should work out the max of sum. I found it in the last 10 minutes when checking the example . So I changed some parts quickly, and have no time to make it faster.

I have another solution to C :

+1

And problem B seems to be hard to implement . I don't like this round :(

Problem A to D are too easy, especially Div1 D is much easier than usual .

And I have a O(nlog^2n) solution to E , but it got TLE . So Sad ...

I stuck in D for a long time ...

thanks .

AGC055E Set Merging by antontrygubO_o.

I am curious how can a human brain come up with such solutions ?

Yet another young LGM in China ,He_Ren orz.