Problem Statement:
There are 2*N Chess players and N Boards in a chess tournament. The rating of the Chess Player is given by array A . Every player can play only with one player. N board pairing is to be done, and if you match Player i and Player j in the board K, then the Happiness Score increases by K * abs(A[i] - A[j]) * gcd(A[i], A[j]). Find the Maximum Happiness score you can make by designing an ideal pairing. Every player should play a match.
Constraints:
1 <= N <= 10
1 <= A[i] <= 10^6
Here are two solutions
Solution-1: link
Solution-2: link
I think the time complexity of both the solutions are same the only difference between them being the memory optimization.
We can see a relation between board and mask that board = (count of bits in mask) / 2 + 1 (did +1 to convert number of board to 1 based indexing)
Now since for a given mask, board value is fixed, we can drop the board from our dp state.
But doing this will only lead to memory optimisation. Will that lead to any time complexity improvement?
The tutor who taught this problem told that the time complexity of Solution-1 will be O(N^3 * 2^N) while the complexity of Solution-2 will be O(N^2 * 2^N). But I think the time complexity of both the solution should be same as there are same number of recursive calls.
Please correct me if I am wrong.