AtCoder Beginner Contest 352 Announcement

6 месяцев назад, # |

← Rev. 3 →

-8

Can anyone help me why I am getting WA on 2 testcases for this solution of F?

→ Ответить

KrVivk4

6 месяцев назад, # ^ |

-12

hey aryanc403, Im eagerly waiting for your youtube video discussion. those are great. When will it come today

→ Ответить

6 месяцев назад, # ^ |

-8

You can find my solution ideas in this linkedin blog

→ Ответить

TrendBattles

6 месяцев назад, # ^ |

← Rev. 2 →

I have an AC submission here, you can use this to generate counter tests. https://atcoder.jp/contests/abc352/submissions/53146457

→ Ответить

TAoz1

6 месяцев назад, # ^ |

On line 181 of your latest submission, the return value of this function is a boolean, but you write return ans. While ans here is either tr or fal and both of them are positive integers, so the real return value is always true. I just changed this and got Accepted.

→ Ответить

https://atcoder.jp/contests/abc352/submissions/53139365

6 месяцев назад, # ^ |

Nice catch. Thank You.
It would have taken me forever to debug this.

→ Ответить

lwenkai

6 месяцев назад, # |

← Rev. 3 →

Does anyone know why I am getting Runtime Error for this submission for D? Is there any issue with the DSU implementation ?

→ Ответить

red_one_fine_day

6 месяцев назад, # |

what's the idea behind F?

→ Ответить

6 месяцев назад, # |

← Rev. 3 →

-7

Hello! I'm just a mediocre problem setter who is wondering how to give many many many D&C NTT problems which has almost the same solution quickly. May Atcoder Beginner Contest help?

UPD: I don't know whether ironies are just unwelcomed in codeforces or it's not the right place to discuss a problem which has only 143 solves with many newbies? Please, tell me the reason if you decide to downvote me @_@.

UPD 2: Maybe next time I'll try "DCNTT in ABC G author's solution, are you retarded?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????".

→ Ответить

Clein.qwq

6 месяцев назад, # ^ |

← Rev. 3 →

+19

Of coz,ABC is a great way to improve your poly skill quickly.

UPD:In fact I agree with wyrqwq's opinion.I think he's not saying that D&C NTT problems are not good,but too many similar D&C NTT problems in ABC are not interesting.

→ Ответить

hashman

6 месяцев назад, # ^ |

+40

They are meant to be educational for beginners, as it says in the name. ARCs and AGCs are held to (much) higher standards.

→ Ответить

6 месяцев назад, # ^ |

I think it's not educational to put many tasks with a same algorithm again and again. It's just a sign of lack of responsibility and lack of time to polish a contest.

→ Ответить

oversolver

6 месяцев назад, # ^ |

← Rev. 2 →

probably you don't know that atcoder has acl and you can just call convolution in your solution without knowing what is ntt

→ Ответить

6 месяцев назад, # ^ |

That is indeed helpful during contest time. But that doesn't help me learn the algorithm itself. Am I just participating in ABC only for getting a higher rank?

→ Ответить

oversolver

6 месяцев назад, # ^ |

← Rev. 2 →

I am trying to understand your frustration. if author's solution used std::set / std::map how much author is retarded?

→ Ответить

6 месяцев назад, # ^ |

-21

Are you saying: if author's solution contains int main() how much author is retarded?

→ Ответить

oversolver

6 месяцев назад, # ^ |

please no puzzles just answer

→ Ответить

6 месяцев назад, # ^ |

-12

Am I not clear? If you don't have the ability to hold a good ABC round every week, hold it every two weeks. If you cannot educate beginners but just keep creating trashes, stop using the name "beginner contest" but "atcoder library contest". If you cannot come up with a different G-placed problem from NTTing, stop posting problems for Atcoder and leave the company. In reply to your question: std::set and std::map are STL containers, and you are sure to learn them long before you understand how a balanced search tree works.

→ Ответить

pkhaustov

6 месяцев назад, # ^ |

I'd rather agree with unpopular opinion of wyrqwq.

I completely don't understand the point of ACL. What is it designed for? I never use it and never will, because I try to improve or at least to keep up my coding skills, first of all. Also, for those who can still participate in official onsite contests, it is really harmful and, I suppose, many of real beginners will suffer from not being able to implement any specific variety of data structure adjusted to specific problem's requirements when they have no access to online resources and ACL. If they need to take a higher place and get more rating, that's completely their choice, although I don't really think it is quite educational.
As for the name "AtCoder Beginner Contest", it's really misleading. Despite being not really high-rated lately, I wouldn't call myself a beginner. However on average I solve only 6 problems out of 7. Actually, at least a couple of problems are tricky and educational in almost every round, and they genuinely require a certain effort from me. And normally problem-setters should at least try to avoid similar problem ideas in adjacent contests, which may not be the case for ABC, unfortunately. I think this what wyrqwq meant if to throw away the emotional wording.

→ Ответить

ibrahimwq

6 месяцев назад, # |

loved F, thank you for contest!

→ Ответить

theRealChainman

6 месяцев назад, # ^ |

What was the method for F? I was roughly trying to brute force on all non-trivial connected components, (each connected component of size > 1), because I knew 16! would be too slow, but 16 * 8! might pass.

