KAN13H - Editorial

PROBLEM LINK:

Practice
Contest

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.

//