Re: [algogeeks] Inversion Count
no all these data structure also take time O(nlogn)
solving this problem using segment tree
map all elements to its index on the sorted array.
ex. 2 3 8 6 1 -- 1 2 4 3 0
intialiize all element in segment tree wid zero
start from the last index of array
whenever u visit a node increase its value by 1 -- one more value came in
this range
if u have go right child then increase the count by number of element in
left child(that is value left node). thats it;
void query(int a, int s, int e, int node, unsigned long long count)
{
int mid = (s+e)1;
tree[node] += 1;
if (s == e) return;
if (a = mid)
{
query(a, s, mid, (node1)+1, count);
}
else
{
count += tree[(node1)+1];
query(a, mid+1, e, (node1)+2, count);
}
return;
}
I have written another code using ur logic its giving correct answer. I m
not getting where u r wrong. :P
#include stdio.h
unsigned long long int merge_and_count (int *a, int start, int mid, int end)
{
int len_a = mid - start + 1;
int len_b = end - mid;
int C[end - start + 1];
int k = 0;
int i = start;
int j = mid + 1;
unsigned long long int count = 0;
int rem = len_a;
while ( i = mid j = end ) {
C[k++] = a[i] a[j] ? a[i] : a[j];
if ( a[j] = a[i] ) {
count += rem;
j++;
} else {
i++;
rem--;
}
}
while ( i = mid ) {
C[k++] = a[i++];
}
while ( j = end ) {
C[k++] = a[j++];
}
for ( i = start; i = end; i++ ) {
a[i] = C[i-start];
}
return count;
}
unsigned long long int sort_and_count(int *a, int start, int end)
{
int mid;
unsigned long long int rA, rB, r;
if ( end == start )
return 0;
else {
mid = (start + end) 1;
rA = sort_and_count (a, start, mid);
rB = sort_and_count (a, mid + 1, end);
r = merge_and_count (a, start, mid, end);
} return (rA+rB+r);
}
int main()
{
int t, n, i;
int a[200100];
scanf (%d, t);
while ( t-- ) {
scanf (%d, n);
for ( i = 0; i n; i++ ) {
scanf (%d, a[i]);
}
printf (%llu\n, sort_and_count(a, 0, n - 1));
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
When I replaced cout with printf in my code, I got AC!! I Should have tried
it earlier itself..
On Fri, May 13, 2011 at 11:51 AM, anshu mishra anshumishra6...@gmail.comwrote:
no all these data structure also take time O(nlogn)
solving this problem using segment tree
map all elements to its index on the sorted array.
ex. 2 3 8 6 1 -- 1 2 4 3 0
intialiize all element in segment tree wid zero
start from the last index of array
whenever u visit a node increase its value by 1 -- one more value came in
this range
if u have go right child then increase the count by number of element in
left child(that is value left node). thats it;
void query(int a, int s, int e, int node, unsigned long long count)
{
int mid = (s+e)1;
tree[node] += 1;
if (s == e) return;
if (a = mid)
{
query(a, s, mid, (node1)+1, count);
}
else
{
count += tree[(node1)+1];
query(a, mid+1, e, (node1)+2, count);
}
return;
}
I have written another code using ur logic its giving correct answer. I m
not getting where u r wrong. :P
#include stdio.h
unsigned long long int merge_and_count (int *a, int start, int mid, int
end)
{
int len_a = mid - start + 1;
int len_b = end - mid;
int C[end - start + 1];
int k = 0;
int i = start;
int j = mid + 1;
unsigned long long int count = 0;
int rem = len_a;
while ( i = mid j = end ) {
C[k++] = a[i] a[j] ? a[i] : a[j];
if ( a[j] = a[i] ) {
count += rem;
j++;
} else {
i++;
rem--;
}
}
while ( i = mid ) {
C[k++] = a[i++];
}
while ( j = end ) {
C[k++] = a[j++];
}
for ( i = start; i = end; i++ ) {
a[i] = C[i-start];
}
return count;
}
unsigned long long int sort_and_count(int *a, int start, int end)
{
int mid;
unsigned long long int rA, rB, r;
if ( end == start )
return 0;
else {
mid = (start + end) 1;
rA = sort_and_count (a, start, mid);
rB = sort_and_count (a, mid + 1, end);
r = merge_and_count (a, start, mid, end);
} return (rA+rB+r);
}
int main()
{
int t, n, i;
int a[200100];
scanf (%d, t);
while ( t-- ) {
scanf (%d, n);
for ( i = 0; i n; i++ ) {
scanf (%d, a[i]);
}
printf (%llu\n, sort_and_count(a, 0, n - 1));
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
Cartesian trees could also help.
Cartesian tree takes O(n) time to build, and if you have the count of how
many nodes are there in a tree rooted at any node, by just having the index
of the element also stored there. Once the cartesian tree is built, just
traverse from the root and find how many nodes are there in the left subtree
from its left child node, and that is the number of inversions for the root
node. Keep doing this for all emenents and kep adding them to a counter.
When you have gone through all the n nodes, you have the total numbr of
inversions, that traversal would also take O(n) time.
When you are at any node, and you know its index in the array, all the
elements to the left sub-tree are inversions because all the elements to the
left of the node are to the left of in the actual array, and that this node
now holds all of the left side of the array rooted at its left child, so all
of them are inversions. And they are the only inversions possible for the
node in questions.
Let me know your views.
Regards
Topo.
On Thu, May 12, 2011 at 5:16 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
@Anshu:
My logic:
during merge step, lets say you have two array left and right (both are
sorted) and you are going to merge it.
l[i] represent the element of left arrray
r[j] represent the element of right array
if (r[j] l[i]) {
increase the inversion count by the number of elements lefts in left
array
put element r[j] into merged array
j++
} else {
no increase in count, just put the element r[i] into merged array
i++;
This will be O(nlogn) solution. Can we do better using BIT or segment
trees? Can you please provide me some hint of how to solve it using segment
trees, I just know the basics of it..
On Thu, May 12, 2011 at 5:00 PM, anshu mishra
anshumishra6...@gmail.comwrote:
explain your logic instead of posting code, use binary index tree or
segment tree or bst to solve this problem.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Topo.
There are days when solitude is a heady wine that intoxicates you with
freedom, others when it is a bitter tonic, and still others when it is a
poison that makes you beat your head against the wall. ~Colette
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
Guard value error.
L[n1]=;
R[n2]=999;
R[n2] may be merged and counted, if L[1..n1-1] has 999.
On 2011-5-12 19:18, Akshata Sharma wrote:
I tried to solve this problem using merge sort logic, the algorithm is
same as merge sort, only change is in the merge step where i am
counting the inversion_count.
I tested some test cases and I am getting correct answer, but I am
getting WA on spoj. Is the code incorrect or any test case whr it fails?
http://www.spoj.pl/problems/INVCNT/
#includeiostream
using namespace std;
long inversion_count = 0;
void merge(long arr[], long p, long q, long r)
{
long n1 = q-p+1;
long n2 = r-q;
long L[n1];
long R[n2];
for(long i=0;in1;i++)
{
L[i]=arr[p+i];
}
L[n1]=;
for(long i=0;in2;i++)
{
R[i]=arr[q+1+i];
}
R[n2]=999;
long i=0;
long j=0;
long k=p;
while(k=r)
{
if(L[i]=R[j])
{
arr[k]=L[i];
i++;
k++;
}
else if(L[i]R[j])
{
arr[k]=R[j];
j++;
k++;
inversion_count+=n1-i;
}
}
}
void merge_sort(long arr[], long p, long r)
{
if(pr)
{
long q = (p+r)/2;
merge_sort(arr,p,q);
merge_sort(arr,q+1,r);
merge(arr,p,q,r);
}
}
int main()
{
int t;
char a;
long n,i;
long arr[22];
scanf(%d,t);
while(t--)
{
scanf(%ld,n);
for(i=0;in;i++)
scanf(%ld,arr[i]);
merge_sort(arr,0,n-1);
coutinversion_count\n;
inversion_count=0;
}
return 0;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups Algorithm
Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
@Terence:
I dont know what a guard value error is, but by mistake I wrote R[n2] =
999, should be one more 9 since array value can be =10^7. May be test
cases have values less than 999 that got me AC.
On Thu, May 12, 2011 at 5:20 PM, Terence technic@gmail.com wrote:
Guard value error.
L[n1]=;
R[n2]=999;
R[n2] may be merged and counted, if L[1..n1-1] has 999.
On 2011-5-12 19:18, Akshata Sharma wrote:
I tried to solve this problem using merge sort logic, the algorithm is
same as merge sort, only change is in the merge step where i am counting the
inversion_count.
I tested some test cases and I am getting correct answer, but I am
getting WA on spoj. Is the code incorrect or any test case whr it fails?
http://www.spoj.pl/problems/INVCNT/
#includeiostream
using namespace std;
long inversion_count = 0;
void merge(long arr[], long p, long q, long r)
{
long n1 = q-p+1;
long n2 = r-q;
long L[n1];
long R[n2];
for(long i=0;in1;i++)
{
L[i]=arr[p+i];
}
L[n1]=;
for(long i=0;in2;i++)
{
R[i]=arr[q+1+i];
}
R[n2]=999;
long i=0;
long j=0;
long k=p;
while(k=r)
{
if(L[i]=R[j])
{
arr[k]=L[i];
i++;
k++;
}
else if(L[i]R[j])
{
arr[k]=R[j];
j++;
k++;
inversion_count+=n1-i;
}
}
}
void merge_sort(long arr[], long p, long r)
{
if(pr)
{
long q = (p+r)/2;
merge_sort(arr,p,q);
merge_sort(arr,q+1,r);
merge(arr,p,q,r);
}
}
int main()
{
int t;
char a;
long n,i;
long arr[22];
scanf(%d,t);
while(t--)
{
scanf(%ld,n);
for(i=0;in;i++)
scanf(%ld,arr[i]);
merge_sort(arr,0,n-1);
coutinversion_count\n;
inversion_count=0;
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
@Topojoy Biswas:
If A = [3, 1, 5, 2, 4] then CT (A) is:
1
/ \
3 2
/ \
54
counting the number of nodes in the tree rooted at each node,
1(5)
/\
3(1) 2(3)
/ \
5(1) 4(1)
where the numbers in () denotes the number of nodes in tree rooted at that
node.
Once the cartesian tree is built, just traverse from the root and find how
many nodes are there in the left subtree from its left child node, and that
is the number of inversions for the root node
Now, the number of inversions for each node according to you is:
1 - 1
3 - 0
2 - 1
5 - 0
4 - 0
so in total, 2 inversion pairs. But thats not correct. Correct me if I am
wrong.
On Sat, May 14, 2011 at 11:19 AM, Akshata Sharma
akshatasharm...@gmail.comwrote:
@Terence:
I dont know what a guard value error is, but by mistake I wrote R[n2] =
999, should be one more 9 since array value can be =10^7. May be test
cases have values less than 999 that got me AC.
On Thu, May 12, 2011 at 5:20 PM, Terence technic@gmail.com wrote:
Guard value error.
L[n1]=;
R[n2]=999;
R[n2] may be merged and counted, if L[1..n1-1] has 999.
On 2011-5-12 19:18, Akshata Sharma wrote:
I tried to solve this problem using merge sort logic, the algorithm is
same as merge sort, only change is in the merge step where i am counting the
inversion_count.
I tested some test cases and I am getting correct answer, but I am
getting WA on spoj. Is the code incorrect or any test case whr it fails?
http://www.spoj.pl/problems/INVCNT/
#includeiostream
using namespace std;
long inversion_count = 0;
void merge(long arr[], long p, long q, long r)
{
long n1 = q-p+1;
long n2 = r-q;
long L[n1];
long R[n2];
for(long i=0;in1;i++)
{
L[i]=arr[p+i];
}
L[n1]=;
for(long i=0;in2;i++)
{
R[i]=arr[q+1+i];
}
R[n2]=999;
long i=0;
long j=0;
long k=p;
while(k=r)
{
if(L[i]=R[j])
{
arr[k]=L[i];
i++;
k++;
}
else if(L[i]R[j])
{
arr[k]=R[j];
j++;
k++;
inversion_count+=n1-i;
}
}
}
void merge_sort(long arr[], long p, long r)
{
if(pr)
{
long q = (p+r)/2;
merge_sort(arr,p,q);
merge_sort(arr,q+1,r);
merge(arr,p,q,r);
}
}
int main()
{
int t;
char a;
long n,i;
long arr[22];
scanf(%d,t);
while(t--)
{
scanf(%ld,n);
for(i=0;in;i++)
scanf(%ld,arr[i]);
merge_sort(arr,0,n-1);
coutinversion_count\n;
inversion_count=0;
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
explain your logic instead of posting code, use binary index tree or segment tree or bst to solve this problem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
@Anshu:
My logic:
during merge step, lets say you have two array left and right (both are
sorted) and you are going to merge it.
l[i] represent the element of left arrray
r[j] represent the element of right array
if (r[j] l[i]) {
increase the inversion count by the number of elements lefts in left array
put element r[j] into merged array
j++
} else {
no increase in count, just put the element r[i] into merged array
i++;
This will be O(nlogn) solution. Can we do better using BIT or segment trees?
Can you please provide me some hint of how to solve it using segment trees,
I just know the basics of it..
On Thu, May 12, 2011 at 5:00 PM, anshu mishra anshumishra6...@gmail.comwrote:
explain your logic instead of posting code, use binary index tree or
segment tree or bst to solve this problem.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
