## Intuition The problem is about counting the number of flights between two cities based on a sequence of office visits. Specifically, we need to determine if the flights from Seattle ('S') to San Francisco ('F') are more frequent than the reverse. We can achieve this by simply counting the transitions from 'S' to 'F' and from 'F' to 'S'. ## Approach 1. **Initialize Counters**: Start with two counters, one for flights from Seattle to San Francisco (`sf_count`) and another for flights from San Francisco to Seattle (`fs_count`). 2. **Iterate Through the String**: Traverse the given string from the first to the second last character. For each character, check the next character: - If the current character is 'S' and the next character is 'F', increment the `sf_count`. - If the current character is 'F' and the next character is 'S', increment the `fs_count`. 3. **Compare Counts**: After processing the string, compare the two counters: - If `sf_count` is greater than `fs_count`, print "YES". - Otherwise, print "NO". This approach ensures that we count only valid transitions (flights) and directly compare them to determine the result. ## Complexity - **Time Complexity**: O(n), where n is the length of the string. We make a single pass through the string. - **Space Complexity**: O(1), as we only use a fixed number of extra variables. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; string offices; cin >> offices; int sf_count = 0, fs_count = 0; for (int i = 0; i < n - 1; ++i) { if (offices[i] == 'S' && offices[i + 1] == 'F') { sf_count++; } else if (offices[i] == 'F' && offices[i + 1] == 'S') { fs_count++; } } if (sf_count > fs_count) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; } ``` This solution reads the input, processes the string to count the transitions, and outputs the result based on the comparison of the two counts. It is efficient and directly addresses the problem requirements.

Between the Offices

Problem Details