codeforces-scrape

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

1669E.md (2247B)


      1 Source: https://codeforces.com/problemset/problem/1669/E
      2 
      3 E. 2-Letter 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 Given $n$ strings, each of length $2$, consisting of lowercase Latin alphabet letters from 'a' to 'k', output the number of pairs of indices $(i, j)$ such that $i \lt j$ and the $i$-th string and the $j$-th string differ in exactly one position.
     22 
     23 In other words, count the number of pairs $(i, j)$ ($i \lt j$) such that the $i$-th string and the $j$-th string have exactly one position $p$ ($1 \leq p \leq 2$) such that ${s_{i}}_{p} \neq {s_{j}}_{p}$.
     24 
     25 The answer may not fit into 32-bit integer type, so you should use 64-bit integers like long long in C++ to avoid integer overflow.
     26 
     27 Input
     28 
     29 The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of strings.
     32 
     33 Then follows $n$ lines, the $i$-th of which containing a single string $s_i$ of length $2$, consisting of lowercase Latin letters from 'a' to 'k'.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case, print a single integer — the number of pairs $(i, j)$ ($i \lt j$) such that the $i$-th string and the $j$-th string have exactly one position $p$ ($1 \leq p \leq 2$) such that ${s_{i}}_{p} \neq {s_{j}}_{p}$.
     40 
     41 Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 6
     51 
     52 ab
     53 
     54 cb
     55 
     56 db
     57 
     58 aa
     59 
     60 cc
     61 
     62 ef
     63 
     64 7
     65 
     66 aa
     67 
     68 bb
     69 
     70 cc
     71 
     72 ac
     73 
     74 ca
     75 
     76 bb
     77 
     78 aa
     79 
     80 4
     81 
     82 kk
     83 
     84 kk
     85 
     86 ab
     87 
     88 ab
     89 
     90 5
     91 
     92 jf
     93 
     94 jf
     95 
     96 jk
     97 
     98 jk
     99 
    100 jk
    101 ```
    102 
    103 Output
    104 
    105 ```
    106 5
    107 6
    108 0
    109 6
    110 ```
    111 
    112 Note
    113 
    114 For the first test case the pairs that differ in exactly one position are: ("ab", "cb"), ("ab", "db"), ("ab", "aa"), ("cb", "db") and ("cb", "cc").
    115 
    116 For the second test case the pairs that differ in exactly one position are: ("aa", "ac"), ("aa", "ca"), ("cc", "ac"), ("cc", "ca"), ("ac", "aa") and ("ca", "aa").
    117 
    118 For the third test case, the are no pairs satisfying the conditions.