chokudai's blog

AtCoder Beginner Contest 158 Announcement
By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 158.

We are looking forward to your participation!

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

Comments Comments (49)
| Write comment?
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Just got all 6 problems correct. No WA on any of them either!

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

good contest!

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Task-D submission using deque Here. I first did the same logic but instead wrote this line which gave me TLE.

s = c + s

This line appends c to the front of the string S and rewrites the whole string S which is costly. Hope this helps :)

→ Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Screencast

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What do I need to learn to solve task-E?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +18 Vote: I do not like it

    Thinking.

    Ok honestly, prefix sums and modular arithmetic if you really don't know them, but actually it is more about experience and figuring out the correct direction to think in.

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

      Thx. Prefix sums did not pop in my head, anyways I will practice more :)

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

    How I understood it: in case p is neither 2 nor 5, it can be solved with the same linear-time solution (after using a vector of size p as hashmap) as the 2sum problem: (https://leetcode.com/problems/two-sum/) (one needs to make an observation about divisibility, basically that if $$$t\cdot 10^i = 0 \mod p$$$, then $$$p\vert t$$$ ).

    In case p = 2 or 5, then this observation is no longer true, but the problem can be solved (more) easily on an ad hoc basis (e.g. if p=5, count all substrings which end at a 0 or 5).

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for E I can solve it in O(NP) time using dp but it will give TLE for N=2*10^5 & P<=10^4.

So any suggestion please?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    With some optimizations, I managed to fit O(NP) solution in TL. I will share some methods I used. I assume that you understand some basic modulo arithmetic.

    1) Precompute everything. We precompute transition, which is 10*10000 size. transition[i][j] = k will represent the information of "If we had a substring with $$$k \mod p$$$ until this letter, and we have current digit $$$i$$$, it will produce substring with $$$j \mod p$$$.

    2) Of course, if $$$P = 2, 5$$$, it may be possible that we do not have such $$$j$$$. I used two different logic for $$$p < 10$$$ and $$$p >= 10$$$, but what I actually wanted is to guarantee $$$p \neq 2, 5$$$.

    3) Use dp with toggling for memory optimization (we cant' fit 2e9 integers to memory), using the transition we computed at 1).

    Here is my code. https://atcoder.jp/contests/abc158/submissions/10628481

    Note that the transition for two cases (small P and large P) is different. For small P, we use transition[i][j] = k then "If we had a substring with $$$j \mod p$$$, current digit $$$i$$$, it produce $$$k \mod p$$$. This is dirty, but it is because I knew that 1) definition better after getting TLE several times.

    After TLE, I also noticed that we have to use 10*10000 array for transition instead of 10000*10, which I feel very unintuitive for logic. But this was to enhance performance with better caching. Of course I used O3 and Ofast pragmas, and all those tedious things unrelated to algorithm.

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

      I have read your code. But I still can't make sense of the difference between the two kinds of definition.

      My code is the same as yours. (Just the part in P<10)

      https://atcoder.jp/contests/abc158/submissions/10633816

      This will get TLE.

      I just can't understand why the second part in your code(P>10) is faster than the original one (P<10)? Do these two have any difference in Complex?

      Thank you~

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

        I do not fully understand the performance difference between two definitions, but I got 3 TLEs from definitions above and got AC after changing definition.

        As I understand, in the first case (which I used for $$$P < 10$$$), we cannot guarantee that every single dp[r][k] is touched by one iteration for $$$n$$$, hence we have to reset the dp table. However in my logic we can't simple reassign this variable (we have to add it just like you used rem[now][mp[j][s[i]-'0']]+=rem[now^1][j];) In your code I see for (int j=0;j<p;j++) rem[now][j]=0; which is executed $$$O(np)$$$ times.

        If we use second definition, it is guaranteed that every entry is updated in single iteration. Hence, we do not have to reset the value before we use, and we can simply assign as dp[r][j] = dp[1-r][k];. I think the zeroing out time is quite critical, since I used memset which should be much faster than manually zeroing out and it didn't passed.

        I don't think using register keyword is meaningful (modern compilers tend to ignore that) in my code. But using pragmas are. Try with bunch of #pragma stuff I wrote in my code. You might find https://codeforces.net/blog/entry/66279 helpful for understanding these compiler pragma and how it enhances performance.

        And to answer last question, no. It has absolutely no difference in complexity. My code is still $$$O(np)$$$, but as you might know, there are hidden constant factors in big-O notation. My code is optimizing that constant factor.

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

          Ok, I will try to reduce my constant and think more about this.

          Thank you~

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a tutorial for task E

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    We observe that we can transform the string into an array of integers, where A[0] = S[0], A[1] = 10 * S[1], A[2] = 100 * S[2] and so on. We build the array A modulo P.

    Now, the substring is transformed into a subarray. We observe that if P is coprime to 10, then if the subarray sum is divisible by P the substring must also be divisible by P in base 10. Thus, if P is coprime to 10, this becomes the classic problem of finding the number of subarrays with sum divisible by P, which can be solved in O(N logN) with a map.

    If P is not coprime to 10, P is either 2 or 5. Thus, we just count all of the substrings ending with a digit divisible by P.

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

      We observe that if P is coprime to 10, then if the subarray sum is divisible by P the substring must also be divisible by P in base 10.

      Can you elaborate more? Why do we not need to divide the subarray sum by some power of ten to get the substring here?

      Thanks

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

      It's probably A[N-1] = S[N-1], A[N-2] = 10 * S[N-2], A[N-3] = 100 * S[N-3] and so on.
      Or reverse S in the beginning :)

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

        Yeah, I implicitly did some reversal somewhere in my code (oops).

        Actually, it doesn't really matter for the case where P is coprime to 10, because subarray sum is the same forwards and backwards.

        Update: Oops, it seems I have made a small misunderstanding about what "reversal" means. My apologies, it does matter.

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

          I don't think subarray sum is the same forwards and backward. Take 15 and 51 for example: 15 % 7 = 1 51 % 7 = 2

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

      Can you please explain,why "if P is coprime to 10, then if the subarray sum is divisibile by P the substring must also be divisible by P"

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        We observe that the subarray sum is equal to the substring in base 10, multiplied by some power of 10. If P is coprime to 10, then multiplying by a power of 10 will not change divisibility by P.

        Example:

        S="135"

        P=13

        A={100, 30, 5} (actually, we store A mod P, which is {9, 4, 5})

        We observe that the subarray sum of the first two elements is 130, which is 13 * 10. The 10 does not affect divisibility by 13, thus we see this equivalence between subarray sum and substring.

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

      https://atcoder.jp/contests/abc158/submissions/10648178 I have implemented the same idea suggested by you, but I am still getting a good amount of WAs, can you point out the mistake my code is having?

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

