Cut Logs
Ninja is a log cutter. He has a ‘K’ number of axes and an infinite amount of logs. But, Ninja has a log cutting stand that has a capacity of ‘N’, which means he can only try to cut at max ‘N’ logs in one go. All the axes are exactly the same and can cut up to some logs in one go. If we try to cut more logs than its capacity the axe will break.
To improve efficiency, Ninja wants to know how many logs he can cut with an axe in one go without breaking it. But, he wants to know this is the minimum number of moves and in the allotted number of axes.
Can you calculate the minimum number of moves in which Ninja can know the limit of axes?
Some points to notice about axes are:
1. An axe that is used to cut a lesser or equal number of logs than its limit can be used again.
2. An axe that is used to cut more logs than its limit will be broken. Thus, it cannot be used again.
3. All the axes have the same limit of cutting logs until broken.
4. An axe may also cut N logs or may not even cut a single log.
Example
Let the number of axes (K) be 2 & the capacity of the log cutting stand (N) be 6.
From the above example, we can see that the maximum number of moves is 3 for 2 axes and a capacity of 6 logs.
Input format:
The first line of input contains an integer ‘T’ denoting the number of queries or test cases.
The first and only line of each input consists of 2 space-separated integers ‘K’ and ‘N’ denoting the number of axes and the capacity of log cutting stand simultaneously.
Output format:
For each test case, print the minimum number of moves required to know the limit of the axe.
Print the output of each test case in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up
Can you solve this in the worst-case time complexity of N ^ (1/3)
Constraints:
1 <= T <= 10
1 <= K <= 100
1 <= N <= 10000
The very first approach can be to try cutting logs and find the one with the minimum number of moves.
- The idea is to use recursion to reduce the big problem into several small subproblems.
- We will try to cut each possible number of logs and get the answer for checking the remaining number of logs.
- The algorithm for the following will be:
cutLogs( K, N ):
- If N <= 1 or K <= 1, return N.
- Initialize a variable ans = N
- Loop for ( i=1; i <= N; i++ ):
- Initialize cur = max of
- cutLogs(K-1, i-1), (If axe couldn’t cut i logs)
- cutLogs(K, N-i) ( If axe could cut i logs)
- Initialize cur = max of
- Minimize the answer i.e. ans = min( ans, cur )
- Return answer + 1
We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. This means, in this approach, we will eliminate the need for solving the same subproblems again and again.
To optimize the overlapping sub-problem calculation, we will use memoization by storing answers for each recursive state.
- The idea is to use memoization.
- Create a lookUp table with K + 1 rows and N + 1 columns to store the answers to the subproblems where lookUp[ i ][ j ] denotes the minimum number of moves required when we have i axes available and with j capacity of log cutting stand.
- Initialize the lookUp array with -1 which denotes that it is not calculated yet.
- We will call a helper function that returns us the minimum number of moves required.
- The algorithm for the helper function will be as follows:
cutLogsHelper( K, N ):
- If N <= 1 or K <= 1:
- Return N
- If lookUp[K][N] != -1:
- Return lookUp[K][N]
- Initialize a variable ans = N
- Loop for ( i = 1; i <= N; i++ ):
- Initialize cur = max of
- cutLogsHelper(K-1, i-1), (If axe couldn’t cut i logs)
- cutLogsHelper(K, N-i) ( If axe could cut i logs)
- Initialize cur = max of
- Minimize the answer i.e. ans = min( ans, cur )
- lookUp[K][N] = ans + 1
- Return lookUp[K][N]
Initially, we were breaking the large problem into small problems but now, let us look at it differently. Let us solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now.
- The idea is to create a DP table with K+1 rows and N+1 rows.
- Initialize DP[i][j] = j
- The algorithm for filling DP table is as follows
- Loop for( i=2; i <= K; i++ ):
- Loop for( j=2; j <= N; j++):
- Loop for( t=1; t <= j; t++ ):
- Initialize cur = max(
- DP[i - 1][t - 1], (If axe couldn’t cut i logs)
- DP[i][j - t] (If axe could cut i logs)
- )
- Minimize DP[i][j] = min( DP[i][j], cur )
- Initialize cur = max(
- DP[i][j]++, for checking 1 floor
- Loop for( t=1; t <= j; t++ ):
- Loop for( j=2; j <= N; j++):
- Return DP[K][N]
It is similar to the previous approach but in the previous approach, we are finding the point with the minimum required moves in a loop. But, in this approach, we will optimize that.
As, in the loop the first value i.e DP[i - 1][t - 1] (If axe couldn’t cut i logs) is increasing and the second value i.e DP[i][j - t] (If axe could cut i logs) is decreasing. So, we can find the optimum point using a binary search.
If we observe that each row in DP[ K ][ N ] is an increasing function in N. So, the optimal answer for current iteration will be greater than or equal to answer of the previous iteration. So, we will use this property to optimize the previous approach.
Algorithm:
- Create a DP array of size N+1.
- Initialize DP[i] = i
- Loop for( i=2; i <= K; i++ ):
- Create a DP2 array of size N+1 containing 0’s.
- Initialize t = 1
- Loop for( j=1; j <= N; j++):
- Loop while(t < j and max(DP[t - 1], DP2[j - t]) > max(DP[t], DP2[j - t - 1]):
- t++
- DP2[j] = 1 + max(DP[t - 1], DP2[j - t])
- Loop while(t < j and max(DP[t - 1], DP2[j - t]) > max(DP[t], DP2[j - t - 1]):
- Update DP = DP2
- Return DP[N]
Now let's just solve the problem in another way. Previously we were solving the problem for K axes and N log cutting capacity. Now let's just calculate what is the maximum number of log capacity we can check with K axes in each move. So, our recurrence relation will be:
f(T, K) = f(T-1, K-1) + f(T-1, K) + 1
Using this recurrence relation we can answer each test case in worst-case time complexity of √N
First, let’s discuss some optimizations we are going to use.
- For K = 1, the answer will always be N.
- For K = 2, the answer can be calculated using the following approach:
In x moves with 2 eggs, we can check a capacity of (x × (x + 1)) / 2. Thus we get our equation to be. Solving this equation we get
x = ceil( ( -1 + √(1 + 8 × N) ) / 2 )
- The maximum number of axes used will be equivalent to the number of moves. And if we have more axes than log2N then we can check the capacity of N in the minimum number of moves, that is log2N.
- We will pre-compute the DP table which has log2N rows and the number of columns will be different for each row as the maximum capacity is N. Initially, all rows will have 1 column containing 0. We will answer each test case using a binary search
The algorithm to pre-compute DP tables is as follows.
- Loop for(i=0; 1; i++):
- cur = DP[3][i] + (i * (i + 1)) / 2 + 1
- [3].push_back(cur)
- If cur >= 1e18:
- break
- Loop for( i=4; i <= 60; i++ ):
- Loop for( j=0; 1; j++):
- cur = DP[i][j] + DP[i-1][j] + 1
- DP[i].push_back(cur)
- If cur >= 1e18:
- break
- Loop for( j=0; 1; j++):
Now as we have our DP table ready where row number defines the number of available axes and column number defines the number of required moves and entry in each cell defines the maximum number of cutting capacity it can check.
To answer each test case we will just find the entry in the Kth row which is greater than or equal to N.
The algorithm for the same is as follows.
- If K == 1:
- Return N
- If K == 2:
- Return ceil((-1.0 + sqrtl(1 + 8 * N)) /2.0)
- Update K = min( K, log2N )
- ans = DP[K].lower_bound(N) - DP[K].begin()
- Return ans