Блог пользователя atcoder_official

Автор atcoder_official, история, 3 месяца назад, По-английски

We will hold AtCoder Beginner Contest 369.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Omg the first time I solve all 7 problems!

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

problem E was great, but implementation was long

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was F some sort of 2D Segment Tree?

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I liked the problem E very much.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

E was exhausting, great question.

»
3 месяца назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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"

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 :)

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?