codeforces-scrape

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

1045I.md (2232B)


      1 Source: https://codeforces.com/problemset/problem/1045/I
      2 
      3 I. Palindrome Pairs
      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 After learning a lot about space exploration, a little girl named Ana wants to change the subject.
     22 
     23 Ana is a girl who loves palindromes (string that can be read the same backwards as forward). She has learned how to check for a given string whether it's a palindrome or not, but soon she grew tired of this problem, so she came up with a more interesting one and she needs your help to solve it:
     24 
     25 You are given an array of strings which consist of only small letters of the alphabet. Your task is to find how many palindrome pairs are there in the array. A palindrome pair is a pair of strings such that the following condition holds: at least one permutation of the concatenation of the two strings is a palindrome. In other words, if you have two strings, let's say "aab" and "abcac", and you concatenate them into "aababcac", we have to check if there exists a permutation of this new string such that it is a palindrome (in this case there exists the permutation "aabccbaa").
     26 
     27 Two pairs are considered different if the strings are located on different indices. The pair of strings with indices $(i,j)$ is considered the same as the pair $(j,i)$.
     28 
     29 Input
     30 
     31 The first line contains a positive integer $N$ ($1 \le N \le 100\,000$), representing the length of the input array.
     32 
     33 Eacg of the next $N$ lines contains a string (consisting of lowercase English letters from 'a' to 'z') — an element of the input array.
     34 
     35 The total number of characters in the input array will be less than $1\,000\,000$.
     36 
     37 Output
     38 
     39 Output one number, representing how many palindrome pairs there are in the array.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3  
     47 aa  
     48 bb  
     49 cd
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 1
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 6  
     62 aab  
     63 abcac  
     64 dffe  
     65 ed  
     66 aa  
     67 aade
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 6
     74 ```
     75 
     76 Note
     77 
     78 The first example:
     79 
     80 1. aa $+$ bb $\to$ abba.
     81 
     82 The second example:
     83 
     84 1. aab $+$ abcac $=$ aababcac $\to$ aabccbaa
     85 2. aab $+$ aa $=$ aabaa
     86 3. abcac $+$ aa $=$ abcacaa $\to$ aacbcaa
     87 4. dffe $+$ ed $=$ dffeed $\to$ fdeedf
     88 5. dffe $+$ aade $=$ dffeaade $\to$ adfaafde
     89 6. ed $+$ aade $=$ edaade $\to$ aeddea