atcoder_official's blog

AtCoder Beginner Contest 355 Announcement
By atcoder_official, history, 6 months ago, In English

We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2024（AtCoder Beginner Contest 355).

We are looking forward to your participation!

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to solve ABCD!!

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

There is a strange bug on the homepage of ABC355. If you're in English mode, when you enter the page, your browser begins playing music; after that, there will be some Japanese introduction to this company.

I found that the problem was caused by the video on the homepage (in Japanese mode), and the solution is to ban your browser from automatically playing media on the page. And I hope AtCoder can fix it. This is not a big problem, but sometimes it's annoying.

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

i think problem D is close to this problem

atcoder's solution

codeforces solution

the only difference is that codeforces's problem one interval should contains the other.

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

Misread B :)

Btw, how to solve F? Does it involve link-cut trees?

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

    this can be extended easily for F

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

    maybe yes , I just opened cf 5 minutes before the contest ended and saw a blog come up on MST query. I saw a GM explaining to use link cut trees. I started to read it and knew it was not of my cup of tea at least for my level.

    LMAO

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

    I solved it with basic Kruskal's algorithm, by looking at the constraints.

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

      please elaborate

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

        If one Kruskal doesn't solve the problem use 10 of them

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

found very difficult.

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

My idea for problem-E using dp find the minimum no of moves to reach from L to R, then get the path. I'm getting WA.

Code

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

    i did not read your code, but you took into consideration right that we can also add and reduce values not in range L-R for example if 1-7, we can add 0-7 and sub 0-0?

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

SpeedCoder?

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

Anybody missed reading the constraint on weight in F and then waste time?

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

    So do I.

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

    Yes. But i just dropped the problem after reading

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

    Me too, is there a Link-Cut Tree solution to it?

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

      Actually there is, but would you like to really write it...

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

Cool.

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

    Cool.

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

    he/she needs only a minute to finish four problems!? That's really insane, and also suspicious.

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

      Maybe I don't get something, but it took him 51 minutes to solve ABCD?

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

      No, they just have a really good gaming chair.

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

    Is there any extension for atcoder as well which predicts rating change ?

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

    I checked toyuzuko's contest history. Their last contest was ABC354 and they solved ABCE in less than 2 minutes, but they registered as unrated and didn't get reported. I didn't find any abnormal contests before that.

    maroonrk could you please figure this out

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

    Cool.

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

    Cool.

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

      Another conjecture is that he may have used very intelligent AI due to some unnecessary annotations.

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

    Remind me of this

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

    It's quite interesting (and suspicious?) that they also added comments to their code...it implies that they weren't rushing, yet they solved all the problems almost immediately??

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

Is there any other solution apart from link-cut tree? I didn't know about link-cut tree so did a brute force kind of solution.
I processed initial N-1 edges from lowest weight to highest weight. For each weight, I maintained connected component data using DSU.
Then for each additional edge of weight W to add, I checked if nodes U, V are in same component at DSU of weight W. If they are that means, an edge with weight <= W has connected components of these two nodes so the incoming edge can't replace any edge in MST.

If they are in different components, then that means, components to which U, V belong are connected by some higher weight edge and incoming edge can replace heavier edge in MST and update MST edge weight and then do union for U, V for all edge weights greater than or equal to W.

I got an AC with this approach but not sure if this approach is correct as everybody is mentioning link-cut tree. Can someone confirm if this is correct?

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

Why does this solution to D gives WA (https://atcoder.jp/contests/abc355/submissions/53878525)

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

For problem E, is there any intuitive understanding about the definition of S(x,y) = -S(y,x) when x > y.

I wonder how could someone come up with this definition and construct a graph.

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

When will the Editorial in English be available?

→ Reply