ACBALL - Editorial

PROBLEM LINK

Practice

Contest

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

1 Like

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?

I did the same as it is mentioned above in the subtask 2

https://www.codechef.com/viewsolution/10204950

1 Like

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^?

2 Likes

CodeChef: Practical coding for everyone Can you please tell me how can I improve my code so that I don’t get a TLE in subtask2

Is this a case that printing a string takes more time than printing individual character?
Cause TLE on former approach but AC on latter.

1 Like

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

#include
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;

}

#include
#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?

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;
}

What’s wrong with the code?

#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;
}

@akjais-

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! :slight_smile:

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.

Your approach is correct. You can directly print each character without adding it with K.

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.

I converted the array to a string and printed it.

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.

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.

link of the codes?

CodeChef: Practical coding for everyone TLE
CodeChef: Practical coding for everyone AC

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…