FLAASH - Editorial

PROBLEM LINK:

Practice
Contest

Author: Varun Singh

DIFFICULTY:

SIMPLE

PREREQUISITES:

DP

PROBLEM:

Given a number n, count minimum steps to reach 1 according to the given criteria.

EXPLANATION:

One can think of greedily choosing the step, which makes n as low as possible and continue the same, till it reaches 1. If you observe carefully, the greedy strategy doesn’t work here.

Eg: Given n = 10 , Greedy → 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 ( 4 steps ).

But the optimal way is → 10 -1 = 9 /3 = 3 /3 = 1 ( 3 steps ).

So, we need to try out all possible steps we can make for each possible value of n we encounter and choose the minimum of these possibilities.

It all starts with recursion.
F(n) = 1 + min{ F(n-1) , F(n/2) , F(n/3) } if (n>1) , else 0 ( i.e., F(1) = 0 )

We notice in the recurrence relation that the problem exhibits the property of overlapping subproblems and optimal substructure, so DP.

#include <bits/stdc++.h>
#define sz (int)1e6
using namespace std;
int getminsteps(int n, int *memo)
{
  if( n == 1) return 0;                   // Base Case
  if( memo[n] != -1)  return memo[n];     // Solved it. Return ans
  int r = 1 + getminsteps(n-1,memo);      // Regular steps. From n to n-1
  if(n%2 == 0)
    r = min(r,1+getminsteps(n/2,memo));   // Divisible by 2 steps
  if(n%3 == 0)
    r = min(r,1+getminsteps(n/3,memo));   // Divisible by 3 steps.
  memo[n] = r;                            // Save the result. If we forget this, then plain recursion
  return r;
}
int main()
{
    int t,n,i,ans;
    cin >> t;
    int memo[sz];                       // DP
    memset(memo, -1, sizeof(memo));     // Fill all elements with -1 i.e not solved yet
    while (t--)
    {
        cin >> n;
        ans = getminsteps(n,memo);
        cout << ans << endl;
    }
    return 0;
}

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.