codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1694B.md (2060B)


      1 Source: https://codeforces.com/problemset/problem/1694/B
      2 
      3 B. Paranoid String
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Let's call a binary string $T$ of length $m$ indexed from $1$ to $m$ paranoid if we can obtain a string of length $1$ by performing the following two kinds of operations $m-1$ times in any order :
     22 
     23 * Select any substring of $T$ that is equal to 01, and then replace it with 1.
     24 * Select any substring of $T$ that is equal to 10, and then replace it with 0.
     25 
     26   For example, if $T = $ 001, we can select the substring $[T_2T_3]$ and perform the first operation. So we obtain $T = $ 01.
     27 
     28 You are given a binary string $S$ of length $n$ indexed from $1$ to $n$. Find the number of pairs of integers $(l, r)$ $1 \le l \le r \le n$ such that $S[l \ldots r]$ (the substring of $S$ from $l$ to $r$) is a paranoid string.
     29 
     30 Input
     31 
     32 The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.
     33 
     34 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of $S$.
     35 
     36 The second line of each test case contains a binary string $S$ of $n$ characters $S_1S_2 \ldots S_n$. ($S_i = $ 0 or $S_i = $ 1 for each $1 \le i \le n$)
     37 
     38 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, output the number of pairs of integers $(l, r)$ $1 \le l \le r \le n$ such that $S[l \ldots r]$ (the substring of $S$ from $l$ to $r$) is a paranoid string.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 
     51 1
     52 
     53 1
     54 
     55 2
     56 
     57 01
     58 
     59 3
     60 
     61 100
     62 
     63 4
     64 
     65 1001
     66 
     67 5
     68 
     69 11111
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 1
     76 3
     77 4
     78 8
     79 5
     80 ```
     81 
     82 Note
     83 
     84 In the first sample, $S$ already has length $1$ and doesn't need any operations.
     85 
     86 In the second sample, all substrings of $S$ are paranoid. For the entire string, it's enough to perform the first operation.
     87 
     88 In the third sample, all substrings of $S$ are paranoid except $[S_2S_3]$, because we can't perform any operations on it, and $[S_1S_2S_3]$ (the entire string).