Not satisfied after authoring two problems that ask for the best $$$k$$$ solutions (HuronForces from Donald Knuth 2021 and Best Tests from ICPC Mexico Repechaje 2024), here is another problem that asks for the best $$$k$$$ solutions:
José Juan is on vacation again and bought $$$n$$$ souvenirs for his two best friends. There are $$$n$$$ types of souvenirs in the souvenir shop. Juan wants to distribute the $$$n$$$ souvenirs between his two friends. He thinks that if he gives the $$$i$$$-th souvenir to his first best friend, it will give him $$$a_i$$$ units of happiness. Similarly, if he gives the $$$i$$$-th souvenir to his other best friend, it would give him $$$b_i$$$ units of happiness.
The distribution of the souvenirs might introduce envy in his friends, so he wants to determine the distributions of souvenirs that have the minimum absolute difference of the total happiness given to his friends.
Find the $$$k=2^{min(n,20)}$$$ distributions with the minimum absolute difference of the happiness of the two friends. Each of the souvenirs must be given to exactly one of the friends.
The first line contains one integer $$$n$$$ ($$$1\leq n \leq 40$$$) $$$-$$$ number of souvenirs in the souvenir shop.
The second line contains $$$n$$$ integers $$$a_i$$$ ($$$|a_i| \leq 10^{16}$$$) – happiness given to the first best friend of José Juan by each souvenir.
The third line contains $$$n$$$ integers $$$b_i$$$ ($$$|b_i| \leq 10^{16}$$$) – happiness given to the second best friend of José Juan by each souvenir.
Print $$$2^{min(n,20)}$$$ integers – the difference of happiness given to José Juan's best of the best distributions of souvenirs sorted in increasing order.
4 1 2 3 4 4 3 2 1
0 0 0 0 0 0 5 5 5 5 5 5 5 5 10 10
2 -1 10 -1 10
9 9 11 11
