How would you decide to do this exercise?

Question

Introduction:

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

I already have a programming contest, and I'm cooking :)

I use these questions:

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

I look at issue B ("Dinner").

Any idea where to start? I can’t even think of anything other than a naive approach (i.e., to try permutations), which for too long would be considered the right answer.

Btw, which is spoken by C ++ and pascal, I think, but I don't care which language you use. I mean, all I want is a hint at the direction in which I should work, as well as a brief explanation, agree with this. It seems to me that I will miss something obvious ...

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

---

Short version of the question:

You have a binary string N of length 1-100 (in the question they use H and G instead of one and 0). You must remove all the numbers from it in the least number of steps . At each step, you can delete any number of adjacent digits if they are the same. That is, at each step, you can delete any number of neighboring Gs or any number of neighboring H, but you cannot delete H and G in one step.

Example:

HHHGHHGHH 

Solution for example:

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

Please note that there may also be a restriction on how large adjacent groups should be when you delete them. For example, he may say “2,” and then you cannot delete individual numbers (you will need to delete pairs or larger groups at a time).

---

Decision

I took the main algorithm of Mark Harrison and the idea of ​​grouping Paradigm and used them to create the solution below, you can try it on official tests , 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 (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 Example 6

   20 2 GGHGGHHGGGHHGHHGHHGG 

  Answer: 6

• Test Example 14

   100 4 HGHGGGHGGGHGHGGGHHGHGGGHHGHHHGHGGHGGHHHGGHHGHHGHGHHHHGHHGGGHGGGHGHGHHGGGHGHGHGGGHHGHHHGHGGGHGGGHGHHH 

  Answer: -1

  Explanation: -1 is output when there is no correct answer.

• Test Example 18

   100 5 GHGGGGGHGGGGGGGHHHHGGGGGHGGHHHGGGGGHHHHGGHHHHHGGGGGGHHHHHHGGGHHHHHGHHGGHHHHHGGGHHGGHHGGGGGGHHHGGGGHH 

  Answer: 16

• Test Example 21

   95 2 GGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGGHHGHGHGHGHGHGHGHGHGHGHGHGHGHGHGHG 

  Answer: 32

Answer 1

Follow these steps:

• Find a template such as H + G + H +. Remove the G + that leaves the combined H + when one or more of the original H + H + could not be removed due to length restrictions. Otherwise, remove the longest coagulated H +.
• Similarly for G + H + G +.

Repeat the above steps. each step will combine a large group of H + or G +.

In the end, you will have one H + and one G + (if you start with H and G). Remove them.

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

Answer 2

This problem becomes a little easier if you treat sequential h or sequential g as 1 h or 1 g respectively (they are treated the same way, in that ghhhhhg and ghg will require the same number of paragraphs).

This reduces the problem to a set of variables h and g. At this point, deleting as few as 2 will give you the number of operations you need (plus 1 for the remaining "remaining letters").

The algorithm can be executed in O (n):

• Keep a counter for h and a counter for g.
• Start with the first character and increase the corresponding counter by 1.
• Go to the next character, and if it matches the previous one, go to the next character.
• If it is different, add a counter for the new character.
• Continue the process by incrementing the corresponding counter each time a character changes from the previous one.

After iterating over the set, the answer should be the smaller of the two counters (# abstractions needed to remove fewer characters), plus 1 (for the remaining characters that will be left).

Is there a faster way? (and does it really work ?;)

Answer 3

Well, here's the thought - without loss of generality, you can replace the sequences Gs and Hs with a number representing the number of letters in the group.

take case # 2: GGHGGHHGGGHHGHHGHHGG - it becomes 2 1 2 2 3 2 1 2 1 2 2

deleting a group of letters and combining two neighbors - deleting a number and replacing two neighboring ones 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, every time we delete a group from the middle (not left or right), the length decreases by 2, so the number of necessary steps seems to be about N / 2 (where N is the length of the list of numbers we started with) - the twist is in that if N was an even number, at the very end you will have a list of 2 elements that will be cleared in 2 steps (so +1 is an additional step).

It seems to me that the optimal number of steps is always = trunc ((N + 1) / 2) - if at all possible. Thus, the work seems to depend more on whether the HG chain can be reduced at all - if so, then we know the minimum number of steps.

Thoughts?