ducmatgoctoanlyhoa's blog

Find all substrings of a string of digits that forms a number divisible by 2019
By ducmatgoctoanlyhoa, history, 2 months ago, In English

Problem:

Given a string $$$S$$$ containing only digits from $$$1$$$ to $$$9$$$, with length at most $$$5 * 10 ^ 5$$$. Find all pairs $$$(L, R)$$$ such that the substring of $$$S$$$ from $$$L$$$ to $$$R$$$ forms a number divisible by $$$2019$$$.

Problem source (Vietnamese): https://lqdoj.edu.vn/problem/mult2019

My idea for this problem is to try and evaluate all substrings and check if they are divisible, but of course that would be too long. Other than that I am pretty stuck.

I would love to know if there are better ideas for this problem. Thanks in advance!

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

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

im interested to know the answer too, pls tell me when u get the answer

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

I have an idea to solve in $$$O(n2019)$$$. Let's say p[i] is the mod of the number formed by the first i digits. Let's say we moved from i to i+1, then all prefixes before i+1 will multiply by 10, so we can get p[i+1]. Now to find how many substring end up here that satisfy the constraints, we want to find the count of previous prefixes that equal the current prefix. We can keep a frequenxy array and every time we move we loop through it and make f[i*10%2019] = f[i]

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

    That seems interesting, I'll try it

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

      It won't pass since n * 2019 = 1e9 . But I thought that maybe there's an improvement to the solution

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

Here's an explanation of one possible solution

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

    Why do they use the suffix and not prefix sums?

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

      Define the suffix sum in the following way:

      $$$ s_i = s_{i+1} + 10^{n-i} * value_i $$$

      Now, if a substring $$$L, R$$$ is a multiple of 2019, then the value of that substring multiplied by $$$10^i$$$ is still a multiple of 2019 for every $$$i$$$. The reason we use suffix sums is that after calculating $$$s_L - s_{R+1}$$$, we might get a value with zeros at the end, however, we can ignore these since multiplying by any power of 10 doesn't change the divisibility by 2019.

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

        Wait, isn't that the formula for the prefix case instead? In that solution link calculating stuff from the suffix looks much more complicated

        for (int i = n - 1; i >= 0; i--) {
	// find the remainder of the current number mod 2019
	num = (num + pow * (s[i] - '0')) % 2019;
	// increment the count of this remainder
	count[num]++;
	pow = pow * 10 % 2019;
}

        And also feel free to check my implementation, I wonder where I got wrong:

        void solve() {
    m = 2019;
    cin >> s;
    t = 0;
    p = 1;
    // for (int i = 0; i < 2020; i++) ar[i] = 1;
    for (int i = s.size() - 1; i >= 0; i--) {
        n = (n + p * (s[i] - '0')) % m;
        p = (p * 10) % m;
        ar[n] += 1;
    }
    // dbgar(ar, m);
    for (int i = 0; i < 2019; i++) t += ar[i] * (ar[i] - 1);
    cout << t / 2 << endl;
}
        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sorry, I've corrected the mistake. The problem in your code is that you don't consider the empty suffix, so initially, you have to set ar[0]=1.

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

            Thanks! I got some tests going down, but for some reason it TLEs.

            inline void solve() {
    m = 2019;
    cin >> s;
    t = 0;
    p = 1;
    memset(ar, 0, sizeof ar);
    ar[0] = 1;
    n = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        n = (n + p * (s[i] - '0')) % m;
        p = (p * 10) % m;
        ar[n] += 1;
    }
    // dbgar(ar, s.size());
    // dbgar(ar, m);
    for (int i = 0; i < 2019; i++) t += ar[i] * (ar[i] - 1);
    cout << t / 2 << endl;
}

            I'm thinking of some sort of precomputation, because p = (p * 10) % 2019 is pretty expensive. What do you think?

            Update: the problem is a multitest problem. I definitely feel like I would benefit from a precomputed table.

            Update 2: it still TLEs

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

              What is the size of array ar? It should be 2019, so if you made it 100 000 or something, you waste way too much time for memset.

              Because beside that the code looks ok to me.

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

                oh, my ar size is like 10^6 because I'm lazy to change sizes and stuff. Changed it to 2019 and now it AC'ed.

                moral of the story don't use memset with comically large arrays.

                Thanks!

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

isnt this is clearly suffix

→ Reply