Magnets
Time limit1sMemory limit128 MB
Given N unit magnets that auto-merge based on adjacent poles, find the minimum number of flips needed to create a merged magnet of exact length L.
- Level
Medium6 of 10
- Topics
- Greedy, Simulation, Array
- Solved
- No attempts yet
Problem
Donghyuk has N small bar magnets, each of length 1. Each magnet has different poles, N and S, at its left and right ends. The input gives each magnet's left-to-right pole order as either NS or SN.
Two neighboring magnets stick together when the two ends facing each other have different poles; they do not stick when those poles are the same. The magnets are so strong that once two magnets stick together, they cannot be separated. When the experiment starts, all neighboring magnets that can stick together do so, forming longer magnets. A magnet formed this way is still treated as one magnet, and that whole magnet may be flipped. Flipping a magnet swaps its left and right poles. After a flip, if it can stick to a neighboring magnet, it sticks immediately.
The following is a layout of 6 magnets before the experiment starts.
After the experiment starts, the fourth and fifth magnets stick together as shown below.
Given the initial layout, find the minimum number of flips needed to obtain a magnet whose length is exactly L. The input is guaranteed to be a case where such a magnet can be obtained.
Input
The first line contains the number of magnets N and the desired length L. (1 <= N <= 500000, 1 <= L <= N)
The second line contains N strings, each either NS or SN, describing the initial layout of the magnets.
The input is guaranteed to have an answer.
Output
Print the minimum number of flips needed to make a magnet whose length is exactly L.