Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

atcoder_official's blog

AtCoder Beginner Contest 369 Announcement
By atcoder_official, history, 2 weeks ago, In English

We will hold AtCoder Beginner Contest 369.

We are looking forward to your participation!

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

this round like div.3 or div.4 at codeforces?

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

    Like Div. 2.5, but the problems are more classical.

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

Let's go, can't wait for this contest!

→ Reply
»
2 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Omg the first time I solve all 7 problems!

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

problem E was great, but implementation was long

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Not sure if reconstructing the path in F added anything to the problem, but it wasn't too bad I guess

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

    i agree lol, i spend like 10 minutes to implement the "counting" part and like 15 minutes to implement "back-tracking" part

    → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was F some sort of 2D Segment Tree?

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

    You can do it with a regular segtree if you process all coins with lowest rows and rightmost columns first

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

      you can also use fenwick tree, no need to compress the coordinate :D

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

        Oops, somehow I tricked myself into thinking that coordinates are up to $$$10^9$$$ lol (and it wouldn't even make sense then to try and output the whole path in a non-compressed manner)

        → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked the problem E very much.

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how can I solve G? anyways, why have there been no official tutorials in English recently?

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

    This problem is similar to https://codeforces.net/problemset/problem/1615/E, but we only have weights on edges. Main idea is greedily expand the chosen set of vertices with such vertex that maximizes distance to current set of vertices. And when we add some vertex, we also need to put all vertices to set on path btw set and chosen set. From start set contains only root.

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

      Thanks!

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

      How to maintain the tree and find the vertex that maximizes distance from the chosen vertices fast?

      → Reply
      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        1976F - Remove Bridges

        → Reply
      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Well, you can use segtree, where you store for each vertex a length of the path from it to chosen set. And when you add some vertex u to set, you should decrease all lengths of such v that in subtree of u(it can be done via euluer tour). We also need to get maximum over all vertices(segtree allows us to do it). Now we know that each vertex will be modified exacly one time, then our compexity will be O(nlogn).

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

        Thanks to you both!

        I saw 1976F but forgot about it entirely. Exactly what I needed.

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

    Don't English tutorials always arrive slightly late? I couldn't spot any recent rated contests without an editorial in English.

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

      Oh I see it, in the past it appeared as soon as the contest ended.

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

E was exhausting, great question.

→ Reply
»
2 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

F**k ABC,G has an original problem.

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C I didn't got a single idea which was working brute was only which I could think of and d also anyone if someone can help me please

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

    The logic is to find all contiguous subarrays that form an arithmetic progression (AP). For each starting index l, the code finds the longest subarray ending at r where the difference between consecutive elements is constant. It then counts the number of valid subarrays within this range and accumulates the total count. This is done by extending the subarray as far as possible while maintaining the AP property and calculating the number of subarrays for each segment. The process is repeated for each possible starting index in the array.

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

      so we need to find the subarrays I was stuck in finding subsequences :( shittt I could have done it easily

      → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please tell how to practice dp and trees,graphs question like i can solve dp of difficulty till 1500 and above it its diffcult.

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

atcoder_official Hey there. I got a -89 rating change in ARC183, but I didn't even participate in the contest (was only registered). Can you look this up? I'm sure it might've been a mistake. My atcoder username is "Bruteforcekid"

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

    You would be rated even if you just register and didn't submit anything, so it's better to register right before the contest next time :)

    → Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any other solution to E other than brute force? like if we a problems where we don't have any queries. we just have to pass some bridges but the number of bridges can be large(large enough to not bruteforce maybe). How will we solve that version of this problem?

→ Reply