You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 19 May '16, 12:10

prateekg603's gravatar image

5★prateekg603
20421223
accept rate: 0%

edited 28 May '16, 23:23


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

link

answered 29 May '16, 07:26

yashmundra13's gravatar image

1★yashmundra13
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) yashmundra131★

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) yashmundra131★

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

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

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

link

answered 29 May '16, 01:51

debjitdj's gravatar image

4★debjitdj
46519
accept rate: 31%

edited 29 May '16, 01:54

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

link

answered 30 May '16, 00:46

gtpan77's gravatar image

4★gtpan77
21
accept rate: 0%

link of the codes?

(30 May '16, 00:51) amitpandeykgp4★

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★

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?

link

answered 28 May '16, 23:16

coderaashir's gravatar image

4★coderaashir
1082
accept rate: 28%

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

link

answered 29 May '16, 08:31

mvs_217's gravatar image

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) ankurverma19944★

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;

}

link

answered 30 May '16, 12:06

mondalsourav's gravatar image

3★mondalsourav
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) debjitdj4★

include <iostream>

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?

link

answered 23 Nov '16, 17:08

sagarpant74's gravatar image

1★sagarpant74
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; }

link

answered 05 Mar '17, 10:45

akjais's gravatar image

2★akjais
1
accept rate: 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; }

link

answered 05 Mar '17, 10:47

akjais's gravatar image

2★akjais
1
accept rate: 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! :)

link

answered 05 Mar '17, 11:10

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

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.

link

answered 06 Apr '18, 09:38

adshin21's gravatar image

4★adshin21
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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