CROSSOVER - The Crossover

no tags 

Scientist Aftab has made a groundbreaking discovery regarding chromosomal crossover today!

Before going into details let’s understand a few definitions first. According to Holland’s convention, a gene is represented by either 0 or 1. A chromosome is a string of genes. While in crossover, two parental chromosomes arbitrarily get separated at the exact same position forming four non-empty parts.  And these parts join together to form two offspring. For example, let A and B be two parental chromosomes of length N. After cutting those at arbitrary position X, we get four parts LA, RA, LB, RB. Here LA is made of A[0,…,X], RA is made of A[X+1,…,N-1] and the same for LB and RB. After applying crossover, we get two offspring O1=LA+RB andO2= LB+RA. Here ‘+’ is string concatenation operator.

Scientist Aftab’s claim is that, the fittest offspring among O1 and O2 is the one which is greater in value. Here the value of a chromosome is computed keeping in mind that this is a bitstring with the leftmost bit being the Most Significant Bit (MSB) and the rightmost bit is the Least Significant Bit (LSB).

Although scientist Aftab is a great genetics researcher, he is not good at handling chromosomes of large size. So he is seeking your help. You will be given two chromosomes of length N. And you will have to output the decimal value modulo 109+7 of the fittest offspring after applying crossover.

Input

Input starts with an integer T(<=30), denoting the number of test cases. Each case contains two lines containing two strings of same length N (2<=N<=100000). Strings will contain only 0’s and 1’s.

Output

For each case of input, print the case number followed by the decimal value modulo 109+7 of the fittest string after the crossover.

Sample I/O

Input

Output

2

100101

110010

10010

11101

Case 1: 53

Case 2: 30

 

Explanation of Sample I/O

For the first case, the fittest offspring is 110101, whose decimal value modulo 109+7 is 53.


hide comments
akshayvenkat: 2016-11-08 20:14:28

@Sourav Sen Tonmoy, could you please check my submission? 25+ WA's now, its getting very frustrating.

akshayvenkat: 2016-11-07 02:45:46

I am getting every answer right for all randomly generated strings, the ones in toolkit, and also for the cases provided by @matematikaadit. Still getting WA. Can someone help? Is there any corner case?

Doubt1: Long Long is enough for the answer, right?

Last edit: 2016-11-07 02:46:23
:D: 2016-10-01 20:31:33

Nice question. Requires careful analysis of all the scenarios. If anyone is having trouble with WA, please test with brute force. BF here is simply checking all valid partitions and getting the max value out of all of them. And since inputs are binary strings, you can quickly test all valid test cases up to length of 10 or so. It should guarantee you test all possible scenarios. Also remember partitions must be non-empty and we're looking for biggest value BEFORE modulo operation.

matematikaadit: 2016-05-06 09:18:01

For those who still got WA. Try a few simple test case below:
10
00
00
01
00
10
00
11
00
01
01
10
01
11
01
10
10
11
10
11
11

the output should be:
Case 1: 0
Case 2: 1
Case 3: 2
Case 4: 2
Case 5: 1
Case 6: 3
Case 7: 3
Case 8: 2
Case 9: 3
Case 10: 3

it_is_me: 2016-05-01 19:46:10

@Sourav Sen Tonmoy can you please tell some test where one might make mistakes getting WA again and again.

naruto09: 2016-04-28 12:16:45

@Sourav can you please check my submission once...I keep getting WA and TLE

Last edit: 2016-04-28 12:59:18
Purav Shah: 2016-04-28 10:27:46

@Sourav are the solutions rejudged, since my AC solution became WA. Please check submission ID 16825716.

Edit: Got AC
Consider the two halves after the cut are always non-empty!!

Last edit: 2016-04-28 18:35:01
Sourav Sen Tonmoy: 2016-04-28 10:25:45

Jubayer Nirjhor suggested a couple of critical cases, which I've missed previously. I've updated the dataset accordingly and rejudged all the submissions. Sorry for the inconvenience.

Sourav Sen Tonmoy: 2016-04-27 19:11:32

I just removed the problem statement from the "classical" section to "none" for testing. Then after adding it back to the classical section, all the comments on this thread disappeared. Ridiculous. -_- Sorry about that BTW.


Added by:Sourav Sen Tonmoy
Date:2016-04-25
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own problem. Used in NHSPC 2016 Final Round. More about NHSPC: http://www.nhspc.org/