→ Ответить

ibrahimwq

6 месяцев назад, # ^ |

Yes, you can actually do brute force, but instead of factorials think about placing components.

→ Ответить

electric_boogaloo

6 месяцев назад, # |

Solved D with a segtree

All I can see now are segment trees

→ Ответить

papa-ka-para

6 месяцев назад, # |

-10

"Yes" != ("YES" || "yes").

LOL, still case sensitive on output strings.

→ Ответить

surung9898

6 месяцев назад, # |

Randomized solution for F gave me some hope for a moment

→ Ответить

Abito

6 месяцев назад, # ^ |

what was your solution?

→ Ответить

llc5pg

6 месяцев назад, # |

For E, I forgot to handle this disconnected case:

Spoiler

My submission still gets AC, even though I didn't output -1 for the above case.

→ Ответить

6 месяцев назад, # |

Could someone help me debug E? I've been absolutely confused for the second part of the contest and still can't understand where the WA is coming from: https://atcoder.jp/contests/abc352/submissions/53123170

→ Ответить

6 месяцев назад, # ^ |

← Rev. 2 →

brother, iam doing the same, but still wa

Did you figured it out yet??

i looked at Ac code he used vector<pair<int,vector> E(M) and sort it.

aren't we doing the same thing using map(which automatically sort by first value)

→ Ответить

6 месяцев назад, # ^ |

i think i got why we are failing, because it stores only uniques values there might be some subset having same edges weight but different components, but our map is assuming it's a single components!!

→ Ответить

6 месяцев назад, # ^ |

← Rev. 4 →

Fails on following testcase.

Spoiler

Answer is -1 because graph is disconnected. You cannot directly merge all components with same cost.

→ Ответить

6 месяцев назад, # ^ |

← Rev. 2 →

Not sure i got what you mean, my code outputs -1: https://ideone.com/pnCDk1 I only merge when I'm taking a new edge into MST:

for (auto &[compCost, conComp]: edges) {
    int first = conComp[0];
    for (auto &vComp: conComp) {
        if (findSet(first) != findSet(vComp)) {
            totalCost += compCost;
            unionSets(first, vComp);
        }
    }
}

→ Ответить

6 месяцев назад, # ^ |

Ah, okay, i finally got it. The test case should probably be

or smth similar

→ Ответить

6 месяцев назад, # ^ |

Yes. I messed up with input format. https://ideone.com/TYhyXr

→ Ответить

6 месяцев назад, # ^ |

Yeah, looks completely ridiculous i haven't thought about it now. I was so focused on trying to find an error in my Kruskal's implementation i completely overlooked the fact map can merge a couple of cliques together. Thanks for the help!

→ Ответить

TrendBattles

6 месяцев назад, # ^ |

Try this one:

Spoiler

5 2
2 3
1 2 3
2 3 
3 4 5

//this should be 12

→ Ответить

Mendeke

6 месяцев назад, # |

Good luck !!!

→ Ответить

J.A.K.D.Z

6 месяцев назад, # |

Speedforces and Speedcoder :)

→ Ответить

6 месяцев назад, # |

← Rev. 2 →

E Submission

What's wrong here?

Spoiler

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int N = 2e6 + 10;

struct Dsu{
    vector<ll> parent, rank;
    ll sz;
    Dsu(ll n){
        sz = n;
        parent.resize(n+5); rank.resize(n+5, 1); iota(begin(parent), end(parent),0);
    }
    vector<ll> getparent() {return parent;}

    vector<ll> getrank() {return rank;}

    ll find(ll x){
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    void Union(ll x, ll y){
        x = find(x); y = find(y);
        if(x != y){
            if(rank[x] < rank[y])
                swap(x,y);
            rank[x] += rank[y];
            parent[y] = x;
        }
    }
    
    bool isConnected(ll x, ll y) {return find(x) == find(y);}

    ll Components(){
        ll ans = 0;
        for(ll i=1;i<=sz;i++) if(find(i) == i) ans++;
        return ans;
    }
};


int main() {
	int t;
    // cin >> t;
    t = 1;
    while(t--){
        int n, m;
        cin >> n >> m;
        map<ll, vector<ll>> M;
        for(ll i = 0; i < m; i++){
            ll k, c;
            cin >> k >> c;
            for(ll j = 0; j < k; j++){
                ll x;
                cin >> x;
                M[c].push_back(x);
            }
        }
        Dsu t = Dsu(N);
        ll sum = 0;
        for(auto [x, y]: M){
            vector<ll> cur = y;
            for(int i = 1; i < cur.size(); i++){
                if(!t.isConnected(cur[i - 1], cur[i])){
                    sum += x;
                    t.Union(cur[i - 1], cur[i]);
                }
            }
        }
        cout << (t.Components() > 1 ? -1 : sum) << '\n';
    }
}

→ Ответить

6 месяцев назад, # ^ |

← Rev. 4 →

Fails on following testcase.

Spoiler

Answer is -1 because graph is disconnected. You cannot directly merge all components with same cost.

→ Ответить

6 месяцев назад, # ^ |

Thanks, i have figured it out!!

→ Ответить