Hi all,
I was trying to solve http://www.spoj.com/problems/MCHAOS/. I think my solution is correct with the given constraints. I got TLE with BIT and STL maps initially in the 10th test case. Then I tried to optimize by converting strings into longs (preserving their order) and sorting long long[] instead of vector<string>. This gave WA. I believe there is some problem in the hash() function but I was not able to find it. Can someone help or suggest some other optimization?
Here are the two versions of the code...
#include <stdio.h>
#include <string>
#include <map>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;
const int NMAX = 100000+5;
ll BIT[NMAX];
int LIM = 0;
map<ll, int> dict;
char vs[NMAX][11];
vector<string> vecs, seq;
ll read (int v) {
ll sum = 0;
while (v) {
sum += BIT[v];
v -= v &-v;
}
return sum;
}
void update (int v, int val) {
while (v <= LIM) {
BIT[v] += val;
v += v & -v;
}
}
string reverse(string s) {
char c;
int l = s.length();
for (int i=0; i <= (l-1)/2; i++) {
c = s[i];
s[i] = s[l-i-1];
s[l-i-1] = c;
}
return s;
}
ll hash(string s){
ll sum = 0;
for (int i = 0; i < s.length(); i++) sum = sum * 26 + s[i]-26 + 1;
for (int i = s.length(); i <= 10; i++) sum *= 26;
return sum;
}
int main () {
int N;
memset(BIT, 0, sizeof(BIT));
memset(vs, 0, sizeof(vs));
cin >> N;
string s;
for (int i=0; i < N; i++) scanf("%s", vs[i]);
for (int i=0; i < N; i++) vecs.push_back(vs[i]);
sort(vecs.begin(), vecs.end());
for (int i = 0; i < N; i++) {vecs[i] = reverse(vecs[i]);seq.push_back(vecs[i]);}
sort(seq.begin(), seq.end());
for (int i = 0; i < N; i++) dict[hash(seq[i])] = i+1;
LIM = N+1;
ll bad_pairs = 0;
for (int i = N-1; i >= 0; i--) {
bad_pairs += read(dict[hash(vecs[i])]);
update(dict[hash(vecs[i])], 1);
}
cout << bad_pairs << endl;
return 0;
}
After the optimization ...
#include <stdio.h>
#include <string>
#include <map>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long int ull;
const int NMAX = 100000+5;
ull BIT[NMAX];
int LIM = 0;
map<ull, int> dict,d2;
char vs[NMAX][12], sq[NMAX][12];
ull vecs[NMAX], seq[NMAX];
ull read (int v) {
ull sum = 0;
while (v) {
sum += BIT[v];
v -= (v &-v);
}
return sum;
}
void update (int v, int val) {
while (v <= LIM) {
BIT[v] += val;
v += (v & -v);
}
}
void reverse(char *s) {
char c;
int l = strlen(s);
for (int i=0; i <= l/2-1; i++) {
c = s[i];
s[i] = s[l-i-1];
s[l-i-1] = c;
}
}
ull hash(char *s){
ull sum = 0;
for (int i = 0; i < strlen(s); i++) sum = sum * 26 + s[i]-'a'+1;
for (int i = strlen(s); i < 10; i++) sum *= 26;
return sum;
}
int main () {
int N;
memset(BIT, 0, sizeof(BIT));
memset(vecs, 0, sizeof(vecs));
memset(seq, 0, sizeof(seq));
cin >> N;
string s;
for (int i=0; i < N; i++) scanf("%s", vs[i]);
for (int i=0; i < N; i++) {vecs[i] = hash(vs[i]);d2[vecs[i]] = i;}
sort(vecs, vecs+N);
for (int i = 0; i < N; i++) {
strcpy(sq[i],vs[d2[vecs[i]]]);
reverse(sq[i]);
seq[i] = hash(sq[i]);
}
sort(seq, seq+N);
for (int i = 0; i < N; i++) dict[seq[i]] = i+1;
LIM = N+1;
ull bad_pairs = 0;
for (int i = N-1; i >= 0; i--) {
bad_pairs += read(dict[hash(sq[i])]);
update(dict[hash(sq[i])], 1);
}
cout << bad_pairs << endl;
return 0;
}
