Power Programmer

The idea is to find a suitable rearrangement of S1, S2, and S3 such that their Bitwise XOR value is maximized using Dynamic Programming. The subproblems can be stored in a dp[][][][] table where dp[i][o1][o2][o3] stores the maximum XOR value up to position N-1 starting from the index i, where o1 is, o2 and o3 are the number of 1s still remaining to be placed in strings S1, S2 and S3 respectively.

There can be four cases possible at any position i from 0 to (N – 1):

Assign 1s to all the three strings
Assign 1s to any two strings
Assign 1s to any one of the strings.
Assign 0s to all the strings.
From the above possible cases for each position, calculate the maximum Bitwise XOR obtainable from the four possibilities:

Follow the steps below to solve the problem:

Initialize a table dp[][][][] to store the number of ones in S1, S2 and S3 for the positions i from 0 to N-1.
The transition states is as follows:
dp[i][o1][o2][o3] = max(dp(assign 1s to all three strings), dp(assign 1s to any of the two strings), dp(assign 1s to any one string), dp(do not assign 1 to any string)) where,

i = current position
o1 = remaining ones to be placed in the string S1
o2 = remaining ones to be placed in the string S2
o3 = remaining ones to be placed in the string S3

Solve the subproblems for all cases using the above transition and print the maximum XOR value amongst them.

Tip 1 : use nested query