Problem E, Editorial:Your text to link here..., though I still couldn't solve it.

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

can anyone explain O(1) solution for C?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Let the price before taxes (that's what we're looking for) be p. Then,

    floor(0.1p) = B.

    We know that floor(n) = x means that x <= n < x + 1. So, "floor(0.1p) = B" means that "B <= 0.1p < B + 1". Multiplying by 10: "10*B <= p < 10*B + 10". So, if there's an answer, it's between 10*B and 10*B + 9.

    So, all you have to do is scan each number x between 10*B and 10*B + 9 (those are only 10 numbers, so it's O(1)) and check if "A <= floor(0.08x) < A + 1" (because floor(0.08p) must be A and "floor(n) = A" means that "A <= n < A + 1"). The first number that satisfies that condition is the answer. If no number between 10*B and 10*B + 9 satisfies that condition then there's no answer and you return -1.

    → Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Can anyone guide me how to solve or approach problems of type E? I really don't have any clue.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    In my opinion E is a fairly nice problem. It requires one good observation followed by knowledge of some (fairly well-known) classic problem.

    The observation is that you can transform substring to subarray sum if P is not 2 or 5 (if P is 2 or 5, the problem becomes much easier anyways, so it doesn't matter) by transforming the string to an array using a method I described here: https://codeforces.net/blog/entry/74534?#comment-586664. I'm not sure how to explain how to get to this observation, but I believe that it comes from experience with similar problems.

    After that, the problem becomes "count subarrays with sum divisible by P". This is a fairly well-known classic problem that can be solved with prefix sum and map (or some other method of counting occurrences of a value in a range quickly).

    In conclusion, if you're stuck on a problem like E, try to make some nice observations to turn the problem into something more classic that you've seen before.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh Yes!!! Your transformation to the problem made it look so easy. Thank You.

      → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

English Translation of Japanese editorial

E: Divisible Substring First, fix the left end and extend the right side while calculating the remainder after actually dividing by P, so you can find the answer with O (N2). For example, if the left and right sides of a character string are fixed, let's consider formulating whether the remainder after dividing by P can be calculated. Put Ui: = S [i: N] (the i-th character after S) as the evaluated integer. For convenience, UN + 1 = 0. (At this point, we have not yet considered it with modP.) At this time, the integer that evaluates the i-th to j-th characters of S can be expressed as Ui−Uj + 110j + 1−i. (1≤i≤j≤N) where it is important that P and 10 are relatively prime. In the case of P = 2,5, it can be solved by O (N) because it is determined only by whether or not the right end is divisible by P. P̸ = 2,5. At this time, Ui−Uj + 110j + 1−i is divisible by P is equivalent to Ui−Uj + 1 being divisible by P. Therefore, this problem was solved by O (N + P) by calculating UimodP from the right side and managing the number of j that is currently xmodP with an array or map. (This time P is small, but if P is large, use map)

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

My solution for E uses the same logic as provided in the editorial here : https://codeforces.net/blog/entry/74551 But I am getting WA on TC 33 (and only on 33). Could someone point out why this is the case? Here is the link to my solution: https://atcoder.jp/contests/abc158/submissions/10649436

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

General question as I wasn't sure where/who to ask on AtCoder. If we register for a contest, but do not participate, does it impact rating, or does rating only get impacted when something is submitted (similar to Codeforces)?

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +13 Vote: I do not like it

I found there contain a BUG in some of the AC programs base on prefix sum/suffix sum at problem E. Try this input:

4 4
3543

The answer should be 1. I used several solutions based on prefix sum for testing, but they all output 6. The reason why this problem occur is that when p=4, 10%p=2. If there are 2 zeros at the end, the answer will be divisible whatever the number really are. for example, 3543-43=3500, even though 35 is not divisible by 4, 3500 is divisible by 4.

However, I notice there are some guys solve this problem by DP. They would not occur the bug like this.

update： I made a STUPID mistake that I didn't notice p should be a prime. Sorry about that :( So the solution based on prefix sum is right, they just can not handle the situation when p is not prime, which is not considered in this problem.

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

    can u share the codes which used dp to solve this.

    → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In the editorial of E, shouldn't it be $$$\frac{U_i-U_{j+1}}{10^{N-j}}$$$ instead of $$$\frac{U_i-U_{j+1}}{10^{j+1-i}}$$$?

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Supplementary editorial and sample codes for last 4 problems AtCoder_ABC_158

→ Reply