codeforces-scrape

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

1879C.md (2115B)


      1 Source: https://codeforces.com/problemset/problem/1879/C
      2 
      3 C. Make it Alternating
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 You are given a binary string $s$. A binary string is a string consisting of characters 0 and/or 1.
     22 
     23 You can perform the following operation on $s$ any number of times (even zero):
     24 
     25 * choose an integer $i$ such that $1 \le i \le |s|$, then erase the character $s_i$.
     26 
     27 You have to make $s$ alternating, i. e. after you perform the operations, every two adjacent characters in $s$ should be different.
     28 
     29 Your goal is to calculate two values:
     30 
     31 * the minimum number of operations required to make $s$ alternating;
     32 * the number of different shortest sequences of operations that make $s$ alternating. Two sequences of operations are different if in at least one operation, the chosen integer $i$ is different in these two sequences.
     33 
     34 Input
     35 
     36 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     37 
     38 Each test case consists of one line containing the string $s$ ($1 \le |s| \le 2 \cdot 10^5$). The string $s$ consists of characters 0 and/or 1 only.
     39 
     40 Additional constraint on the input:
     41 
     42 * the total length of strings $s$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, print two integers: the minimum number of operations you have to perform, and the number of different shortest sequences of operations. Since the second number might be large, print its remainder modulo $998244353$.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 3
     54 
     55 10010
     56 
     57 111
     58 
     59 0101
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 1 2
     66 2 6
     67 0 1
     68 ```
     69 
     70 Note
     71 
     72 In the first test case of the example, the shortest sequences of operations are:
     73 
     74 * $[2]$ (delete the $2$-nd character);
     75 * $[3]$ (delete the $3$-rd character).
     76 
     77 In the second test case of the example, the shortest sequences of operations are:
     78 
     79 * $[2, 1]$ (delete the $2$-nd character, then delete the $1$-st character);
     80 * $[2, 2]$;
     81 * $[1, 1]$;
     82 * $[1, 2]$;
     83 * $[3, 1]$;
     84 * $[3, 2]$.
     85 
     86 In the third test case of the example, the only shortest sequence of operations is $[]$ (empty sequence).