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

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

DP Bitmask - Topic Stream

Shayan

До начала 07:47:27

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

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

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

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
5 недель назад
14

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

Написать комментарий?

seanyong1225

5 недель назад, # |

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

→ Ответить

ducmatgoctoanlyhoa

5 недель назад, # ^ |

I got the answer! It's in the below comments.

→ Ответить

Abito

5 недель назад, # |

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

5 недель назад, # ^ |

That seems interesting, I'll try it

→ Ответить

Abito

5 недель назад, # ^ |

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

→ Ответить

asdasdqwer

5 недель назад, # |

Here's an explanation of one possible solution

→ Ответить

ducmatgoctoanlyhoa

5 недель назад, # ^ |

Why do they use the suffix and not prefix sums?

→ Ответить

asdasdqwer

5 недель назад, # ^ |

← 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

5 недель назад, # ^ |

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

5 недель назад, # ^ |

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

5 недель назад, # ^ |

← 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

→ Ответить