How would you go about tackling this problem? [SOLVED in C++]

Question

Intro:

EDIT: See solution at the bottom of this question (c++)

I have a programming contest coming up in a bit, and I've been prepping :)

I'm practicing using these questions:

http://cemc.math.uwaterloo.ca/contests/computing/2009/stage2/day1.pdf

I'm looking at problem B ("Dinner").

Any idea where to start? I can't really think of anything besides the naive approach (ie. trying all permutations) which would take too long to be a valid answer.

Btw, the language there says c++ and pascal I think, but i don't care what language you use - I mean really all I want is a hint as to the direction I should proceed in, and perhpas a short explanation to go along with it. It feels like I'm missing something obvious...

Of course extended speculation is more than welcome, but I just wanted to clarify that I'm not looking for a full solution here :)

---

Short version of the question:

You have a binary string N of length 1-100 (in the question they use H's and G's instead of one's and 0's). You must remove all of the digits from it, in the least number of steps possible. In each step you may remove any number of adjacent digits so long as they are the same. That is, in each step you can remove any number of adjacent G's, or any number of adjacent H's, but you can't remove H's and G's in one step.

Example:

HHHGHHGHH

Solution to the example:

1. HHGGHH (remove middle Hs)
2. HHHH (remove middle Gs)
3. Done (remove Hs)
   -->Would return '3' as the answer.

Note that there can also be a limit placed on how large adjacent groups have to be when you remove them. For example it might say '2', and then you can't remove single digits (you'd have to remove pairs or larger groups at a time).

---

Solution

I took Mark Harrison's main algorithm, and Paradigm's grouping idea and used them to create the solution below. You can try it out on the official test cases if you want.

//B.cpp
//include debug messages?
#define DEBUG false


#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

#define FOR(i,n) for (int i=0;i<n;i++)
#define FROM(i,s,n) for (int i=s;i<n;i++)
#define H 'H'
#define G 'G'

class String{
public:
    int num;
    char type;
    String(){
        type=H;
        num=0;
    }
    String(char type){
        this->type=type;
        num=1;
    }
};

//n is the number of bits originally in the line
//k is the minimum number of people you can remove at a time
//moves is the counter used to determine how many moves we've made so far
int n, k, moves;
int main(){

    /*Input from File*/
    scanf("%d %d",&n,&k);
    char * buffer = new char[200];
    scanf("%s",buffer);

    /*Process input into a vector*/
    //the 'line' is a vector of 'String's (essentially contigious groups of identical 'bits')
    vector<String> line;
    line.push_back(String());
    FOR(i,n){

        //if the last String is of the correct type, simply increment its count
        if (line.back().type==buffer[i])
            line.back().num++;

        //if the last String is of the wrong type but has a 0 count, correct its type and set its count to 1
        else if (line.back().num==0){
            line.back().type=buffer[i];
            line.back().num=1;
        }

        //otherwise this is the beginning of a new group, so create the new group at the back with the correct type, and a count of 1
        else{
            line.push_back(String(buffer[i]));
        }

    }

    /*Geedily remove groups until there are at most two groups left*/
    moves=0;
    int I;//the position of the best group to remove
    int bestNum;//the size of the newly connected group the removal of group I will create
    while (line.size()>2){

        /*START DEBUG*/
        if (DEBUG){
            cout<<"\n"<<moves<<"\n----\n";
            FOR(i,line.size())
                printf("%d %c \n",line[i].num,line[i].type);
            cout<<"----\n";
        }
        /*END DEBUG*/

        I=1;
        bestNum=-1;
        FROM(i,1,line.size()-1){
            if (line[i-1].num+line[i+1].num>bestNum && line[i].num>=k){
                bestNum=line[i-1].num+line[i+1].num;
                I=i;
            }
        }
        //remove the chosen group, thus merging the two adjacent groups
        line[I-1].num+=line[I+1].num;
        line.erase(line.begin()+I);
            line.erase(line.begin()+I);

            //we just performed a move
        moves++;
    }

    /*START DEBUG*/
    if (DEBUG){
        cout<<"\n"<<moves<<"\n----\n";
        FOR(i,line.size())
            printf("%d %c \n",line[i].num,line[i].type);
        cout<<"----\n";
        cout<<"\n\nFinal Answer: ";
    }
    /*END DEBUG*/


    /*Attempt the removal of the last two groups, and output the final result*/
    if (line.size()==2 && line[0].num>=k && line[1].num>=k)
        cout<<moves+2;//success
    else if (line.size()==1 && line[0].num>=k)
        cout<<moves+1;//success
    else
        cout<<-1;//not everyone could dine.

    /*START DEBUG*/
    if (DEBUG){
        cout<<" moves.";
    }
    /*END DEBUG*/
}

