Author: Vaibhav Tulsyan Difficulty:Medium PreRequisites:greatest common divisor (gcd) Problem StatementYou 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. ExplanationSubtask 1For the first subtask, we can iterate over all partitions using bitmasks. After each of the first $N1$ digits we can put separator or don't put, hence it takes $2^{N1})$ 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 2For 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
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 Please feel free to post comments if anything is not clear to you.
This question is marked "community wiki".
asked 19 Jan '17, 06:03

@abhaygupta97: you have to only change the value of ans from 1 to 0. This can be verified in the case if the string is "00000". answered 21 Jan '17, 16:53

my solution is this https://www.codechef.com/submit/complete/12634499. It is passing for half of the test cases,I couldn't figure out error in my code. Can you please help? @wittyceaser answered 24 Jan '17, 20:19

I couldn't figure out the error in my solution https://www.codechef.com/viewsolution/12596229 . It is passing for half of the testcases.Can you please help? @wittyceaser My approach : dp[idx][num][cur] gives the maximum gcd of the string from index idx to the end using atmost 'num' separators and the first string from index idx can have atmost 'cur' digits. Let t1 = dp[idx+1][num1][m] .It means we placed a separator at index idx. t2 = dp[idx+1][num][cur1] .It means we didn't place a separator here. Let z is the substring s.substr(idxm+cur,mcur+1)); Now dp[idx][num][cur] = max(gcd(t1,z) , t2); answered 25 Jan '17, 13:18

@wittyceaser could you please explain the time complexity .. there are NxN states and for each such state there are M transitions . Each set may contain M x 10^(1/3) values .So shouldn't it be N x N x M x M x 10^(1/3) ? answered 02 Feb '17, 23:07

Has anybody done it with backward approach? like DP(i,j) = max(DP(k,j1)) for all k=i+1 to n1 with initialisation similar to done in the editorial just in backward manner. My code is failing on two input cases. I am attaching my code. https://www.codechef.com/viewsolution/12839603 code is well commented for ease of understanding. could you please help? answered 14 Feb '17, 19:15
