Please give me a hint in solving DIGITSEP?
3 Likes
I solved it using Dynamic Progrmming.
Let dp[i][j][k] denote maximum value of gcd you can get after placing 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).
7 Likes
nicely explained!
1 Like
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.
1 Like
@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.