KAN13A - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dr. Mustaq Ahmed
Tester: Jingbo Shang
Editorialist: Jingbo Shang

DIFFICULTY:

Easy - Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a M×N matrix Price (M days, N types) indicating the price of each model of hard disk on each day, find out the minimum cost to have exact one disk per day. The price of selling an older one is 100 less than the current buying price.

EXPLANATION:

Let’s use OPT[D][T] to state the minimum cost if D days passed and we have disk T in the end.
From this state, we can enumerate the next selling/buying day D’ and the new model T’. That is,
OPT[D’][T’]= Price[D’][T’]+min_(D<D’,T’≠T)⁡{OPT[D][T]–Price[D’][T]+100}
This dynamic programming is O(N^2 M^2), which will get TLE.

We should observe that if we known T, we will definitely choose min_(D<D’) {OPT[D][T]}, denoted as G[D’][T]. Therefore, we can use this G[][] array to optimize the solution to O(N^2 M)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

How the answers to the 1st and 2nd test case are 3400 and 4500. I think it should be 3500 and 4800.
Can anyone explain me. Thankyou…