Clash of Kings - Editorial

editorial
, , , ,
1

Problem link : contest
practice

Difficulty : medium

Pre-requisites : dp over subset, bitmasking.

Solution :

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

2

@amitsaharana Well explained and written solution. Only thing which I couldn’t digest was the difficulty level.

3

This is why the editorial is put up in community wiki :slight_smile: I have edited it.

4

I’ve mentioned it before also,
the no. of state variables can be reduced from three to two,
by writing:
no. of cities assigned = __builtin_popcount(mask1) + __builtin_popcount(mask2)

here is my AC code implementing the same:-
http://www.codechef.com/viewsolution/4942559