2009 Canadian Computing Competition, Stage 2

Day 1, Problem 2: Dinner

On the way to dinner, the CCC competitors are lining up for their delicious curly fries. The N (1 ≤ N ≤ 100) competitors have lined up single-file to enter the cafeteria.

Doctor V, who runs the CCC, realized at the last minute that programmers simply hate standing in line next to programmers who use a different language. Thankfully, only two languages are allowed at the CCC: Gnold and Helpfile. Furthermore, the competitors have decided that they will only enter the cafeteria if they are in a group of at least K (1 ≤ K ≤ 6) competitors.

Doctor V decided to iterate the following scheme:

• He will find a group of K or more competitors who use the same language standing next to each other in line and send them to dinner.
• The remaining competitors will close the gap, potentially putting similar-language competitors together.

So Doctor V recorded the sequence of competitors for you. Can all the competitors dine? If so, what is the minimum number of groups of competitors to be sent to dinner?

Note: Test cases worth 60% of the points have K ≤ 2. Out of these, on test cases worth one third of the points (20% of the total points), N ≤ 10.

Input

The first line contains two integers N and K.
The second line contains N characters that are the sequence of competitors in line (H represents Helpfile, G represents Gnold)

Output

Output, on one line, the single number that is the minimum number of groups that are formed for dinner. If not all programmers can dine, output -1.

Sample Input

7 2
GHHGHHG

Sample Output

3

Explanation

There are seven competitors: a Gnold programmer followed by two Helpfile programmers, followed by another Gnold programmer, followed by another two Helpfile programmers followed by a final Gnold programmer. Programmers want to go to dinner in pairs.

First send the first pair of Hs to dinner, leaving GGHHG. Then send the second pair of Hs to dinner, leaving GGG; finally, send in the group of Gs. It might be coincidental that the two pairs of Helpfile programmers entered the cafeteria successively.

All Submissions
Best Solutions

Point Value: 40 (partial)
Time Limit: 1.00s
Memory Limit: 128M
Added: Jun 06, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

there is a solution with 0.06 second runtime vs. >1.0 solutions for others
This is because solutions that store the minimum number of moves as part of the state are wasting time and memory. It is only neccessary to determine if it is possible to solve or not.

If you only know that it is possible, it is easy to quickly find the minimum number of moves it takes to solve it (determining if it is possible for a million people would take forever, but you could quickly find out the minimum number of moves after being told there was a valid grouping, even for a million people)

E.g. if you knew it was possible for GHHGHHG(odd # of groups), it is best to remove the end groups last (since that could always be done later on without making the solution worse). Removing from the middle will always reduce the total number of groups by two(eliminating one and merging two).
There are originally 5 groups. Removing from the middle 2 times and the ends once gives 3 moves
For GHHGHH(even # of groups), it is a bit different(4 groups, but remove from middle once and ends twice, also 3 moves (It is unneccessary to know what part of the middle, as long as you know that there is a valid solution))