Difficulty : medium
Pre-requisites : dp over subset, bitmasking.
Explanation by Amit Saharana
I will explain my solution : which is a minimax dp.
Basically, the first king wants to maximize and second king wants to minimize the finals sum of pairs of distances.
Also k <= 12. Maximum number of possible ways in which we can assign some cities to first king = kC(k/2) <= 12C6 <= 1000.
So, the solution is straightforward : dp(cities assigned to first king, cities assigned to second king, number of cities assigned):
- Base case : If number of cities assigned=k -> calculate pairwise distances using information in cities assigned to first king, second king and return that number.
- If number of cities assigned is divisible by 2 => assign it to first king. Choose all remaining cities and take max of recursive calls.
- Else => assign to second king. Take minimum.
Encode assigned cities as bitmasks, and store dp values in a map.
Pre-calculate distances using flyod-warshall.
Time Complexity: O((kC(k/2))^2 * k).
The recursive nature and many overlapping states ensure that the solution passes in time.
You can also have a look at nicely written tester’s code.
Tester’s solution: link