You are not logged in. Please login at www.codechef.com to post your questions!

×

DIGITSEP - Editorial

6
1

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.

This question is marked "community wiki".

asked 19 Jan '17, 06:03

mgch's gravatar image

6★mgch
3451128
accept rate: 23%

edited 19 Jan '17, 20:34

admin's gravatar image

0★admin ♦♦
19.7k350498541


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

link

answered 21 Jan '17, 16:53

amrityavagmi's gravatar image

4★amrityavagmi
111
accept rate: 0%

edited 22 Jan '17, 13:43

wittyceaser's gravatar image

2★wittyceaser
3.4k194377

thanks a lot :D

(21 Jan '17, 17:27) abhaygupta971★

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

link

answered 22 Jan '17, 21:22

c0d3h4ck3d's gravatar image

4★c0d3h4ck3d
11918
accept rate: 0%

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

(23 Jan '17, 13:22) wittyceaser2★

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. :|

(25 Jan '17, 19:41) c0d3h4ck3d4★

"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 .

link

answered 23 Jan '17, 09:31

jragarwal's gravatar image

2★jragarwal
11
accept rate: 0%

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.

(23 Jan '17, 13:19) wittyceaser2★

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?

link

answered 21 Jan '17, 15:20

abhaygupta97's gravatar image

1★abhaygupta97
1
accept rate: 0%

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

link

answered 24 Jan '17, 20:19

fasahatnizami's gravatar image

4★fasahatnizami
1
accept rate: 0%

I can not access your solution.

(24 Jan '17, 21:58) wittyceaser2★

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][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);

link

answered 25 Jan '17, 13:18

codefreak9's gravatar image

5★codefreak9
1
accept rate: 0%

edited 25 Jan '17, 13:20

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

link

answered 02 Feb '17, 23:07

pparwal12's gravatar image

5★pparwal12
1
accept rate: 0%

edited 02 Feb '17, 23:10

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?

link

answered 14 Feb '17, 19:15

tkg97's gravatar image

4★tkg97
1
accept rate: 0%

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

link

answered 04 Jul '17, 23:26

esolang_coder's gravatar image

5★esolang_coder
1
accept rate: 0%

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 ;) )

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

(05 Jul '17, 00:23) abhikalpu_1235★

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.

(05 Jul '17, 00:28) abhikalpu_1235★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,490
×2,558
×2,086
×921
×314
×125
×18

question asked: 19 Jan '17, 06:03

question was seen: 3,607 times

last updated: 05 Jul '17, 00:30