DIGITSEP - Editorial

Practice

Contest

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.

6 Likes

I solved the problem just as given in the editorial. All sub-tasks are giving right answer except one. Here is the link to my code link text. Can you please tell what I am missing in my code?

@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”.

1 Like

This is too much for me. Can you please provide some source which explains DP with bitmasks in simple language.

1 Like

“Each prefix in the string may have O(M∗1010/3)O(M∗1010/3) values of gcdgcd in the worst case.” Can you please elaborate this line .

1 Like

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

I couldn’t figure out the error in my solution CodeChef: Practical coding for everyone . 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][num-1][m] .It means we placed a separator at index idx.
t2 = dp[idx+1][num][cur-1] .It means we didn’t place a separator here.
Let z is the substring s.substr(idx-m+cur,m-cur+1));

Now dp[idx][num][cur] = max(gcd(t1,z) , t2);

@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) ?

Has anybody done it with backward approach? like DP(i,j) = max(DP(k,j-1)) for all k=i+1 to n-1 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?

could anyone please explain why the complexity of finding gcd in a list is O(N+log(max of list)) ,not O(n*log(max of list))??

thanks a lot :smiley:

The maximum possible first number that you can select is 10^{10}, because the maximum allowed length in the worst case is 10.
A rough upper bound on the no. of divisors of any positive integer is N^{1/3}.
Now, when you select further numbers, the greatest common divisor has to be one of the divisors of this first number.
Hence, we can calculate an upper bound on the no. of distinct GCDs possible based on the first number selected.

What part of the solution did you not understand - if you specify, I may be able to help.

I can not access your solution.

I don’t understand the state of the DP used in the solution. I am new to DP, so it is not at all understandable, I should start solving DP problems. :expressionless:

fact 1- while calculating a gcd(a,b) applying eulerian algorithm the more iteration it will take to calculate the lesser will be the gcd.

fact2- while calculating gcd(a,b) if the minimum(a,b) is very small the algorithm will execute in few iteration.

Now answering your question(combo of fact1 and fact2 :wink: )

at every iteration of the for loop the value of gcd will remain same or decrease.

suppose calculating gcd in first iteration(of for loop) took i1 steps.

let, calculating gcd in second iteration took i2 steps.

after several such steps…(suppose after nth iterations)

when i1+i2+i3…+in is nearly equal to log(max).

the current calculated gcd will be nearly equal to 1(may be ~ 100(which is still less)).

then after nth iteration yhe gcd can be calculated with at max 4 or 5 iterations…(the 4 or 5 will be decreasing to 2 or 3 afterwards:D )

so it is O(N+ log(Max of list)).

Please feel free to ask if you are stuck.