codeforces-scrape

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

1703D.md (2187B)


      1 Source: https://codeforces.com/problemset/problem/1703/D
      2 
      3 D. Double 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 You are given $n$ strings $s_1, s_2, \dots, s_n$ of length at most $\mathbf{8}$.
     22 
     23 For each string $s_i$, determine if there exist two strings $s_j$ and $s_k$ such that $s_i = s_j + s_k$. That is, $s_i$ is the concatenation of $s_j$ and $s_k$. Note that $j$ can be equal to $k$.
     24 
     25 Recall that the concatenation of strings $s$ and $t$ is $s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$, where $p$ and $q$ are the lengths of strings $s$ and $t$ respectively. For example, concatenation of "code" and "forces" is "codeforces".
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of strings.
     32 
     33 Then $n$ lines follow, the $i$-th of which contains non-empty string $s_i$ of length at most $\mathbf{8}$, consisting of lowercase English letters. Among the given $n$ strings, there may be equal (duplicates).
     34 
     35 The sum of $n$ over all test cases doesn't exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case, output a binary string of length $n$. The $i$-th bit should be $\texttt{1}$ if there exist two strings $s_j$ and $s_k$ where $s_i = s_j + s_k$, and $\texttt{0}$ otherwise. Note that $j$ can be equal to $k$.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 3
     47 
     48 5
     49 
     50 abab
     51 
     52 ab
     53 
     54 abc
     55 
     56 abacb
     57 
     58 c
     59 
     60 3
     61 
     62 x
     63 
     64 xx
     65 
     66 xxx
     67 
     68 8
     69 
     70 codeforc
     71 
     72 es
     73 
     74 codes
     75 
     76 cod
     77 
     78 forc
     79 
     80 forces
     81 
     82 e
     83 
     84 code
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 10100
     91 011
     92 10100101
     93 ```
     94 
     95 Note
     96 
     97 In the first test case, we have the following:
     98 
     99 * $s_1 = s_2 + s_2$, since $\texttt{abab} = \texttt{ab} + \texttt{ab}$. Remember that $j$ can be equal to $k$.
    100 * $s_2$ is not the concatenation of any two strings in the list.
    101 * $s_3 = s_2 + s_5$, since $\texttt{abc} = \texttt{ab} + \texttt{c}$.
    102 * $s_4$ is not the concatenation of any two strings in the list.
    103 * $s_5$ is not the concatenation of any two strings in the list.
    104 
    105 Since only $s_1$ and $s_3$ satisfy the conditions, only the first and third bits in the answer should be $\texttt{1}$, so the answer is $\texttt{10100}$.