Loved problem D （＾－＾）

Honestly, that A and B where worst problems I ever had on atcoder. Abc is supposed to be constest for beginner partitipants, not beginner problem setters.

I am disapointed because quality of atcoder contests was very good before.

I would recommend whoever wrote B to consider never problemsetting again.

E and F were fun though.

Found problem B harder than E. Maybe I need to pickup my high school mathsbook again.

A: Statement is so hard to understand. Bruh

B: Why is this a problem???

C: Decent

D: Repeated problem but now with gEomeTRy

TLDR: This is actually WaCoder. The first half of problemset is shit

I used bfs but 6 testcase are failing is it due to overflow im not getting idea?? Plzz help

vector<int>v[3001];
bool vis[3001];
ull distance(int x1, int y1, int x2, int y2){
    return pow(x2 - x1, 2) + pow(y2 - y1, 2);
}
bool bfs(ull sp,ull ep){
    if(sp==ep)return true;
    queue<ull>q;
    q.push(sp);
    vis[sp]=true;
    while(!q.empty()){
        ull x = q.front();
        q.pop();
        for(auto y:v[x]){
            if(y==ep){
                return true;
            }
            if(!vis[y]){
                q.push(y);
                vis[y]=true;
            }
        }
    }
    return false;
}
void solve(){
    int n;
    cin>>n;
    ull sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    vector<vector<ull>>p(n+1);
    for(int i=1;i<=n;i++){
        ull x,y,r;
        cin>>x>>y>>r;
        p[i]={x,y,r};
    }
    int sp = -1;
    for(int i=1;i<=n;i++){
        if((p[i][0]-sx)*(p[i][0]-sx) + (p[i][1]-sy)*(p[i][1]-sy)+0ULL==p[i][2]*p[i][2]+0ULL){
            sp=i;
        }
    }
    if(sp==-1){
        cout<<"No\n";
        return;
    }
    int ep = -1;
    for(int i=1;i<=n;i++){
        if((p[i][0]-tx)*(p[i][0]-tx) + (p[i][1]-ty)*(p[i][1]-ty)+0ULL==p[i][2]*p[i][2]+0ULL){
            ep=i;
        }
    }
    if(ep==-1){
        cout<<"No\n";
        return;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ull dis = distance(p[i][0],p[i][1],p[j][0],p[j][1]);
            ull d1 = (p[i][2]-p[j][2])*(p[i][2]-p[j][2]);
            ull d2 = (p[i][2]+p[j][2])*(p[i][2]+p[j][2]);
            if(d1<dis && dis<d2){
                v[i].push_back(j);
                v[j].push_back(i);
            }
            else if(d1==dis){
                v[i].push_back(j);
                v[j].push_back(i);
            }else if(d2==dis){
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    memset(vis,0,sizeof(vis));
    // cout<<sp<<" "<<ep<<endl;
    // for(int i=1;i<=n;i++){
    //     cout<<i<<" ";
    //     for(auto x:v[i]){
    //         cout<<x<<" ";
    //     }
    //     cout<<endl;
    // }
    if(bfs(sp,ep)){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    //1.Check whether those points lie on any circle..
    //check whether circles intersect or not..
    //graph problem there is egde between intersecting circle
    //find whether path exist between sx,sy,tx,ty
}

problem E can solved with divide and conquer + hashing. code

In editorial of problem G:

Shouldn't it be?:

Also, I don't really understand why solution works :(

To be more precise, I don't understand why do we add edge from:

Sorry but according to this post in Chinese(You don't have to understand Chinese but just see the code), GREEDY ALGORITHM can pass problem G, and there's just a hack data below.

Well if you can't see the code and the hack data, here I will copy it :

int main() {
    qread(n, m);
    rep(i, 1, n) rep(j, 1, m) qread(a[i][j]);

    rep(i, 1, n) {
        ll sum = 0;
        rep(j, 1, m) sum += a[i][j];
        if(sum > 0) ans1 += sum, v[i] = 1; 
    }
    rep(i, 1, m) {
        ll sum = 0;
        rep(j, 1, n) if(v[j] && a[j][i] < 0) {
            sum = -1;
            break;
        }
        else if(!v[j]) sum += a[j][i];
        if(sum > 0) ans1 += sum;
    }

    memset(v, 0, sizeof v);

    rep(j, 1, m) {
        ll sum = 0;
        rep(i, 1, n) sum += a[i][j];
        if(sum > 0) ans2 += sum, v[j] = 1; 
    }
    rep(i, 1, n) {
        ll sum = 0;
        rep(j, 1, m) if(v[j] && a[i][j] < 0) {
            sum = -1;
            break;
        }
        else if(!v[j]) sum += a[i][j];
        if(sum > 0) ans2 += sum;
    }

    cout << max(ans1, ans2) << '\n';
    return 0;
}

4 4
-1 -1 100 100
-1 100 100 100
100 100 -1000 -1000
100 100 -1000 -1000

Out of all problems from A to E, I think only C,D were Decent

For problem F, my first idea is based on greedy algorithm (inspired by Kruskal's algorithm), i.e., sort edges in decreasing order of weight, and choose from large ones to small ones as long as the "rule of degree" is not broken. But, I really wonder why this does not work? What are the counter-examples?

By the way (I am sorry that this is off topic), I find KrK in the standings!!! I am sorry to disturb you here, but you are really a legend!! During past years, I kept practicing by virtual participation in codeforces, and I usually saw you in standings, and witness your persistence and improvement. Early codeforces rounds usually do not have detailed tutorials, and it is difficult for me to understand for most of the time. During that tough period, I learned a lot by reading your solutions. The codes are clean, simple, and it helps me understand the idea behind the solution quite a lot. I am very glad to attend a true contest with you this time.

Can anyone give me any test case for problem C that fails in my submission. My approach seems similar to the official editorial.

This contest made me learn new functions like sqrtl, cosl, sinf, tan2 and other due to lack of accuracy. I've never had so many WAs during contests. Hope there will be less such problems, or at least not at that positions.

Solving today's contest reminded me of my JEE days :)

Typo?

1. ca*m* be chosen at most d_v times. 

Editorial of F, Line 13

plz fix it thx :)