FameOfTheLegends's blog

By FameOfTheLegends, 12 days ago, In English

Question 1 — N boxes are Arrranged in a line. Each box is colored either with white or black. You can select any number of boxes from the starting and put it behind the last box in the same sequence as it was placed initially. you can perform this operation atmost once. For example string s="wbbb" . In one operation you can select "wb" and from the start and put it behind the last box "b".

Note: you cannot select all the n boxes.

You are required to find the minimum number of boxes whose colors must be reversed so that all the boxes in the sequence are of an alternate color, that is any two adjacent boxes are of different colors.


Input : 5 wwwwwbbww wwwb bwww wwww bbbbb Output : 3 1 1 2 2

I was thinking of brute forcing the solution, that is doing operation for each length and then calculating for that configuration. Can anyobody tell the correct approach

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
12 days ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Append string to itself and use sliding window of size N , and calculate each window the transition required to convert, now while moving the window you could also manage the dp states , dp will be minimum operation required to convert current window that is ending at index i and such that ith character is W or B, and before that there is alternating sequence for the range [i-N+1,i].

»
12 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Let pref[i][0] show the minimum number of flips to make the characters [0, i) alternating while the first character itself being W. pref[i][1] shows the same thing but the first character needs to be a B there. Do this calculation for all suffix too, where suff[i][0] shows the characters [i, n) alternating while the last one is W and suff[i][1] for the last one being B. Those calculations are O(n). Then the answer is minimum of min(pref[i][0] + suff[i+1][0] + 1, pref[i][1] + suff[i+1][0], pref[i][0] + suff[i+1][1], pref[i][1] + suff[i+1][1] + 1) for all i. This is also O(n).

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I want to ask you 2 things:-

    1. pref[i] contains [0,i) while suff[i] contains [i,n) and in the end you're checking for pref[i]+suff[i+1], which means you're not considering ith character at all.
    2. When we're appending an alternating prefix which starts with 'W' to an alternating suffix which ends with 'W' (for ex ...BWBWBW + WBWBWB...) then I believe the characters of at least one of the string should be flipped (i.e....BWBWBW + BWBWBW... or ...WBWBWB + WBWBWB...) which may cost more than 1 depending on the length and values of pref[i] and suff[i].

    Please correct me If I'm wrong or If I missed something.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Correct, my bad.

      1. Should be pref[i]+suff[i]

      2. Now I think about it, I believe you don't need to check for +1 cases (do you? I might look into it later).

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think we need to consider them. And the cost should depend on the relation between two numbers X and Y where X is number of operations required to form an alternating string S while Y is the number of operations required to from the counter alternating string of S (Sorry couldn't find a better word) and If I'm not wrong, the relation should be Y = len(S)-X.

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone verify if my code is right? Or missing some edge cases?

My idea: lets take wwwb as e.g. Moving prefix back is essentially duplicating the front part back which gives me the string wwwbwww. The target strings are wbwbwbw or bwbwbwb Using sliding widown we calculate the min of changes.

Code
»
11 days ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

it's very easy
1. pre-compute suffix array cost making wbwbwb and bwbwbw.

  1. iterate 1 to n, also simultanously compute cost for prefix wbwbw and bwbwbw.
    -> ans = min(ans ,prefix cost of starting with w and prefix end with b )
    -> ans = min(ans ,prefix cost of starting with b and prefix end with w )
code
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What we can do is brute force the solution. We can one by one remove from the i length substring from the beginning and add it to the end, not in the literal sense but we can simulate so by keeping count of the number of black and white balls present in the even and odd positions. And suppose the original string is bwwwb. (consider 1 indexing) odd => b = 2 , w = 1 even => b = 0, w = 2 If we remove substring of length 1, then the string will become wwwbb and even=> b = 1 , w = 1 odd=> b = 1, w = 2 . We can calculate them easily by keeping prefix sums of black and white respecitvely. And for each configuration, we can calculate the answer for that configuration by min(even) + min(odd)

And we take minimum for all possible configutations

time complexity : O(n)