×

# Contributors

Author: Amit Pandey
Tester & Editorialist: Prateek Gupta

Simple

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

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

This question is marked "community wiki".

20421223
accept rate: 0%

 4 I think I had the correct logic for sub task 2 & 3, however It does not get correct answer. https://www.codechef.com/viewsolution/10209206 What's wrong with this code^? answered 29 May '16, 07:26 21 accept rate: 0% I am not an expert in java. But I can say that you have created $Z[]$ correctly. The answer is $Z[]$ itself. I have no idea what you have done after the forloop to create $Z[]$ as I am not familiar with the syntax of java. (29 May '16, 13:40) debjitdj4★ I converted the array to a string and printed it. (29 May '16, 15:03) Is it really required? I mean, I don't know. I think we can simply print each character. The result will be same if we print a complete string or individual characters one by one without any space. (29 May '16, 16:42) debjitdj4★ Yes, that's true, however it still does not explain why the result is WA. Even if i print the whole string the answer should be correct. (29 May '16, 18:54) Ok, I got it :P. You have to print the output for each test case in a new line. Or just give a space after each output. Bad luck bro... (30 May '16, 05:03) debjitdj4★ I just tried with your code in the practice section by adding a space... https://www.codechef.com/viewsolution/10231723 (30 May '16, 05:05) debjitdj4★ showing 5 of 6 show all
 2 I did the same as it is mentioned above in the subtask 2 https://www.codechef.com/viewsolution/10204950 answered 29 May '16, 01:51 4★debjitdj 465●1●9 accept rate: 31%
 2 Is this a case that printing a string takes more time than printing individual character? Cause TLE on former approach but AC on latter. answered 30 May '16, 00:46 4★gtpan77 21 accept rate: 0% link of the codes? (30 May '16, 00:51) (30 May '16, 03:50) gtpan774★ Using strlen() repeatedly wastes sometime... (30 May '16, 05:34) debjitdj4★ There is a gap of 0.00s and 1.01s (30 May '16, 13:29) gtpan774★ It is actually not 1.01s....it is >=1.01s...that means, the system has stopped the code after 1.01s because the code is taking more than 1s to give the output. (30 May '16, 14:27) debjitdj4★
 0 1 My solution runs in O(n) time aswell and seems simpler. What do you think? (Also, the first 2 conditions can be ignored, as x and y are the same length). Does bitmasking make the above solution more efficient? answered 28 May '16, 23:16 108●2 accept rate: 28%
 0 https://www.codechef.com/viewsolution/10207233 Can you please tell me how can I improve my code so that I don't get a TLE in subtask2 answered 29 May '16, 08:31 2★mvs_217 1 accept rate: 0% Your approach is correct. You can directly print each character without adding it with $K$. (29 May '16, 13:26) debjitdj4★ In Java concatenating String takes more time as each time it creates a new instance of String. You can use StringBuilder in Java for concatenation the string or print each character. (30 May '16, 10:45)

THIS IS MY CODE.. IT RUNS PERFECTLY IN CODEBLOCKS AND OTHER PLATFORMS BUT CODECHEF COMPLAINS OF A RUNTIME ERROR. WHY????

# include <iostream>

using namespace std;

int main() {

int i,k; cin>>k; while(k!=0) { char a[20],b[20]; cin>>a>>b;

for(i=0;a[i]!='\0';i++)
{   if(a[i]==b[i] && a[i]=='W')
{cout<<"B";}

else
{cout<<"W";}
}
cout<<endl;
k--;
}

return 0;

}

1
accept rate: 0%

First of all, why are you taking so small string? The maximum length will be $10^5$, so you should take at least $1$ greater than the maximum possible length.

The second point is, your code will not work. In the case when $a[i]!=b[i]$ the output should be $B$, but in your code, it will give $W$.

(30 May '16, 13:34) 4★

# include<string.h>>

using namespace std;

int main() { int t; cin>>t; while(t--) { char x[100005],y[100005]; char str[100005]; cin>>x>>y;

for(int i=0;i<strlen(x);i++)
{
if(x[i]==y[i])
{
if(x[i]=='W')
str[i]='B';
else
str[i]='W';
}

else
str[i]='B';

}
cout<<str<<endl;;

} return 0; }

why is this ans wrong?

0
accept rate: 0%

What's wrong with this code? Why it shows wrong answer on submission?

# include<stdio.h>

int main() { int t; scanf("%d",&t); while(t--) { int i; char x[1000000],y[1000000]; scanf("%s",&x); scanf("%s",&y); for(i=0;x[i]!='\0'&&y[i]!='\0';i++) { if(x[i]=='B'&&y[i]=='B') printf("W"); else printf("B"); } } return 0; }

2★akjais
1
accept rate: 0%

 0 What's wrong with the code? #include int main() { int t; scanf("%d",&t); while(t--) { int i; char x[1000000],y[1000000]; scanf("%s",&x); scanf("%s",&y); for(i=0;x[i]!='\0'&&y[i]!='\0';i++) { if(x[i]=='B'&&y[i]=='B') printf("W"); else printf("B"); } } return 0; } answered 05 Mar '17, 10:47 2★akjais 1 accept rate: 0%
 0 Make sure you print the output of each test case in a new line. What you're lacking, is a printf ("\n") character at the end of your loop (to make the result of next test case in new line). Eg- If the answer for some X and Y for T=2 is- BBWB WWBB Then your code is printing BBWBWWBB Rectify that and I think you will go fine! :) answered 05 Mar '17, 11:10 15.4k●1●20●66 accept rate: 18%
 0 Here I think that the output of the give testcase can be different also. as mention in the testcase Input: 1 WBWB WBBB Output: BWBW as mentioned here that the maximum hamming distance is 7 but is we are taking a string 'BWWW' it also have the hamming distance is 7 so why it can not be the correct output?? New here please help. answered 06 Apr '18, 09:38 4★adshin21 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,706
×1,004
×126

question asked: 19 May '16, 12:10

question was seen: 3,946 times

last updated: 06 Apr '18, 09:38