codeforces-scrape

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

1714D.md (3134B)


      1 Source: https://codeforces.com/problemset/problem/1714/D
      2 
      3 D. Color with Occurrences
      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 some text $t$ and a set of $n$ strings $s_1, s_2, \dots, s_n$.
     22 
     23 In one step, you can choose any occurrence of any string $s_i$ in the text $t$ and color the corresponding characters of the text in red. For example, if $t=\texttt{bababa}$ and $s_1=\texttt{ba}$, $s_2=\texttt{aba}$, you can get $t=\color{red}{\texttt{ba}}\texttt{baba}$, $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$ or $t=\texttt{bab}\color{red}{\texttt{aba}}$ in one step.
     24 
     25 You want to color all the letters of the text $t$ in red. When you color a letter in red again, it stays red.
     26 
     27 In the example above, three steps are enough:
     28 
     29 * Let's color $t[2 \dots 4]=s_2=\texttt{aba}$ in red, we get $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$;
     30 * Let's color $t[1 \dots 2]=s_1=\texttt{ba}$ in red, we get $t=\color{red}{\texttt{baba}}\texttt{ba}$;
     31 * Let's color $t[4 \dots 6]=s_2=\texttt{aba}$ in red, we get $t=\color{red}{\texttt{bababa}}$.
     32 
     33 Each string $s_i$ can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.
     34 
     35 Determine the minimum number of steps needed to color all letters $t$ in red and how to do it. If it is impossible to color all letters of the text $t$ in red, output -1.
     36 
     37 Input
     38 
     39 The first line of the input contains an integer $q$ ($1 \le q \le 100$) —the number of test cases in the test.
     40 
     41 The descriptions of the test cases follow.
     42 
     43 The first line of each test case contains the text $t$ ($1 \le |t| \le 100$), consisting only of lowercase Latin letters, where $|t|$ is the length of the text $t$.
     44 
     45 The second line of each test case contains a single integer $n$ ($1 \le n \le 10$) — the number of strings in the set.
     46 
     47 This is followed by $n$ lines, each containing a string $s_i$ ($1 \le |s_i| \le 10$) consisting only of lowercase Latin letters, where $|s_i|$ — the length of string $s_i$.
     48 
     49 Output
     50 
     51 For each test case, print the answer on a separate line.
     52 
     53 If it is impossible to color all the letters of the text in red, print a single line containing the number -1.
     54 
     55 Otherwise, on the first line, print the number $m$ — the minimum number of steps it will take to turn all the letters $t$ red.
     56 
     57 Then in the next $m$ lines print pairs of indices: $w_j$ and $p_j$ ($1 \le j \le m$), which denote that the string with index $w_j$ was used as a substring to cover the occurrences starting in the text $t$ from position $p_j$. The pairs can be output in any order.
     58 
     59 If there are several answers, output any of them.
     60 
     61 Example
     62 
     63 Input
     64 
     65 ```
     66 6
     67 
     68 bababa
     69 
     70 2
     71 
     72 ba
     73 
     74 aba
     75 
     76 caba
     77 
     78 2
     79 
     80 bac
     81 
     82 acab
     83 
     84 abacabaca
     85 
     86 3
     87 
     88 aba
     89 
     90 bac
     91 
     92 aca
     93 
     94 baca
     95 
     96 3
     97 
     98 a
     99 
    100 c
    101 
    102 b
    103 
    104 codeforces
    105 
    106 4
    107 
    108 def
    109 
    110 code
    111 
    112 efo
    113 
    114 forces
    115 
    116 aaaabbbbcccceeee
    117 
    118 4
    119 
    120 eeee
    121 
    122 cccc
    123 
    124 aaaa
    125 
    126 bbbb
    127 ```
    128 
    129 Output
    130 
    131 ```
    132 3
    133 2 2
    134 1 1
    135 2 4
    136 -1
    137 4
    138 1 1
    139 2 6
    140 3 3
    141 3 7
    142 4
    143 3 1
    144 1 2
    145 2 3
    146 1 4
    147 2
    148 4 5
    149 2 1
    150 4
    151 3 1
    152 4 5
    153 2 9
    154 1 13
    155 ```
    156 
    157 Note
    158 
    159 The first test case is explained in the problem statement.
    160 
    161 In the second test case, it is impossible to color all the letters of the text in red.