Please give me a hint in solving DIGITSEP?

I solved it using Dynamic Progrmming.

Let * dp[i][j][k]* denote maximum value of

*you can get after placing*

**gcd****jth**partition on the

**ith**number, and the number you are considering is of length

**k**, that is number formed using digits i,i-1,…i-k+1.

To calculate the dp value:

**dp[i][j][k]**=max(gcd(current number,dp[i-k][j-1][l]) ) , where **l** varies from 1 to **m**

Final answer is: max(dp[n][i][j]),m where **X<=i<=Y** of the question, and **1<=j<=m**

Complexity: **NY(M^2)** per test case, considering O(1) gcd, but actually gcd(a,b)) takes time **logarithmic** in max(a,b).

nicely explained!

happy it helped !

Dynamic Programming was indeed the intended solution. You can either refer to @ankesh18 's method (which, by the way is quite similar to how I did too) or have a look at the editorial.

@ankesh18, I tried to partition the string into exact k parts and tried this for every value from x+1 to y+1. However, I found was getting WA on 2 test cases…I later found mistake in the code, that taking maximum gcd was not the solution. Please have a look at my code here https://www.codechef.com/viewsolution/12554951

and suggest me how do I correct this mistake…

are you partitioning the string in k parts and iterating over k, like first for 1, then for 2 and others, it wont work.

See my dp states.

@ankesh18 approach could be more optimized by reducing the state to just two variables ie the no of separation used and the index.