Algorithm
problem link- https://www.spoj.com/problems/MCHAOS/
MCHAOS - Chaos Strings
| English | Vietnamese |
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.
Input
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.
Output
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++).
Sample
input
2
lopta
kugla
output
0
input
4
lova
novac
aron
sunce
output
3
input
14
branimir
vladimir
tom
kruz
bred
pit
zemlja
nije
ravna
ploca
ko
je
zapalio
zito
output
48
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define F first
#define S second
#define sp ' '
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e5+5;
int n;
int BIT[MAXN+1];
void update(int idx, int val){
while(idx <= MAXN){
BIT[idx] += val;
idx += idx&-idx;
}
}
int query(int idx){
int sum = 0;
while(idx > 0){
sum += BIT[idx];
idx -= idx&-idx;
}
return sum;
}
int main(){
io;
cin >> n;
string input[n];
string rev[n];
FOR(i,n){
cin >> input[i];
rev[i] = input[i];
reverse(rev[i].begin(), rev[i].end());
}
sort(input, input+n);
sort(rev, rev+n);
ll ans = 0;
unordered_map<string, int> M;
FOR(i, n){
reverse(input[i].begin(), input[i].end());
M[rev[i]] = (i+1);
}
FOR(i, n){
// cout << input[i] << endl;
// cout << M[input[i]] << endl;
ans += query((int)1e5+1) - query(M[input[i]]);
// cout << ans << endl;
update(M[input[i]], 1);
}
cout << ans << endl;
return 0;
}Input
lopta
kugla
Demonstration
SPOJ Solution-Chaos Strings-Solution in C, C++, Java, Python