codeforces-scrape

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

1383A.md (3026B)


      1 Source: https://codeforces.com/problemset/problem/1383/A
      2 
      3 A. String Transformation 1
      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 Note that the only difference between String Transformation 1 and String Transformation 2 is in the move Koa does. In this version the letter $y$ Koa selects must be strictly greater alphabetically than $x$ (read statement for better understanding). You can make hacks in these problems independently.
     22 
     23 Koa the Koala has two strings $A$ and $B$ of the same length $n$ ($|A|=|B|=n$) consisting of the first $20$ lowercase English alphabet letters (ie. from a to t).
     24 
     25 In one move Koa:
     26 
     27 1. selects some subset of positions $p_1, p_2, \ldots, p_k$ ($k \ge 1; 1 \le p_i \le n; p_i \neq p_j$ if $i \neq j$) of $A$ such that $A_{p_1} = A_{p_2} = \ldots = A_{p_k} = x$ (ie. all letters on this positions are equal to some letter $x$).
     28 2. selects a letter $y$ (from the first $20$ lowercase letters in English alphabet) such that $y \gt x$ (ie. letter $y$ is strictly greater alphabetically than $x$).
     29 3. sets each letter in positions $p_1, p_2, \ldots, p_k$ to letter $y$. More formally: for each $i$ ($1 \le i \le k$) Koa sets $A_{p_i} = y$.
     30 
     31    Note that you can only modify letters in string $A$.
     32 
     33 Koa wants to know the smallest number of moves she has to do to make strings equal to each other ($A = B$) or to determine that there is no way to make them equal. Help her!
     34 
     35 Input
     36 
     37 Each test contains multiple test cases. The first line contains $t$ ($1 \le t \le 10$) — the number of test cases. Description of the test cases follows.
     38 
     39 The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of strings $A$ and $B$.
     40 
     41 The second line of each test case contains string $A$ ($|A|=n$).
     42 
     43 The third line of each test case contains string $B$ ($|B|=n$).
     44 
     45 Both strings consists of the first $20$ lowercase English alphabet letters (ie. from a to t).
     46 
     47 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     48 
     49 Output
     50 
     51 For each test case:
     52 
     53 Print on a single line the smallest number of moves she has to do to make strings equal to each other ($A = B$) or $-1$ if there is no way to make them equal.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 5
     61 3
     62 aab
     63 bcc
     64 4
     65 cabc
     66 abcb
     67 3
     68 abc
     69 tsr
     70 4
     71 aabd
     72 cccd
     73 5
     74 abcbd
     75 bcdda
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 2
     82 -1
     83 3
     84 2
     85 -1
     86 ```
     87 
     88 Note
     89 
     90 * In the $1$-st test case Koa:
     91   1. selects positions $1$ and $2$ and sets $A_1 = A_2 = $ b ($\color{red}{aa}b \rightarrow \color{blue}{bb}b$).
     92   2. selects positions $2$ and $3$ and sets $A_2 = A_3 = $ c ($b\color{red}{bb} \rightarrow b\color{blue}{cc}$).
     93 * In the $2$-nd test case Koa has no way to make string $A$ equal $B$.
     94 * In the $3$-rd test case Koa:
     95   1. selects position $1$ and sets $A_1 = $ t ($\color{red}{a}bc \rightarrow \color{blue}{t}bc$).
     96   2. selects position $2$ and sets $A_2 = $ s ($t\color{red}{b}c \rightarrow t\color{blue}{s}c$).
     97   3. selects position $3$ and sets $A_3 = $ r ($ts\color{red}{c} \rightarrow ts\color{blue}{r}$).