MERGEBS - Editorial

editorial
, , ,
33

my resultant string for the above case formed is 110000101010
and answer = 20.
can you provide the resulting string?

34

My greedy solution works on the test cases given in comments. I calculated which ‘1’ brings how many inversions for both strings, then greedily added the ‘1’ with higher inversions to my answer string. I calculated the total inversions in the answer string and i dont recognize the flaw. Can anyone please point it out.

Solution Link: CodeChef: Practical coding for everyone

35

Check this testcase:
1
9
010010110
001101100
Answer: 28
Your code’s output: 29

36

1
9
010010110
001101100

37

Try the following test case:

1
5
11000
10010

Answer: 15
Merged string: 1001100010

39

Because you can only choose one string to choose an element and place that element in the merged string. Suppose A is 0101 and B is 1010. Now Suppose you have merged till i=2 and j=2 based on 1-based indexing. Now you need to choose the next element to be a part of the merged string which will be either A[i+1] or B[j+1]

40

but my solution with choosing both works, and i think it should because it does not violate any condition given in the question.
My Solution

41

Brother, can you please explain the recursion steps.
Thanks

43

@devapriyanta Sure I will try my best…

We store 3 things at each step of recursion –

  1. next index that we can choose from string a (inda)
  2. next index from string b (indb)
  3. the number of 1s we have seen till now(cnt1).

At each step, we have two choices –
1.take next element from a(a[inda])
2.take next element from b(b[indb])

If a[inda] is 1, it will never contribute to be an inversion because all elements to its left can either be 0 or 1(01 or 11 so no inversion). Hence we just do cnt1 + 1 as the count of 1 increases by 1 and we will now take the next element from a (inda + 1).

If a[inda] is 0, the number of inversions will be cnt1(the number of 1s before this 0). We add this to our answer and then again recurse by doing inda + 1. We do not increase cnt1 as the current element is 0 and the number of zeroes remains the same.

We do the same thing for string b.
Finally, we take the minimum value out of these two choices and make it the final answer.

44

I too did top down dp which is very similar to your solution. But I am getting WA on one test case. It must be a very silly mistake. Can you please help me? CodeChef: Practical coding for everyone

46

Try this test case:

2
3
011
110
6
000100
011010

Now invert both the test case and try:

2
6
000100
011010
3
011
110

and see how your answer is changing for n = 3 test case.

47

My Code is not giving Correct Output. But where i am wrong , I am not able to figure out.

What I am doing here is

1. If starting character of both the string is '1', then i am taking both one 
by one and then taking the minimum of both. and same thing for the 
character are '1'

    if(a[i] == b[j])
    {
        int op1 = solve(a,b,c+a[i],i+1,j);
        int op2 = solve(a,b,c+b[j],i,j+1);
        return dp[i][j] = min(op1,op2);
    }
2. Second thing that i am doing here is if both the characters differes 
then we will take '0' first because it will reduce count inversions.
       if(a[i]=='0')
        {
            return  dp[i][j] =  solve(a,b,c+a[i],i+1,j);
        }
        if(b[j]=='0')
        {
            return  dp[i][j] =  solve(a,b,c + b[j], i ,j+1);
        }
3. Once one of the string exhauseted I am appending the other string 
and finding the inversion. 
I Know that Time Limit is going to definitaly exceed, but trying to find 
where I am gone wrong.