PROBLEM LINK
Contributors
Author: Amit Pandey
Tester & Editorialist: Prateek Gupta
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given two strings X and Y of length N, form another string Z of same length such that the hamming distance(X, Z) + hamming distance(Y, Z) is maximized. If there are many such types of Z possible, print the lexicographically smallest one.
EXPLANATION
Solution for Subtask 1:
This subtask can indeed be solved by Bit Masking. We can generate all possible strings where each character will be either ‘W’ or ‘B’. For each such string, we can track the maximum sum of hamming distances and the corresponding string which gave us the new maximum. In case, we have the same maximum, it is fine to compare the string and store the one which is lexicographically smaller. Lets look at the pseudo code to understand how this works.
F(N, X, Y) {
string Z;
int max_val = -1
for mask in range(0, 2^N) {
string tmp = ""
int hamming_sum = 0
for i in range(0, N) {
if ( bit i is set in mask ) tmp.append('W')
else tmp.append('B')
hamming_sum += (tmp[i] != X[i]) + (tmp[i] != Y[i])
if ( hamming_sum > max_val )
max_val = hamming_sum, Z = tmp
else if ( hamming_sum == max_val )
Z = min(Z, tmp)
}
}
return Z
}
Solution for subtask 2 & 3:
In order to maximize the sum of hamming distance between string (X, Z) and string (Y, Z), we can greedily decide to fill each position of Z with either ‘B’ or ‘W’. At each position, there are only two possible cases for us to consider.
- If X_{pos} and Y_{pos} are same, the best decision will be to insert the character which is not equal to X_{pos} or Y_{pos} since it will fetch you a value of +2 to your sum of hamming distances.
- If X_{pos} is not equal to Y_{pos}, then you can insert any character since it will fetch you a value of +1. But, you also need to make your string Z lexicographically smaller. Hence, you should insert character ‘B’ since ‘B’ < ‘W’ in terms of lexicographical nature.
Fore more details on the implementation of any of the subtasks, have a look at the tester’s solution.
COMPLEXITY
As the string Z can just be found in a single traversal, the overall time complexity of the solution is \mathcal{O}(N).
SOLUTIONS
Setter
Tester’s solution to Subtask 1
Tester’s solution to Subtask 2