IITK1P01-Clash Of Kings--> How to solve?

general
1

Link --> http://www.codechef.com/WPC1401/problems/IITK1P01

What is the required algorithm?

2

I will explain my solution : http://www.codechef.com/viewsolution/4937258 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):

  1. 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.

  2. If number of cities assigned is divisible by 2 => assign it to first king. Choose all remaining cities and take max of recursive calls.

  3. Else => assign to second king. Take minimum.

Encode assigned cities as bitmasks, and store dp values in map<pair<pair<int,int>,int>, int>. Pre-calculate distances using flyod-warshall.

Time: O((kC(k/2))^2*k). The recursive nature and many overlapping states ensure that the solution passes in time.

2 Likes
3

Thank you so much for your explanation. (The code is very well written)
As a side question, in what type of DP problems do you recommend the use of map as opposed to use of a table, for memoization?

1 Like
4

your third state variable=__builtin_popcount(first variable)+ __builtin_popcount(second variable)

1 Like
5

@hippie: Overlooked that in the contest.

You can use it when you know the states that are going to be calculated are not contiguous and very few, like out of 2^12 states for subsets for each type, only very limited were going to be populated, so just optimized it like this instead of declaring (2^12)^2*12 array(which would be too huge).

1 Like