MCHAOS - Chaos Strings
Little Lovro likes to play games with words. During the last few weeks he realized that some words don't like each other.
The words A and B don't like each other if the word A is lexicographically before the word B, but the word B' is lexicographically before the word A', where X' stands for the word X reversed (if X="kamen" then X'="nemak"). For example, the words "lova" and "novac" like each other, but the words "aron" and "sunce" don't like each other.
Given some set of the words, we define the degree of chaos of the set as the number of pairs of different words that don't like each other.
Write a program that, given a set of words, finds the chaos degree for the set.
The first line of input contains an integer N, 2 ≤ N ≤ 100 000.
Each of the following N lines contains one word – a sequence of at most 10 lowercase letters of the English alphabet ('a'-'z'). There will be no two identical words in the set.
The first and only line of output should contain a single integer – the chaos degree of the given set of words.
Note: use 64-bit signed integer type (int64 in Pascal, long long in C/C++).
AC with offline processing & BIT (without fast io)
AC w/ BIT and cin, cout without optimizing
can also be done using BIT , nice problem :)
AC with stl vector and fast IO. TLE without fast IO.
Those who are facing problems of TLE with maps-Try using unordered_map as there is no requirement of sorting here while assigning numbers to the strings.Last edit: 2017-06-08 07:37:16
Awesome problem, AC in one go!
Learnt more about hashing!!! Nice I/o optimisation problem.
Don't use any STL and you'll succeed.
No accepted solution except c/c++/fpc, relax the time limit to allow other languages, please.
One cool solution is converting the strings in long long variables :)