All submissions for this problem are available.
Little John just had his first class in school. He was taught first 20 letters of English alphabet and was asked to make words from these alphabets. Since he doesn't know many dictionary words, he quickly finished this work by making random strings from these alphabets.
Now while other kids are busy creating their words, John gets curious and puts all the strings he created in a list and named it X.
He picks two indices 'i' and 'j' ( not necessarily distinct). He assigns A as X[i] and B as X[j]. He then concatenates both the strings to create a new string C ( = A + B ). He calls a string "super string" if that string contains all the 20 letters of English alphabet he has just learnt,atleast once.
Given the strings of the list, can you tell him how many such unordered pairs (i,j) he can choose such that string C is a super string.
- The first line of the input contains a single integer, N denoting the number of strings in X
- Next N lines contain one string each, i.e, the strings in X.
- Output a single integer, the number of unordered pairs (i,j) , not necessarily distinct such that they follow the above condition.
- 1 ≤ N ≤ 105
- 1 ≤ |S| ≤ 50 where |S| is the length of any string in input
- Each string contains characters only from first 20 alphabets of Uppercase English alphabets i.e. A,B, ... T
Input: 4 ACOKIPNEJOIR PFEKKRRA ACOKIPNEJOIR TSBCDFGHJLMQ Output: 2
The first string (ACOKIPNEJOIR), if concatenated with the fourth string (TSBCDFGHJLMQ) contains all alphabets from A,B...T. Similarly for the 3rd string and 4th string.
On the other hand consider pair (1,1) :
Here A=ACOKIPNEJOIR and B=ACOKIPNEJOIR
C=ACOKIPNEJOIRACOKIPNEJOIR,which doesn't contain several alphabets, for example 'B' and 'D' are absent in C, therefore it is not a valid pair.
Similarly,no other pairs satisfy this criteria.
Therefore the valid pairs are (1,4) and (3,4).
Note: Large I/O data . Use faster I/O methods . (For example: scanf in C++)
|Tags||bitmasking, dynamic-programming, ipc15p3b, medium, sarveshmahajan|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions