Author: Vaibhav Tulsyan
Tester: Istvan Nagy
Editorialist: Misha Chorniy
Difficulty:
Medium
Pre-Requisites:
greatest common divisor (gcd)
Problem Statement
You are given a string S which consists digits as characters. Let’s iterate over all partitions into K parts, where K in the range between X+1 and Y+1 and each part must has a length between 1 and M. After that, let’s transform each part in integer and calculate gcd of received integers. Find the maximal value of gcd over all such partitions.
Explanation
Subtask 1
For the first subtask, we can iterate over all partitions using bitmasks. After each of the first N-1 digits we can put separator or don’t put, hence it takes 2^{N-1}) operations in the worst case. After that go through the partition in O(N) and calculate gcd manually. This approach takes time O(2^N*(N+log(10^M)), not O(2^N*N*log(10^M)). If you have array and you need to find gcd of it’s elements, next algorithm will work in O(N + log (max A)), not in O(N log (maxA)). You can prove it.
g = 0
for i = 1..N
g = gcd(g, A[i])
Subtask 2
For the second subtask we need something smarter than bitmasks. Let’s put the first separator, we will get some number g, which values of gcd is possible after fixing the first integer. If we process gcd(g, x) we’ll obtain some divisor of the number g.
How many first integers can be? At most M. How many distinct values of gcd can be? At most M * O(f(10^M)). f(X) - is the maximal number of divisors of an integer less than X. f(N) can be approximately estimated in N^{1/3}, for numbers less than 10^{18}. Therefore, can be O(M * 10^{10/3}) distinct values of gcd, practically is much less. It gives us the next idea for solution:
Let DP_{i, j} - set of the possible values of gcd on prefix S[1..i], if we put exactly j separators and the last one placed exactly after position i.
What is the start values for this DP?
DP_{i, 1} = {integerValue(S[1..i])}, when 1 <= i <= min(N, M)
How to recalculate DP, which transitions exist?
When we know set of the values of gcd for state DP_{i,j}, we can iterate over next separator after position i:
DP_{i,j} -> DP_{ni,j+1}, where i < ni <= min(N, i + M), and new value of the gcd will be gcd(g, integerValue(S[i+1..ni]))
What will be the answer? It will be the maximal value of gcd over all values DP_{N,i}, where X + 1 <= i <= Y + 1, because we split array in exactly i parts. Let’s write pseudocode of such solution:
for i = 1..min(N,M)
DP[i][1].insert(integerValue(S[1..i])) //initialize DP
for i = 1..N
for sep = 1..Y
for ni = i+1..min(N,i+M):
tempValue = integerValue(S[i+1..ni]))
//It's better to precalculate all values S[i..j]
for g inside DP[i][sep]
DP[ni][sep + 1].insert(gcd(tempValue, g))
ans = 1
for sep = X+1..Y+1
for g in DP[i][sep]
ans = max(ans, g)
How to estimate time of work? Each prefix in the string may have O(M * 10^{10/3}) values of gcd in the worst case. From each value can be O(M) transitions. Hence total complexity can be estimated in O(N * M^2 * 10^{10/3}), but practically is much less.
Solution:
Setter’s solution can be found here
Tester’s solution can be found here
Please feel free to post comments if anything is not clear to you.
)