CF1774C Solution

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

To complain a little, the official solution was rather difficult to understand. I remained quite confused after reading it for a long time (actually, I am also just not good enough). After understanding it, I felt that this problem was quite clever, so I came to write a solution.

Approach

We first need to make an observation: for the string $s$, its final consecutive segment does not increase the number of possible winners. For example, when $s = \texttt{0011}$, the ending $\texttt{11}$ does not increase the number of possible winners.

Why? Suppose that, after any number of matches, the set of possible player combinations is $t$. Then, for any $x \in t$, after any number of consecutive matches in environment $1$, the final winner must be the player in $x$ with the highest temperature. This is because every remaining player must play continuously in environment $1$, and the only player who can win every match must be the largest. Similarly, after the players in $t$ play any number of consecutive matches in environment $0$, the final winner must be the player in $x$ with the lowest temperature.

For example, when $s = \texttt{111}$, player 4 must be the final winner.

Thus, if the ending segment is $1$ (the same applies to an ending of $0$; for convenience, the examples below use $1$), we only need to calculate how many player combinations with different maximum values (player temperatures) can be constructed by the preceding part. This tells us the answer for $s$ at its current length.

Now consider how to construct the maximum number of player combinations with different maximum values. If there are $n$ players, then before any matches, the maximum value is $n$. To make the maximum value different, we can only remove the current maximum.

Special Case

The preceding description may be relatively abstract. The example $s = \texttt{0011}$ makes it easier to understand.

For the first $0$, every player other than the one with the lowest temperature in the player combination can be removed (that lowest-temperature player can win no matter what). We can make the player with the lowest temperature play against any other player, giving the following cases:

$$1 : \texttt{1234} \cancel{\texttt{5}} \\ 2 : \texttt{123} \cancel{\texttt{4}} \texttt{5} \\ 3 : \texttt{12} \cancel{\texttt{3}} \texttt{45} \\ 4 : \texttt{1} \cancel{\texttt{2}} \texttt{345} \\$$

Observation shows that only the first case changes the maximum value (why? Because it removes the maximum). In the other cases, a consecutive segment of numbers at the end must be removed before the maximum value can change.

This is where the second $0$ has an effect. In the second case, it can remove $5$, making the maximum value of the player combination become $3$. Following this pattern, we can generalize the following conclusion: suppose the length of the consecutive segment before the ending segment is $l$. The number of player combinations it can produce with different maximum values is $l + 1$. Specifically, the possible range of maximum values is $[n - l, n]$. (The $+1$ is because we can choose not to change the original maximum value.)

At this point, we can already find the answer when $s$ contains only two consecutive segments. It is $n - k$, where $k = |s| - l$ represents the length of the ending segment.

Generalization

Now let us change the example to $s = \texttt{1011}$ and see whether the conclusion still holds ($s$ contains more than one segment). Similarly, we can list the possible player combinations after the first match. Because the first environment is $1$, only players other than the maximum can be removed:

$$1 : \texttt{123} \cancel{\texttt{4}} \texttt{5} \\ 2 : \texttt{12} \cancel{\texttt{3}} \texttt{45} \\ 3 : \texttt{1} \cancel{\texttt{2}} \texttt{345} \\ 1 : \cancel{\texttt{1}} \texttt{2345} \\$$

Although none of these cases changes the maximum value of the player combination, we only need to play one more match in the following $0$ environment and remove $5$ to produce two new maximum values. In the first case, the maximum becomes $3$; in the second case, it becomes $2$. There are also $n - k$ possible answers in total.

What if there are even more segments? For example, $s = \texttt{01011}$. The conclusion still holds. We can regard $\texttt{010}$ as a group of environments, in which $0$ can remove any player in the range $[2, n]$, while $1$ can remove any player in $[1, n - 1]$. Combining these two kinds of environments allows us to choose any three players from $[1, n]$ to remove, constructing four different maximum values (depending on how many of the players with the highest temperatures are removed from the beginning).

Code and Implementation

Through the preceding examples, we have determined that solving the problem only requires knowing the length of the final consecutive segment in the substring $[1, i]$ of $s$. However, scanning it again for every $i$ is too slow, so we need to use something similar to dynamic programming. The specific explanation is in the code comments:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        string s;
        cin >> n >> s;
        int cur0len = 0; // If the final consecutive segment consists of 0s, cur0len represents its length.
                         // Otherwise, cur0len is 0.
        int cur1len = 0; // The same applies to 1.
        int curn = 2;    // Initially there are two players.
        for (char ch : s){
            int x = ch - '0';
            if (x == 0){
                cur0len++;   // If the current character is 0, the consecutive segment ending in 0 is longer than before.
                cur1len = 0; // The final character of s is no longer 1.
            } else {
                cur1len++;
                cur0len = 0;
            }
            cout << curn - (x ? cur1len : cur0len) << " ";
            // n - k from the preceding discussion.
            curn++;
        }
        cout << '\n';
    }
}