codeforces-scrape

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

2048C.md (2329B)


      1 Source: https://codeforces.com/problemset/problem/2048/C
      2 
      3 C. Kevin and Binary Strings
      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 Kevin discovered a binary string $s$ that starts with 1 in the river at Moonlit River Park and handed it over to you. Your task is to select two non-empty substrings$^{\text{∗}}$ of $s$ (which can be overlapped) to maximize the XOR value of these two substrings.
     22 
     23 The XOR of two binary strings $a$ and $b$ is defined as the result of the $\oplus$ operation applied to the two numbers obtained by interpreting $a$ and $b$ as binary numbers, with the leftmost bit representing the highest value. Here, $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
     24 
     25 The strings you choose may have leading zeros.
     26 
     27 $^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$).
     32 
     33 The only line of each test case contains a binary string $s$ that starts with 1 ($1\le\lvert s\rvert\le 5000$).
     34 
     35 It is guaranteed that the sum of $\lvert s\rvert$ over all test cases doesn't exceed $5000$.
     36 
     37 Output
     38 
     39 For each test case, output four integers $l_1, r_1, l_2, r_2$ ($1 \le l_1 \le r_1 \le |s|$, $1 \le l_2 \le r_2 \le |s|$) — in the case the two substrings you selected are $s_{l_1} s_{l_1 + 1} \ldots s_{r_1}$ and $s_{l_2} s_{l_2 + 1} \ldots s_{r_2}$.
     40 
     41 If there are multiple solutions, print any of them.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 111
     51 
     52 1000
     53 
     54 10111
     55 
     56 11101
     57 
     58 1100010001101
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 2 2 1 3
     65 1 3 1 4
     66 1 5 1 4
     67 3 4 1 5
     68 1 13 1 11
     69 ```
     70 
     71 Note
     72 
     73 In the first test case, we can choose $ s_2=\texttt{1} $ and $ s_1 s_2 s_3=\texttt{111} $, and $ \texttt{1}\oplus\texttt{111}=\texttt{110} $. It can be proven that it is impossible to obtain a larger result. Additionally, $ l_1=3$, $r_1=3$, $l_2=1$, $r_2=3 $ is also a valid solution.
     74 
     75 In the second test case, $ s_1 s_2 s_3=\texttt{100} $, $ s_1 s_2 s_3 s_4=\texttt{1000} $, the result is $ \texttt{100}\oplus\texttt{1000}=\texttt{1100} $, which is the maximum.