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

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

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

We are looking forward to your participation!

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

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

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

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

I love atcoder problemset

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

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.

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

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

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

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

»
19 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +13 Проголосовать: не нравится
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.

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

Any hints on how to solve problem E?

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

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

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +71 Проголосовать: не нравится

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

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

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?

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

    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.

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

      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.

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

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!

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

    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!

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

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

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

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

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

    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 \lt 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 \lt i$$$, minus the sum of $$$dp(j)$$$ such that $$$1\leq j \lt 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

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

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

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

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

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

When will you publish test cases for abc 370?

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

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?

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

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.