How would you go about tackling this problem? [SOLVED in C++]
- by incrediman
Intro:
EDIT: See solution at the bottom of this question (c++)
I have a programming contest coming up in about half a week, and I've been prepping :)
I found a bunch of questions from this canadian competition, they're great practice:
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);
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*/
}
