Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How would you go about tackling this exercise?

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

like image 577
Cam Avatar asked Apr 08 '10 03:04

Cam


People also ask

What are some of the suggested exercises or physical activities that can help you manage stress?

Almost any form of exercise or movement can increase your fitness level while decreasing your stress. The most important thing is to pick an activity that you enjoy. Examples include walking, stair climbing, jogging, dancing, bicycling, yoga, tai chi, gardening, weightlifting and swimming.

How does exercise help relieve stress and reduce the effects of anger?

Exercise reduces levels of the body's stress hormones, such as adrenaline and cortisol. It also stimulates the production of endorphins, chemicals in the brain that are the body's natural painkillers and mood elevators.

How can physical activity help in the management of stress among students?

Exercise and other physical activity produce endorphins—chemicals in the brain that act as natural painkillers—and also improve the ability to sleep, which in turn reduces stress. Meditation, acupuncture, massage therapy, even breathing deeply can cause your body to produce endorphins.


1 Answers

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

like image 147
Mark Harrison Avatar answered Sep 29 '22 19:09

Mark Harrison