Some of the official test cases you can try :

• Test Case 3

  8 2
  GHHGHGGH
  

  Answer: 4

• Test Case 6

  20 2
  GGHGGHHGGGHHGHHGHHGG
  

  Answer: 6

• Test Case 14

  100 4
  HGHGGGHGGGHGHGGGHHGHGGGHHGHHHGHGGHGGHHHGGHHGHHGHGHHHHGHHGGGHGGGHGHGHHGGGHGHGHGGGHHGHHHGHGGGHGGGHGHHH
  

  Answer: -1

  Explanation: -1 is outputted when there's no correct answer.

• Test Case 18

  100 5
  GHGGGGGHGGGGGGGHHHHGGGGGHGGHHHGGGGGHHHHGGHHHHHGGGGGGHHHHHHGGGHHHHHGHHGGHHHHHGGGHHGGHHGGGGGGHHHGGGGHH
  

  Answer: 16

• Test Case 21

  95 2
  GGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHG
  

  Answer: 32

Answer 1

This problem gets a bit simpler if you treat consecutive h's or consecutive g's as 1 h or 1 g respectively (they are treated the same way, in that ghhhhhg and ghg would require the same number of removals).

This reduces the problem to a set of h's and g's alternating. At this point, removing all of the lesser count of the 2 would give you the # of operations needed (plus 1 for the "other" remaining letters).

Algorithm can be done in O(n):

• Keep a counter for h's, and a counter for g's.
• Start at the first character, and increment the appropriate counter by 1.
• Go to the next character, and if it is the same as the previous one, continue to the next one.
• If it is different, increment the counter for the new character.
• Continue the same process, incrementing the appropriate counter each time the character changes from the previous one.

After iterating through the set, the answer should be the lesser of the 2 counters (# of removals needed to remove the smaller # of characters), plus 1 (for the "other" characters, which will be left).

Is there a faster way? (and does this actually work? ;)

Answer 2

Do these steps:

• Look for a a pattern such as H+G+H+. Remove a G+ that leaves a coalesced H+ where one or more of the original H+H+ could not have been removed because of the length restriction. Otherwise remove the longest coalesced H+.
• Likewise for G+H+G+.

Repeat the above steps. each step will coalesce a larger group of H+ or G+.

Eventually you will have one H+ and one G+ (assuming you had both H and G to begin with). Remove those.

(H+,G+ means x or more H or G, where x is the minimum number that can be removed at one time.)

Answer 3

well here is a thought - w/o loss of generality you can replace sequences of Gs and Hs with number repesenting the count of letters in the group.

let's take the case#2: GGHGGHHGGGHHGHHGHHGG - it becomes 2 1 2 2 3 2 1 2 1 2 2

removing a group of letters and merging the two neighbours is removing a number and replacing the two adjacent with their sum: 2 1 2 2 3 2 1 2 1 2 2 -> 2 1 2 4 1 2 1 2 2 -> 2 1 2 4 1 2 3 -> 2 1 3 2 3 -> 2 3 3 -> 5 -> nil

if you notice, each time when we remove a group from the middle (not leftmost or rightmost), the length decreases by 2, so the number of steps necessary seems to be around N/2 (where N is the length of the list of numbers we started from) - the twist being that if N was even number, at the very end you will have list of 2 elements that will be cleared in 2 steps (so +1 extra step).

So seems to me the optimal number of steps is always = trunc((N+1)/2) - if at all possible. So the job seems to be more of the kind of finding if it's possible to reduce H-G chain at all - if it is, then we know the minimula number of steps.

Thoughts?