Split and Reverse

AtCoder

IDagc076_b

Time2000ms

Memory256MB

Difficulty—

You are given an integer sequence $X=(X_1,X_2,\cdots,X_N)$ of length $N$ consisting of $0$ and $1$. You can perform the following operation zero or more times: * Classify each element of $X$ into group `A` or group `B`. Then, for each group, reverse the order of the elements it contains. More formally, if the elements contained in a group are $X_{i_1},X_{i_2},\cdots,X_{i_s}$ ($i_1<i_2<\cdots<i_s$), then for all $1 \leq j \leq s$, simultaneously replace the value of $X_{i_j}$ with $X_{i_{s+1-j}}$. Your goal is to make $X$ non-decreasing. Find the minimum number of operations needed to achieve the goal and the way to perform the operations. It can be proved that a solution always exists under the constraints of this problem. Solve $T$ cases for one input. ## Constraints * $1 \leq T \leq 250000$ * $1 \leq N \leq 250000$ * $0 \leq X_i \leq 1$ * The sum of $N$ over the $T$ cases is at most $250000$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $case_1$ $case_2$ $\vdots$ $case_T$ Each test case is given in the following format: $N$ $X_1$ $X_2$ $\cdots$ $X_N$ [samples]

Samples

Input #1

Output #1

2
AABA
BBBB
0

For the first test case, the goal can be achieved in two operations as follows, which is the minimum number of operations:

*   First operation: Use $s_1$\=`AABA`. Since $(X_1,X_2,X_4)$ are in group `A`, reverse their order, resulting in $(X_1,X_2,X_4)=(1,1,0)$. Similarly, since $(X_3)$ is in group `B`, reverse their order, resulting in $(X_3)=(0)$. Thus, overall we get $X=(1,1,0,0)$.
    
*   Second operation: Use $s_2$\=`BBBB`. Since $()$ are in group `A`, reverse their order, resulting in $()=()$. Similarly, since $(X_1,X_2,X_3,X_4)$ are in group `B`, reverse their order, resulting in $(X_1,X_2,X_3,X_4)=(0,0,1,1)$. Thus, overall we get $X=(0,0,1,1)$.
    

For the second test case, the goal can be achieved by performing the operation zero times.

API Response (JSON)

{
  "problem": {
    "name": "Split and Reverse",
    "description": {
      "content": "You are given an integer sequence $X=(X_1,X_2,\\cdots,X_N)$ of length $N$ consisting of $0$ and $1$. You can perform the following operation zero or more times: *   Classify each element of $X$ into g",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc076_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer sequence $X=(X_1,X_2,\\cdots,X_N)$ of length $N$ consisting of $0$ and $1$.\nYou can perform the following operation zero or more times:\n\n*   Classify each element of $X$ into g...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments