ACBALL - Editorial

editorial
, ,
1

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
2

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?

3

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

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

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

2 Likes
5

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

6

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

7

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.

8

I converted the array to a string and printed it.

9

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.

10

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.

11

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
12

link of the codes?

13

https://www.codechef.com/viewsolution/10229707 TLE
https://www.codechef.com/viewsolution/10229757 AC

14

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…

15

I just tried with your code in the practice section by adding a space…

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

16

Using strlen() repeatedly wastes sometime…

17

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.

18

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;

}

19

There is a gap of 0.00s and 1.01s

20

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.