atcoder_official's blog

By atcoder_official, history, 2 months ago, In English

We will hold Toyota Programming Contest 2024#9(AtCoder Beginner Contest 370).

We are looking forward to your participation!

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

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

Seems to be the highest point value of F+G in recent contests. Good luck :D

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

I love atcoder problemset

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

    till what problem are you able to solve generally?

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

    The most interesting problems at the moment. I don't care if those problems are not new and have been used in some other contests. I still love classical problems with algorithms and data structures much more than ad-hocs/observations.

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I think question A is to determine whether the sum of the first two digits of a three-digit number modulo ten is equal to the last digit.

»
2 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Can anyone explain how the flow of 2nd question is going ?

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

I feel like this contest was harder than usual

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

When will the rating come out?

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Getting RE for C. What's the correct approach towards solving the problem?

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D is too complex for ABC, I think. I considered a DSU solution and I'm not even able to implement it.

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

    I disagree, it is just a simple brute force.

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

    I implemented a Segment Tree solution in about 30 minutes (creating a segment tree for every row and every column, and then find the first/last occurence of the number "1" in a specific range)

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

    I thought of DSU/Path compression and implemented it in around 25 minutes.

    I think problem E was much harder than usual.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it -7 Vote: I do not like it

      I did the same brute force in problem A but it did not work, my rating went down to 69.

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

      I have implemented a DSU solution too but it is giving WA ,can you help me

      https://atcoder.jp/contests/abc370/submissions/57561766

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

      can u explain the DSU approach ?

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

        Just Path compression along 4 directions and keeping an visited array to check if the cell has a wall or not.

        code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    There is a simple solution that doesn't require DSU.

    Spoiler
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    i wrote at first brute force then optimized using vectors of sets for rows and columns and do binary search upon them.

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

    its just binary search ._.

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

    i did a simple binary search solution with sets, it wasnt that hard

»
2 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it
Pain

What is the expected way to find the cuts in F? I'm pretty sure my solution of calculating the min distance for $$$k$$$ segments starting from each point with binary lifting is overkill and not the intended.

Wow, apparently binary lifting is the intended solution based on the official editorial.

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

    if possible, can you share your code, just curious to see and debug where it failed. my approach is just the same as yours.

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

For Question D, can any one tell me why my code is failing on 2nd example testcase,

i don't know what is the issue but my code is working fine on vscode and when i run it on atcoder compiler then it is giving me runtime error. please help me to solving my problem. code link

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

Any hints on how to solve problem E?

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

    You can solve it naively in $$$O(n^2)$$$ with DP, try to kick out the second loop.

    My submission: https://atcoder.jp/contests/abc370/submissions/57538962

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

      You can do in O(n) as well using prefix sums and map

      My submission : Link

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

        because you've used map, so the correct time complexity should be O(nlogn)

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

        Bro,can you plz explain your code? I mean your thought process!

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

          Let $$$dp_i$$$ represent the number of ways to partition the first i elements of the array into continuous subsegments such that none have sum $$$K$$$. For the transition you can extend from any index before $$$i$$$ such if $$$p_i - p_j != K$$$. In other words the sum of all $$$dp$$$ values before $$$i$$$ minus the sum of $$$dp$$$ values where the prefix sum equals $$$p_i - K$$$ which you can maintain with std:map.

»
2 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

hard enough in spite of starting at 20 minutes. My submission

»
2 months ago, # |
  Vote: I like it +71 Vote: I do not like it

PSA: For the editorial of problem G it mentions Lucy DP, DO NOT SEARCH IT UP

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

    yeah same, i also google searched, and it gave me inappropriate results. Any resources for this Lucy Dp to learn?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +16 Vote: I do not like it

      Checking the original editorial in japanese shows what they actually meant by Lucy DP. The term is coined from a comment by user Lucy_Hedgehog in the thread for Project Euler: Problem 10, which simply asks you to find the sum of all prime numbers below $$$2\cdot 10^6$$$. Lucy_Hedgehog shows a solution using dynamic programming instead of using the sieve of Eratosthenes. It can be read here. (Only visible if you have solved the problem)

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

the ABC problem is easy for me

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

A question: when doing F, I set the lower bound to do binary search to 0, and that results in WA*1 on testcase55.txt. When I set it to 1, it passed. That's strange to me: not check(1) is obvious impossible, or is it?

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

    I think there might be a subtle mistake somewhere else in your code which is causing this change to somehow affect the answer.

    My code which uses a lower bound of 1 (with $$$l \lt r$$$ as the break condition, so printing $$$0$$$ is impossible) gets AC on testcase55.txt.

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

      Gave my first contest at Atcoder any idea when do editorials come out, i found the problems to be great but had little issue understanding prob B,could only solve till C sadly.

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

      Well, I think it would be easier to talk about it if I post out my code for checking:

      int calc(int v) {
        for (int i(0), l(0), s(0); i != N; ++i) {
          while (s < v) s += arr[(i + l++) % N];
          len[0][i] = l;
          s -= arr[i], --l;
        }
        for (int i(1); (1 << i) <= K; ++i) {
          for (int j(0); j != N; ++j) {
            int m((j + len[i - 1][j]) % N);
            len[i][j] = len[i - 1][j] + len[i - 1][m];
          }
        }
        int cnt(0);
        for (int i(0); i != N; ++i) {
          int x(i), l(0);
          for (int j(0); (1 << j) <= K && l <= N; ++j)
            if (K & (1 << j))
              l += len[j][x], x = (x + len[j][x]) % N;
          if (l <= N) ++cnt;
        }
        return cnt;
      }
      

      The logic is a bit different from others, so I wonder if there's a legal piece of input can make a difference.

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

