#Lanku and Mysterious Cities
#Problem Link:
Contest
Practice
Author: Kunal Keshwani
Tester: Mayur Gajabi, Md Shakim
Editorialist: Kunal Keshwani
#Difficulty:
Medium
#Prerequisites:
Dynamic Programming
#Problem:
You have been given two integers N and K. These N integers correspond to N cities. The locations and entry fee associated with N cities are given. Now your objective is to choose K cities as capital and assign every city to exactly one capital city such that following function F is minimized:
C[i] = cost to travel from ith city to its assigned capital city + fee to enter its assigned capital.
F = C[1] + C[2] + … C[N]
#Quick Explanation:
First, we will sort the cities according to their locations. We can maintain DP[i][j] which will tell us the minimum value of the function F in which j capital cities are chosen till now out of i cities.
We will precompute on all pair of i, j that which is the optimal city between i and j to be made as capital, calculate the cost of it and store it in cost[i][j].
Now it is easy to calculate that, DP[i][j] = min(DP[i][j], DP[p][j - 1] + cost[p + 1][i]) where p will vary from j - 1 to i.
#Explanation:
Its obvious that this cannot be solved using a greedy solution. So we will start by thinking a Dynamic Programming solution.
We will apply dynamic programming on cities where cities are sorted by their location.
Why should we consider cities sorted by their location and not by their entry fees or any other criteria??
First try to answer this question.
Your objective is to select K cities such that function F is minimised.
Lets forget the entry fees for now , There are only three cities x , y and z in the country and you need to select only 2 cities as capital (K = 2).
If city x , y and z are located at locations locX , locY and locZ where locX < locY < locZ. Then we can never have a scenario where:
1.city y and z are capital and city x is assigned to z.
2.city x and y are capital and city z is assigned to x.
This observation gives us feeling that we should consider capitals in sorted order only.
Consider another example:
There are N cities and we need to select 3 cities (K = 3) as capital.
Lets sort all the cities in the ascending order of their location.
City 1 City 2 ……. …… …. City x …. … … …. City y …. …. … City z …. … …City N.
If we select City x , City y and City z as capital cities (as K = 3) then in the optimal scenario:
-
All the cities from [1,x-1] should be assigned to City x.
-
All the cities from [z+1,N] should be assigned to City z
-
All the cities from [x+1,y-1] should be assigned to City x or City y
-
All the cities from [y+1,z-1] should be assigned to City y or City z.
Now we know how to approach this question when there is no entry fees involved.
Lets consider the entry fees.
The tricky part is to understand that this property still holds even if we consider entry fees.
You will find that our property will still hold.( Prove it yourself).
So from here we will consider cities as sorted on basis of their location
Next part is to frame our Dynamic Programming.
Our DP will have only 2 states
1.Number of cities visited (i)
2.Number of cities selected as capital (j)
DP[i][j] represents the minimum possible value of the function F if there are i cities in the country and we want to select only j cities as capital.
Hence , our final answer will be DP[N][K].
What we should focus on is how to find the value of DP[i][j] from its previous states.
To do this, we should do some precomputation to find cost[i][j] which is the minimum cost to make exactly one capital between cities i and j. Now to precompute it, we will iterate all the cities between i and j and make each city a capital, then from all the cities we will take the one with the minimum cost .
But this will take O(n^4) which we will time out by naive method.
We can optimise it and can solve it in O(n^3). By find the travelling cost using another dp[n][n][n] array.
After finding the cost[i][j], DP[i][j] is easy to find.
Consider the transition DP[i][j] = min(DP[i][j], DP[p][j - 1] + cost[p + 1][i]) where p will vary from
j - 1 to i.
This transition can be explained like this, to find minimum value of function F upto i cities and j capitals, we can calculate it using all the cities that comes before city i and we have chosen j - 1 capitals which is represented by
DP[p][j - 1] (p will iterate from j -1 to i) . Now we have to add another capital between p + 1 and i to make a total of j capitals from i cities.
Remember, we have already precomputed it in cost[i][j] which is the minimum cost of adding one capital between city i and j so we will add cost[p + 1][i].
So now we can easily find DP[i][j] from its previous states.
The complexity of this solution is O(n ^ 3 + n * k * n) which will pass under given constraints.
#Author’s and Tester’s solutions:
