A Dynamic programming problem

9
votes

Can anyone help me find an optimal Dynamic programming algorithm for this problem

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? 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.

3
algorithmdynamic-programmingpuzzle
You should probably tag the question appropriately if you want to have some answers. trick is a very meaningless tag. - Felix Kling
@kletoskletos - Is there a reason to use dynamic programming here? Since we are given the number of Helpfile programmers and the number of Gnold programmers, we can divide their numbers by the group number specified by Doctor V. The remaining programmers in either group need to be added to an already formed group so that it doesn't exceed groups of six. I guess that's where Dynamic programming comes into play. Interesting problem. - sc_ray
@sc_ray: I think you misread the problem. You need to find contiguous groups of at least K people and remove them from the line, in such a way that you can eventually remove all the people from the line. You can't reorder the line, you can only remove groups of like-minded programmers that happen to be next to each other. - Null Set
@Null Set: In that case, how would you group the following sequence,GHHGHHGH for K>=2? - sc_ray
@sc_ray - you wouldn't, you'd print -1. - IVlad

3 Answers

8
votes

I'd prefer not to solve an SPOJ problem in a practical manner for you, so take the following as an existence proof of a poly-time DP.

For K fixed, the set of strings that can dine is context-free. I'm going to use g and h instead of G and H. For example, for K = 3, one grammar looks like

S -> ε | g S g S g S G | h S h S h S H

G -> ε | g S G

H -> ε | h S H

The idea is that either there are no diners, or the first diner dines with at least K - 1 others, between any two of which (and the last and the end) there is a string that can dine.

Now use the weighted variant of CYK to find the minimum-weight parse, where nonempty S productions have weight 1, and all others have weight 0. For K fixed, the running time of CYK is O(N3).

0
votes

The subproblem is the minimal groups needed to get everyone to dine for a given state of the line. There are a whole lot of possible line states but only a few that will actually be seen, so your memoization should probably be done with a hash map.

Here's some pseudocode.

int dine(string line){
    if(hashmap.contains(line)){
        return hashmap.get(line);
    }
    if(line.length == 0){
        return 0;
    }
    best = N+1;
    for(i=0;i<line.length;i=j){
        type = string[i];
        j = i+1;
        while(type == string[j]){
            j++;
        }
        if(j-i >= K){
             result = dine(string.substring(0,i-1) + string.substring(j,string.length));
             if(result > 0 && result < best){
                  best = result;
             }
        }
    }
    if(best == N+1){
         hashmap.insert(line, -1);
         return -1;
    }
    else {
         hashmap.insert(line, best+1);
         return best+1;
    }
}

If you already found answer for this line, return that answer. If theres no people in the line, you are already done and you don't need to form any more groups.

Assume you can't form any groups. Then try to prove this wrong by trying out all the contiguous groups of like-minded programmers in the line. If the group is big enough to get picked, see how many more moves it would take to get everyone in the resturaunt after removing this group. Keep track of the least moves needed.

If you couldn't find a way to remove all the groups, return -1. Otherwise, return the least moves needed after removing a group plus one to account for the move you made on this step.

0
votes

How about divide and conquer? Take a (removable) group somewhere near the middle, and the two groups either side of it, say ...HHHGGGGGHHHHH.... - now there's two possibilities. Either those 2 sets of H's dine in the same group, or they don't. If they dine in the same group, then those G's between them must be removed as a group of precisely those G's (so you may as well try that as your first move). If they don't, then you can solve for the left and right sublists separately. Either case, you've got a shorter list to recurse on.