Plij_Hire's blog

Request Approach
By Plij_Hire, history, 8 months ago, In English

There are N buckets arranged in a row. Each bucket either is empty or contains a ball. The buckets are specified as a string buckets consisting of characters "." (empty bucket) and " B " (bucket with aball). For example, for buckets = "B. BB. B. . B" the row of buckets appears as follows: In one move you can take the ball out of any bucket and place it in another (empty) bucket. Your goal is to arrange the balls to create an alternating sequence of full and empty buckets. In other words, the distance between two consecutive balls should be equal to 2 . Note that the sequence may start at any bucket. For example, in the figure below, the balls are placed correctly: On the other hand, in both of the figures below, the balls are placed incorrectly: What is the minimum number of moves required to create a correct sequence of balls in buckets

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Imagine the arrangement of balls in the solved state. There will be one alternating sequence of ....(B.B.B.B.B)..... Now, you can represent this final sequence state with a single variable(say i), the starting index of the first ball in the final arrangement. Now that we are able to represent candidate solutions with just one variable, it's time to choose the best solution from them and the associated cost!

Hint: Choose the best arrangement based on some odd, even prefix counting from within the range where the balls should lie. This can be done in linear time :)

→ Reply