Heisenberg's blog

Extension to a standard dp problem :)

By Heisenberg, history, 7 years ago, In English

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 !!

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not sure that it is solvable with dp; I saw similar problem on some OJ.

    → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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<bits/stdc++.h>
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+j<k){
				ll temp=(k-i-1-j);
				if (i>0) 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;
}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution is wrong, test from blog 10 4.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

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.

→ Reply