atcoder_official's blog

AtCoder Beginner Contest 369 Announcement
By atcoder_official, history, 3 months 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

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

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

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

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

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

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

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

Omg the first time I solve all 7 problems!

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

problem E was great, but implementation was long

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

Was F some sort of 2D Segment Tree?

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

I liked the problem E very much.

→ Reply
»
3 months 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
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This problem is similar to https://codeforces.me/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
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

      → Reply
    • »
      »
      »
      3 months 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
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        1976F - Remove Bridges

        → Reply
      • »
        »
        »
        »
        3 months 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
      • »
        »
        »
        »
        3 months 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
  • »
    »
    3 months 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
    • »
      »
      »
      3 months 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
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

E was exhausting, great question.

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

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

→ Reply
»
3 months 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
  • »
    »
    3 months 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
    • »
      »
      »
      3 months 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
»
3 months 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
»
3 months 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
  • »
    »
    3 months 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
»
3 months 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