Find all substrings of a string of digits that forms a number divisible by 2019

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

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

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!

string, hashing, divisibility

ducmatgoctoanlyhoa
23 месяца назад
14

Комментарии (12)

Показать архивные | Написать комментарий?

Abito

23 месяца назад, скрыть # |

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]

→ Ответить

ducmatgoctoanlyhoa

23 месяца назад, скрыть # ^ |

That seems interesting, I'll try it

→ Ответить

Abito

23 месяца назад, скрыть # ^ |

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

→ Ответить

asdasdqwer

23 месяца назад, скрыть # |

Here's an explanation of one possible solution

→ Ответить

ducmatgoctoanlyhoa

23 месяца назад, скрыть # ^ |

Why do they use the suffix and not prefix sums?

→ Ответить

asdasdqwer

23 месяца назад, скрыть # ^ |

← Rev. 2 →

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.

→ Ответить

ducmatgoctoanlyhoa

23 месяца назад, скрыть # ^ |

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;
}

→ Ответить

asdasdqwer

23 месяца назад, скрыть # ^ |

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.

→ Ответить

ducmatgoctoanlyhoa

23 месяца назад, скрыть # ^ |

← Rev. 3 →

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

→ Ответить