### Blue_Legend-'s blog

By Blue_Legend-, history, 10 months ago, ,

Given 1<= n <= 10^6. At every stage one can apply any one of three operations : (1.) if i%3==0 then i=i/3; (2.) if i%2==0 then i=i/2; (3.) if i>=1 then i=i-1; --------->The target is to apply the above steps till we reach 1 ; We can find minimum number of steps to reach 1 easily by simple dp state !! --------->But what if we need to check whether this can be done in exactly k steps where 0<=k<=n-1. ---------->For Example : 1.{ n=10; if(k==4) ans= yes.(10->9->3->1) if(k==3) ans= no. } Solution Needed !!

•
• -8
•

 » 10 months ago, # |   0 Are you sure it is solvable? I mean I almost feel the solution, it doesn't seem unsolvable, but have you come up with it or just read it somewhere?
•  » » 10 months ago, # ^ |   0 I am not sure that it is solvable with dp; I saw similar problem on some OJ.
 » 10 months ago, # | ← Rev. 4 →   0 Ok, so I checked my solution again this works for the case when you use all the -1 operations at once and then the *2 and *3 so, this doesn't give the correct answer for the given question. #include using namespace std; typedef long long int ll; int main(){ long long n,k; cin >>n>>k; ll max2=log2(n)+1; double mx3=((double)log2(n)/(double)(log2(3)))+1; ll max3=mx3; //printf("a + b + c = k\n"); //printf("a + 2^b + 3^c = n\n"); //printf("a = k -b -c\n"); for (int i=0;i<=max2;i++){ for (int j=0;j<=max3;j++){ if (i+j0) temp+=pow(2,i); if (j>0) temp+=pow(3,j); if (temp==n){ printf("Solution Exist \n"); printf("a: %d b: %d c: %d\n",(int)k-1-i-j,i,j); return 0; } } } } printf("Doesn't exist\n"); return 0; } 
•  » » 10 months ago, # ^ |   0 Your solution is wrong, test from blog 10 4.
•  » » » 10 months ago, # ^ |   0 Sorry earlier I was taking n-> 0 in k steps 10->9->3->1 is actually 3 steps Now taking it to n->1 in k-1 steps.
 » 10 months ago, # | ← Rev. 2 →   +28 First let us make brute-force solution: dp[i][j] indicates if it is possible to transform i into 1 in j steps. It can be done in O(n ^ 2) or in O(n^2 / 64) using bitset. I observed that all cells with 1 in dp[i] are making segment [min_for(i), i — 1]. I checked it for first about 70000 numbers and didn't find mismatch. I guess this can be proved strictly, but i thought something like this: Suppose that for all x < i possible j are making segment [min_for(x), x — 1]. If i isn't divisible by 2 or 3 it is obvius it'll have segment [min_for(i — 1) + 1, i — 1] If i is divisible by 2 and isn't divisible by 3 segment will be union of [min_for(i / 2) + 1, i / 2] and [min_for(i — 1) + 1, i — 1]. It is noticeable that min_for(x) is much less than x (for big x), something related to log(x). And because of this min_for(i) <= i / 2 — 1 and union will make range [min_for(i / 2) + 1, i — 1]. Similarly with other cases. So your task is just to calculate min_for array (it can be done in O(n)) and if min_for[x] <= k < x answer is YES.