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

Автор chokudai, история, 4 года назад, По-английски

We will hold AtCoder Beginner Contest 158.

We are looking forward to your participation!

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

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

good contest!

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

    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.

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

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

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

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

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

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?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    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.

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

      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~

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

        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.com/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.

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

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

          Thank you~

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

Can anyone give a tutorial for task E

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

    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.

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

      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

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

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

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

        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.

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

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

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

      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"

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

        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.

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

      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?

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

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

can anyone explain O(1) solution for C?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    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.com/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.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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)

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

My solution for E uses the same logic as provided in the editorial here : https://codeforces.com/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

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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}}$$$?

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

Supplementary editorial and sample codes for last 4 problems AtCoder_ABC_158