PROBLEM LINK:
Author: Dr. M Kaykobad
Tester: Jingbo Shang
Editorialist: Jingbo Shang
DIFFICULTY:
Easy – Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given a method to solve the p-peg Hanoi Towers of n plates, determine after how many steps should be done in the optimal solution before the k-th smallest plate is placed in its final position.
EXPLANATION:
First of all, we can calculate the optimal steps needed for (n,p) system, following the formula stated in the description:
Then, we can calculate the answer by adding a dimension:
Therefore, we can get the answer in O(NPK) time for all answer. Note that we need using long long to store our answer here.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.