Chocolate Breaks
Autumn Tournament (2008)
Submission name: choco.cpp
Problem summary
A chocolate bar is one row of N lettered blocks. Find the fewest breaks needed to separate all blocks carrying a given target letter from all blocks carrying other letters. Adjacent target blocks may remain together.
Input
N and a target uppercase Latin letter, followed by N uppercase Latin letters.
Output
The minimum number of breaks.
Constraints
0 < N < 10000.
Worked example
Original statement sample.
Input
10 A BAACAADZAZ
Output
6
Solution analysis
- A necessary break occurs exactly between two adjacent blocks where one is the target and the other is not. Adjacent target blocks need not be split, and neither do two adjacent non-target blocks.
- Read the N characters, which works whether they are contiguous or separated by whitespace. Compare each target/non-target flag with the previous flag and count changes.
- For BAACAADZAZ with target A, the target flags are 0,1,1,0,1,1,0,0,1,0. They change at six boundaries, so six breaks suffice. For ABAAAAAA there are only two such boundaries.
Why it works
Every boundary joining a target block to a non-target block must be cut, otherwise some resulting piece would mix the two kinds. Cutting all and only those boundaries yields pieces containing just one kind, so this lower bound is attainable.
Watch out. Do not split between consecutive target blocks. A target at an end needs only its internal boundary cut. If every block or no block has the target letter, the answer is zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
int n;
char target;
cin>>n>>target;
int breaks=0;
bool previousIsTarget=false;
for(int i=0;i<n;i++){
char block;
cin>>block;
bool isTarget=block==target;
// Only boundaries between the two kinds require a break.
if(i>0&&isTarget!=previousIsTarget){
breaks++;
}
previousIsTarget=isTarget;
}
cout<<breaks<<'\n';
}