Problem E, have the difficult statment, the authors should have included the full explanation of at least a single test. If any body have understood the problem statement, please describe it. Thanks in Advance!

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

    For each $$$M (1\leq M\leq N)$$$, partition the array into $$$M$$$ non-empty subarrays.

    Example: If $$$A = [1, 2, 3, 4]$$$ and you choose $$$M=3$$$, you can partition the array in 3 ways: $$$([1,2], [3], [4]), ([1], [2, 3], [4]), ([1], [2], [3, 4])$$$. If you choose $$$M=1$$$, you can partition the array into only 1 way: $$$([1, 2, 3, 4])$$$.

    Out of all of these partitions of the array, how many partitions exist such that it does not have a subarray with sum $$$K$$$?

    Let me know if you have further queries!

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

      Can u explain how to solve E? I don’t get the Editorial solution!

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

        Replied to your comment below.

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

Can anyone explain which concept used in problem D?? i got TLE in it.

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

I'm stuck in ABC problem.

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

I dont understand the official editorial. Can anyone explain how to solve E?

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

    Let's define a few things.

    1. A "good subarray" is a subarray with the sum of elements not equal to $$$K$$$. A "bad subarray" is a subarray with the sum of elements equal to $$$K$$$.

    2. $$$dp(i)$$$ is the answer for the prefix of length $$$i$$$ (ending at $$$i$$$), i.e. $$$A[1...i]$$$. The final answer is $$$dp(N)$$$.

    3. $$$pf(i)$$$ is the prefix sum of $$$i$$$, i.e. the sum of the elements $$$A[1...i]$$$.

    We go from left to right and calculate the answer.

    How do you calculate $$$dp(i)$$$ if you know $$$dp(j)$$$ for all $$$j (1\leq j < i)$$$?

    Imagine you want to take $$$[j...i]$$$ as the last subarray. You can take it if and only if it is "good", i.e. $$$pf(i)-pf(j-1)\neq K$$$. So, $$$dp(i)$$$ is the sum of all $$$dp(j)$$$ such that $$$pf(i)-pf(j-1)\neq K$$$. The condition can also be written as $$$pf(i)\neq K+pf(j-1)$$$.

    Notice that $$$dp(i)$$$ can also be defined like this instead: $$$dp(i)$$$ is the sum of all $$$dp(j)$$$ such that $$$1\leq j < i$$$, minus the sum of $$$dp(j)$$$ such that $$$1\leq j < i$$$ and $$$pf(i) = K+pf(j-1)$$$. This is easier because you can keep a sum of all $$$dp(j)$$$ upto $$$i$$$, and also keep a track of the sum of $$$dp(j)$$$ for each $$$K+pf(j-1)$$$ using a map.

    Submission: 57540996

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

      why tot = 1 ? Is not it should be 0 ? as we start form 0 ?

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

        It's because $$$dp(0) = 1$$$. So the total sum of $$$dp(j)$$$ we currently have is $$$1$$$. (Implementation detail)

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

I found B much harder to understand than all other problems.

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

In Question F, how is it ensured that there is no overlap of intervals which is given to each person ?and how does " Noticing that there is at least one i such that cut line i is used by a division if and only if the N pieces can be divided into K segments so that each segment has a mass of at least" hold. Link to editorial: https://atcoder.jp/contests/abc370/editorial/10900

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

so what is the DSU approach to solving D?:(

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

(Newbie here)

Is it just me or is the field stacked against Python users? After the contest I tried cobbling together, for Problem D, a SortedSet equivalent in python using Segment Trees. Whilst my solution ran into TLE with low margins, I find that C++ solutions with same complexity comfortably passing the time constraints.

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

can anybody check my code for problem D pls? code

I don't think that my solution should be AC, since I am using binary search only partially(only for finding down located and right locted walls but for left and upper sides I just did brute force).

is it supposed to be AC using such approach?

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

g1: an array whose i-th element is an ordered set maintaining the column index the remaining walls in the i-th row; g1: an array whose j-th element is an ordered set maintaining the row index the remaining walls in the j-th column; amazing editorial which has 2 g1 and no g2(

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

When will you publish test cases for abc 370?

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

For problem E, i have been trying to do segment tree for optimizing dp, but it gives me wrong answer.

My code:

Code

Can anyone tell what am i doing wrong?

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

Can someone please explain how to quickly compute f_k(i+1) for every 1<=i<=N using doubling method.

I believe the author is referring to powers of 2 where if I have information about f_k(2) and f_k(4), i can use it to calculate f_k(6) but I don't know exactly how to do that.

Thanks.

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

    You can search for binary lifting for better understanding.