Down to Zero II

You are given queries. Each query consists of a single number N. You can perform 2 operations on N in each move.
If N=a*b (a!=1,b!=1),we can change N= max(a,b) or decrease the value of N by 1.

Determine the minimum number of moves required to reduce the value of N to 0.

Input Format

The first line contains the integer Q. The next lines each contain an integer, N.

Constraints:

1 ≤ Q ≤ 103
0 ≤ N ≤ 106

#include <bits/stdc++.h>
using namespace std;

#define SIZE 1000000

//O(nloglogn)
//Sieve of Eratosthenes

void getPrimes(vector<bool> &prime){
for(long i=2;i*i<=SIZE;i++)
if(prime[i])
for(long j=i*i;j<SIZE;j+=i)
prime[j]=0;
}

//O(sqrt(n))
//Get 'max(a,b)' as defined in the problem
//input n is always non-prime

long getVal(long n){
long res;
for(long i=sqrt(n);i>=2;i--){
if(n%i==0){
res = (n/i);
break;
}
}
return res;
}

//Try BFS

long solve(long n,long z, vector<bool> &prime,unordered_map<long ,long> &map){
long result=LLONG_MAX;
long s,tmp;

queue<pair<long,long>> q;

if(map.find(n)!=map.end())
result= map[n];
else{
q.push(make_pair(n,0));
while(!q.empty()){

pair<long,long> p = q.front(); q.pop();
n = p.first;
s = p.second;

if(!n){
result = min(result,s);
break;
}
else if(map.find(n)!=map.end()){
result = min(result,s+map[n]);
}
else{

//Push (n-1) in queue.
q.push(make_pair(n-1,1+s));

//If n is not prime insert 'max(a,b)' in queue.
if(!prime[n]){
tmp = getVal(n);
q.push(make_pair(tmp,s+1));
}

}
}
}

return map[z]=result;
}

int main() {

vector<bool> prime(SIZE,true);
getPrimes(prime);

unordered_map<long ,long> map;
for(long i=0;i<=3;i++) map[i]=i;

int queries,n;
cin>>queries;
while(queries--){
cin>>n;
cout<<solve(n,n,prime,map)<<endl;
}
return 0;
}

I have implemented the following optimizations:

1. Precomputed primes.

2. Getting the required 'max(a,b)' in optimal possible way.

3. Storing the solutions to the sub-problems.

How can I optimize it further for it to be accepted? (Though it is about writing code in competitive programming,I will be happy if you also provide suggestions to improve the readability of code and overall coding style to make it a production level code.)

• Could you add some excerpts from the Hackerrank question to the body of your question mate? Sep 22 '16 at 9:52
• Okay..I'll add. Sep 22 '16 at 9:54
• That looks much better, I made an edit to the explanation.Hope you get good answers . Sep 22 '16 at 11:06
• Given N=12, must max(a,b) be 6? Or can a=3,b=4 and max(a,b) be 4? In other words, can you choose from many different factors, or not? The wording in the problem isn't very clear on this point. I see your program assumes that you can only choose the largest of all factors. I checked the discussion on the hackerrank problem and it seems to imply that you can choose from multiple factors, not just the largest.
– JS1
Sep 22 '16 at 17:04
• In my code, I am not selecting the largest. For example, n = 36 then we have following pairs (2,18),(3,12),(4,9),(6,6). I am selecting 6 from my code, not 18 which is the largest. Sep 22 '16 at 22:06

Bug

Your code assumes that the minimum factor pair out of all factor pairs is best. For example, if n=36, it chooses 6 from (6,6) instead of 9 from (4,9), 12 from (3,12), or 18 from (2,18) because 6 is the smallest of the max(a,b) factors.

However, this may not give you the optimal solution. Consider the case n = 60. Your code finds the following answer:

60 -> 10 -> 5 -> 4 -> 2 -> 1 -> 0 (length 7 chain)

Note that it chose 10 from (6,10). The optimal solution is:

60 -> 12 -> 4 -> 2 -> 1 -> 0 (length 6 chain)

To find this solution, you must consider other factors such as 12 from (5,12).

Memoization unused

Your program attempts to use memoization via the map variable, but doesn't utilize map enough. Given your example of n=300, the function searches through thousands of possibilities without even once writing any result to the map variable until the very end, and then only for map. What it should do is write the results for each of the factors as it recursively finds the solution for them. That way you never need to find the answer to the same number twice.

Faster way

A faster way would be to solve for each number up to the maximum (1000000). Then for each query you would just need to look up the answer in the map. Here is how I would do it:

#include <stdio.h>
#include <math.h>

#define MAX     1000000

int map[MAX+1];

int main(void)
{
int numCases = 0;
int i        = 0;
int n        = 0;
int sqrt_max = sqrt(MAX);

// Init map to worst case scenario.
for (int i=0; i <= MAX; i++)
map[i] = i;

// Now, solve for each number.  At each 'i', we know that map[i] is
// already the best solution.  From 'i', we know that we can reach 'i+1'
// in one extra step.  We can also reach k*i, because 'i' is a factor
// of k*i.  But we only need to check k*i up until i*i, because after
// that, 'i' will be the smaller factor of a factor pair, and we only
// need to consider the higher factor.
for (int i=1; i < MAX; i++) {
int score = map[i] + 1;
int limit;

// Handle n-1 case.
if (map[i+1] > score)
map[i+1] = score;
// Handler the k*i case.  We start at 2*i, and go up until i*i, but
// not more than MAX.
if (i > sqrt_max)
limit = MAX;
else
limit = i*i;
for (int j = i+i; j <= limit; j += i) {
if (map[j] > score)
map[j] = score;
}
}

// At this point, map contains all the best solutions.
if (scanf("%d", &numCases) != 1)
return 1;
while (numCases-- > 0) {
scanf("%d", &n);
printf("%d\n", map[n]);
}
return 0;
}

This program was able to compute all solutions in 0.02 seconds.

• Thanks for the correction. But still the main question is about optimization. Its taking at least 3 seconds for small input n=300. Time Limit Exceeded. Sep 23 '16 at 22:35
• Thanks for the help you have done so far! Nice optimization! For input 225604 the above code answers 10. But 56401 ->56400-> 240->16->4 ->2 ->1 ->0 i.e. total of 8 steps are sufficient. And actually I was trying a solution with DP approach but as the question is in "Queue" section, I'm still willing to learn how to apply queue for this problem. No doubt, other approaches will also add to my learning. Sep 24 '16 at 11:58
• @ShridharR.Kulkarni Thanks for that catch. The problem was with if (i*i > MAX) because i was so large that i*i overflowed an integer. I changed the code to fix that by computing maxi = sqrt(MAX); and changing the check to if (i > maxi). See the edit above.
– JS1
Sep 24 '16 at 16:48