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

Find all substrings of a string of digits that forms a number divisible by 2019
Автор ducmatgoctoanlyhoa, история, 2 месяца назад, По-английски

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!

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

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

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

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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]

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

Here's an explanation of one possible solution

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

    Why do they use the suffix and not prefix sums?

    → Ответить
    • »
      »
      »
      2 месяца назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

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

        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;
}
        → Ответить
        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

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

            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

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

              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.

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

                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!

                → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

isnt this is clearly suffix

→ Ответить