Down to Zero II

Question

Problem : https://www.hackerrank.com/challenges/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 ≤ 10³
0 ≤ N ≤ 10⁶

#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.)

Answer 1

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[300]. 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.