FifthThread's blog

Google Online Assesment Question
By FifthThread, 3 years 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

Comments Comments (6)
| Write comment?
»
3 years 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].

→ Reply
»
3 years 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).

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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).

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
»
3 years 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
→ Reply