Subtask 1

For Subtask 1, we can brute-force generate every possible string S. If the string has length $n$, then there are $2^n$ possible such strings (in the worst case where the entire string is F). Each string takes $\mathcal{O}(n)$ time to compute an answer, so in total this solution takes $\mathcal{O}(2^n \cdot n)$ time.

Problem Solving Process

Note: This section is intended to walk you through the problem-solving process of how to arrive at the solution, rather than just stating the solution immediately; ideally, this problem-solving process can be applied to other problems as well. If you have feedback on how well this format works for you / whether you found this section helpful, and the current date is not yet April 2024, please email me at [email protected].

If you just want the full solution, scroll down to the "Full Solution" section below.

Step 1: Solving the Sample Inputs

The first step is solving the sample inputs by hand. The goal is to make sure you fully understand what the problem is asking you to do.

Step 2: Coming up with more test cases

Next, let's try coming up with more test cases we can solve by hand. Focus on two types of test cases:

1. A lot of simple test cases that have some pattern to them. We want to use these to uncover patterns that we might be able to use to solve the problem. Examples: BFB, BFFB, BFFBFFB, etc.
2. Edge cases -- as many as you can think of!

As you come up with these test cases, try to group them into patterns (especially for the simple test cases). For example, BFB, BFFB, BFFFB can be grouped together into a pattern like BF...FB. The goal is to come up with solutions to each of these patterns, and then try to come up with a solution to the general problem.

I came up with ~30 test cases, but the exact number doesn't really matter. Don't spend too much time on this (I spent ~4 minutes?); you can always come up with more later.

Step 3: Solving test cases by hand

Now, we'll solve the test cases we came up with earlier by hand, trying to uncover patterns in how we solve them. Not all test case categories will have generalizable / nice solutions, and that's fine!

As an example, here's what I wrote for one of the patterns I came up with.

Pattern 1: BF...FB

• BB: $1$
• BFB: $0$, $2$
• BFFB: $1$, $3$
• BFFFB: $0$, $2$, $4$
• BFFFFB: $1$, $3$, $5$

Possible Solution

Do you see any patterns? (You might need to write out more cases.)

Explanation

I arrived at the solution above solely by pattern-matching; I have no idea if it's correct. Let's try to convince ourself as to why it's correct (or if it's actually wrong)!

Can you convince yourself that this solution is correct?

If you're stuck, try using this strategy:

1. Add constraints (simplify the problem as much as possible) until we reach a problem that we can solve / prove. For example, one constraint we might add is "assume the length of the string is even."
2. Add back the constraints one at a time and update your solution / proof until we arrive back at the original problem.

Try it yourself!

For this step, feel free to follow along by solving the test cases I came up with, or you can also use the test cases that you came up with.

For every pattern, try to come up with a possible solution, as well as a justification as to why that solution is correct. Not all patterns will have nice solutions -- if you can't think of anything, just move on! (Also, don't be afraid if your solution has a bunch of different cases -- "nice" solutions can still have different cases!)

You may also find it helpful to skip a complicated pattern and come back to it later after you've solved some simpler patterns. Sometimes a complicated pattern's solution is just a combination of the solution of two easier patterns!

Step 4: Constructing a general solution

Now, try to come up with a solution for the general problem using some of the solutions we came up with earlier.

If you're stuck, the strategy from above is still applicable:

1. Add constraints (simplify the problem as much as possible) until we reach a problem that we can solve / prove.
2. Add back the constraints one at a time and update your solution / proof until we arrive back at the original problem.

You can also go back to step 2 (come up with new small test cases / new patterns and try to find solutions to those) if you are stuck.

Concluding Thoughts

I hope this section on the problem-solving process I used to solve this problem was helpful! This process isn't specific to this problem, so hopefully you can apply a similar process to other problems as well.

If you have feedback on whether you found this section helpful / what can be improved, and the current date is not yet April 2024, please email me at [email protected].

Full Solution

First, assume the starting / ending character is not F.

Split the string into "sections" such that each section has one starting character that isn't F, one ending character that isn't F, and a bunch of F's in the middle. The edge characters of each "section" can overlap. For the sample input BFFFFFEBFE, our sections are:

• BFFFFFE
• EB
• BFE

We will get an answer for each section and then combine the answers to get the answer for the whole string.

Solving each section

Let's start by finding the lowest / highest possible excitement of each section. We will do this with casework:

• Is the starting / ending character the same?
• Is the length of the section even?

Let $n$ be the length of the section.

Case 1: Starting / ending is same

If $n$ is even, min is $1$ and max is $n-1$. Otherwise, min is $0$ and max is $n-1$.

Case 2: Starting / ending is different

if $n$ is even, min is $0$ and max is $n-2$. Otherwise, min is $1$ and max is $n-2$.

Let $x$ be the min and $y$ be the max. We can achieve any value $x, x+2, x+4, \ldots y-2, y$.

Start with the string that yields $x$; it's something like BEBEBEB. Changing one E to become a B will increase our answer by 2.

If we examine something like BFFFB, note that it is impossible to achieve an answer of $1$.

Combining sections

We can add the min / max values from every section together to get the min / max values for the whole string. If we let $x$ be the min for the whole string and $y$ be the max for the whole string, our possible answers are $x, x+2, x+4, \ldots, y-2, y$.

Handling F's on the first / last character

Let $x$ be the number of F's at the start of the string and $y$ be the number of F's at the end of the string. By inspection, these F's contribute a minimum of $0$ to our excitement level and a maximum of $x + y$ to our excitement level.

Note that in this special case where F is on the edge of the string, we can actually achieve any value in between $0$ and $x+y$! For example, take the string FFFB. We can get 0 by doing EBEB, 1 by doing BEBB, 2 by doing EBBB, and 3 by doing BBBB.

As a result, as long as one of $x$ or $y$ is not $0$, we can achieve an excitement level for our overall string of every value in between min and max. However, if both $x$ and $y$ are $0$, then we still can only get excitement levels in increments of $2$.

We also need to take care to handle the case where the entire string is F's properly.

Implementation

Nathan's commented code:

Copy
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;

Ben's code, which is a lot more concise and takes advantage of some nice similarities between cases:

Copy
N = int(input())
S = list(input())
if S.count("F") == N:
	S[0] = "E"
positions = [i for i in range(N) if S[i] != "F"]
ones = positions[0] + N - 1 - positions[-1]
mn, mx = 0, 0
for a, b in zip(positions, positions[1:]):
	mn += ((b - a) & 1) ^ (S[a] != S[b])
	mx += b - a - (S[a] != S[b])
ans = range(mn, ones + mx + 1, 1 + (ones == 0))
print(len(ans))
for level in ans:
	print(level)