atcoder_official's blog

AtCoder Beginner Contest 352 Announcement
By atcoder_official, history, 7 months ago, In English

We will hold AtCoder Beginner Contest 352.

We are looking forward to your participation!

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Yay, hope to solve E and F.

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

GL&HF!

→ Reply
»
7 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Good Luck!Hope F!

→ Reply
»
7 months ago, # |
  Vote: I like it -15 Vote: I do not like it

GL&HR!

→ Reply
»
7 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Bad luck and low rating!

→ Reply
»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Good luck!- Hope to solve F and G.

→ Reply
»
7 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Hope to have good luck，and solve F and G! (But I know that's impossible LOL).

→ Reply
»
7 months ago, # |
  Vote: I like it -15 Vote: I do not like it

for problem E , what's the part of my solution that giving a TLE ? is it constructing the graph ??

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Yes. You don't need the whole graph.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you mean by not taking the whole graph? Does it mean omitting to take all edges we get for each K_i and C_i?

      → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    you can use dsu

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    You can sort first and not use the whole graph

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think Sum of K over all M is 10**5 as in the fourth line of the constraints.

    Constructing a undirected graph will be M squared which is 10**10 which will TLE

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you can use an algorithm similar to Kruskal's.

    You shouldn't use an algorithm with $$$n^2$$$, that may cost $$$100$$$ seconds.

    → Reply
»
7 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I don't understand. Why does my code WA on 4 testcases?

→ Reply
»
7 months ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

what's the idea behind F?

→ Reply
»
7 months ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

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?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????".

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 3   Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            please no puzzles just answer

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it -12 Vote: I do not like it

              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.

              → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        I'd rather agree with unpopular opinion of wyrqwq.

        1. 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.

        2. 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.

        → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

loved F, thank you for contest!

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved D with a segtree

All I can see now are segment trees

→ Reply
»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

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

LOL, still case sensitive on output strings.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Randomized solution for F gave me some hope for a moment

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!!

    → Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Fails on following testcase.

    Spoiler
    → Reply
    • »
      »
      »
      7 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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);
        }
    }
}
      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        5 2
3 2
1 2 3
2 2
4 5

        or smth similar

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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!

            → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Try this one:

        Spoiler
        → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck !!!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Speedforces and Speedcoder :)

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

E Submission

What's wrong here?

Spoiler
→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it

    Fails on following testcase.

    Spoiler
    → Reply
»
7 months ago, # |
  Vote: I like it +28 Vote: I do not like it

When you join the contest late by $$$5$$$ minutes and get $$$F$$$ accepted after the contest end by $$$4$$$ minutes:

→ Reply
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I would like to share my solution to problem F(taking me about 90 minutes to get accepted), as follows:

  1. Divide all the nodes(people) into several connected components, and suppose that there are cnt of them

  2. For each component, compute all the feasible rankings, and denote them based on bitmasks

  3. Use dp[i][j] to denote that, for the previous i components, whether we can achieve the state of j or not, and also use set last[i][j] to store the previous states that can reach j. Here, the state means the bitmask of rankings

  4. The final state should be (1<<n)-1, and we start from last[cnt][(1<<n)-1], and check whether the current state is unique or not. If it is unique, then we have unique rankings for the nodes within this component

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone figure out where i am going wrong in E. https://atcoder.jp/contests/abc352/submissions/53149749

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For this test case:

    Spoiler

    Answer should be -1, because node 6 is not connected. Your code does not output -1.

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a hint on how to optimize problem E?

I did understand the part where we could build a graph from all the given weights (using DSU) and then apply Kruskal to find the MST, but I saw the limits on K and understood this solution would result in TLE.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try using prims.

    → Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Recognize that some of the edges are redundant and use minimum spanning tree algorithm, kruskal or prims. For example on ignoring redundant edges, you only actually care about joining nodes into the minimum spanning tree if they are disjoint. And you can join all nodes to just a single node representative of a connected component.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      By redundant edges, do you mean multiple edges b/w (u, v)? How are you ignoring the redundant edges?

      My Approach: For every k_i and c_i, we can sort the k_i vertexes Then, there will be k_i * (k_i — 1) / 2 possible edges (u, v) with c_i weights

      In this k_i alone, we won't be getting any multiple edges, but in subsequent k_i, we can get (but for that also, we must do k_i * (k_i — 1)/2 to check which have been already done or not)

      Is there any better way to do this ? Above approach will also result in TLE, because there can be atmax N * (N-1) / 2 pairs of (u, v)

      → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with problem E? Why my code is giving wrong answer on some test cases, even though I have also used the same logic as most others. Submission

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

to solve $$$E$$$ do I need to learn any algorithm?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The button "Custom" is gone.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the logic behind the question c please also provide me the java code for it

→ Reply
»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

this contest was totally fixed and made me bored. abc352 is one of the boring contests ever. abc352 fixing and boring. abc353 is genuine and much interesting with sigma problems.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Most difficult biased and headache contest ever.

→ Reply