Friday, 26 August 2016

Colored Balls


Hello all, all of us have curiosities and we look on internet to find informations about it. In last time I just reflected over this topic. Today I am gonna show you aa new problem about Mr. Algorithm and a game with black and white balls.
If you know to solve this exercise and you think someone does not, then I invite you to be the first who give me the correct answer!


Mr. Algorithm has many balls of white and black colors. One day, he was playing with them. During the play, he arranged the balls into two rows both consisting of N number of balls. These two rows of balls are give to you in the form of strings X, Y; Both these strings consist of 'W' and 'B', where 'W' denotes a white colored ball and 'B' a black colored.
Other than these two rows of balls, Mr. Algorithm has an inifinite supply of extra balls of each color. He wants to create another row of N balls, Z in such a way that the sum of hamming distance between X and Z, and hamming distance between Y and Z is maximized.
Hamming Distance between two strings X and Y is defined as the number of positions where the color of balls in row X differs from the row Y ball at that position (e.g. hamming distance between "WBB", "BWB" is 2, as at position 1 and 2, corresponding colors in the two strings differ).
As there can be multiple such arrangements of row Z, Mr. Algorithm wants to find the lexicographically smalles arrangement which will maximize the above value.

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
- first line of each test will contain a string X denoting the arrangement of balls in first row.
- second line will contain the string Y denoting the arrangement of balls in second row.

For each test case, output a single line containing the string of length N denoting the arrangement of colors of the balls belonging to row Z.
1 <= T <= 3
1 <= N <= 10^5




You will learn the following in this exercise:
- string manipulation
- game theory
- probabilities

If you don't know to solve this exercise, you can buy my solution for just $1 (check bellow PayPal buttons): 

Join our community:
Google Plus


No comments:
Write comments