codeforces-scrape

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

1820B.md (3112B)


      1 Source: https://codeforces.com/problemset/problem/1820/B
      2 
      3 B. JoJo's Incredible Adventures
      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 Did you think there was going to be a JoJo legend here? But no, that was me, Dio!
     22 
     23 Given a binary string $s$ of length $n$, consisting of characters 0 and 1. Let's build a square table of size $n \times n$, consisting of 0 and 1 characters as follows.
     24 
     25 In the first row of the table write the original string $s$. In the second row of the table write cyclic shift of the string $s$ by one to the right. In the third row of the table, write the cyclic shift of line $s$ by two to the right. And so on. Thus, the row with number $k$ will contain a cyclic shift of string $s$ by $k$ to the right. The rows are numbered from $0$ to $n - 1$ top-to-bottom.
     26 
     27 In the resulting table we need to find the rectangle consisting only of ones that has the largest area.
     28 
     29 We call a rectangle the set of all cells $(i, j)$ in the table, such that $x_1 \le i \le x_2$ and $y_1 \le j \le y_2$ for some integers $0 \le x_1 \le x_2 \lt n$ and $0 \le y_1 \le y_2 \lt n$.
     30 
     31 Recall that the cyclic shift of string $s$ by $k$ to the right is the string $s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}$. For example, the cyclic shift of the string "01011" by $0$ to the right is the string itself "01011", its cyclic shift by $3$ to the right is the string "01101".
     32 
     33 Input
     34 
     35 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of test cases follows.
     36 
     37 The first and the only line of each test case contains a single binary string $s$ ($1 \le \lvert s \rvert \le 2 \cdot 10^5$), consisting of characters 0 and 1.
     38 
     39 It is guaranteed that the sum of string lengths $|s|$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the maximum area of a rectangle consisting only of ones. If there is no such rectangle, output $0$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 0
     53 
     54 1
     55 
     56 101
     57 
     58 011110
     59 
     60 101010
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 0
     67 1
     68 2
     69 6
     70 1
     71 ```
     72 
     73 Note
     74 
     75 In the first test case, there is a table $1 \times 1$ consisting of a single character 0, so there are no rectangles consisting of ones, and the answer is $0$.
     76 
     77 In the second test case, there is a table $1 \times 1$, consisting of a single character 1, so the answer is $1$.
     78 
     79 In the third test case, there is a table:
     80 
     81 |  |  |  |
     82 | --- | --- | --- |
     83 | 1 | 0 | 1 |
     84 | 1 | 1 | 0 |
     85 | 0 | 1 | 1 |
     86 
     87 In the fourth test case, there is a table:
     88 
     89 |  |  |  |  |  |  |
     90 | --- | --- | --- | --- | --- | --- |
     91 | 0 | 1 | 1 | 1 | 1 | 0 |
     92 | 0 | 0 | 1 | 1 | 1 | 1 |
     93 | 1 | 0 | 0 | 1 | 1 | 1 |
     94 | 1 | 1 | 0 | 0 | 1 | 1 |
     95 | 1 | 1 | 1 | 0 | 0 | 1 |
     96 | 1 | 1 | 1 | 1 | 0 | 0 |
     97 
     98 In the fifth test case, there is a table:
     99 
    100 |  |  |  |  |  |  |
    101 | --- | --- | --- | --- | --- | --- |
    102 | 1 | 0 | 1 | 0 | 1 | 0 |
    103 | 0 | 1 | 0 | 1 | 0 | 1 |
    104 | 1 | 0 | 1 | 0 | 1 | 0 |
    105 | 0 | 1 | 0 | 1 | 0 | 1 |
    106 | 1 | 0 | 1 | 0 | 1 | 0 |
    107 | 0 | 1 | 0 | 1 | 0 | 1 |
    108 
    109 Rectangles with maximum area are shown in bold.