JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? | Reply
can we solve spoj problem http://www.spoj.pl/problems/INVCNT/ using binary indexed tree???? i have gone through topcoder tutorials of binary indexed tree and want to try some problems for practice of binary indexed tree........is it possible to solve this problem using binary indexed tree......plz suggest me some logic?????
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by mukul_gupta) | Reply
Yes, it can be solved with BIT. First compress the numbers(they can be up to 10^7 but their count is at most 200000). You go through each number in the permutation. You insert 1 in the BIT at the corresponding position(if the number is 3, insert 1 at the third position). The freshly inserted number gives query(num + 1, N) inversions.

Let's take the first example - 3, 1, 2. At the beginning the BIT is 0, 0, 0. After inserting 3 the BIT is 0, 0, 1. After inserting 1 the BIT is 1, 0, 1 which gives 1 inversion. After inserting 2, the BIT is 1, 1, 1 which gives again 1 inversion. 1 + 1 = 2 total inversions.

Let's take the second example - 2, 3, 8, 6, 1.
BIT - 0, 0, 0, 0, 0, 0, 0, 0. Insert 2:
BIT - 0, 1, 0, 0, 0, 0, 0, 0. Insert 3:
BIT - 0, 1, 1, 0, 0, 0, 0, 0. Insert 8:
BIT - 0, 1, 1, 0, 0, 0, 0, 1. Insert 6: +1 inversions
BIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversions
BIT - 1, 1, 1, 0, 0, 1, 0, 1.

P.S. In the examples I haven't included the compression for clarity.
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by petar1) | Reply
thanx petar1 ,i have implemented in same way but it is giving me wrong answer,also i didn't get that compression part.....can u plz explain it again and suggest me some test cases where this code fails...thanx in advance...
#include<iostream>
 
using namespace std;
 
int ftree[10000001]={0};
 
int cum(int idx){
	int result=0;
	while(idx>0){
		result=result+ftree[idx];
		idx=idx-(idx & -idx);
	}
	
	return result;
}
 
void update(int idx,int val){
	while(idx<=10000000){
		ftree[idx]=ftree[idx]+val;	
		idx=idx+(idx & -idx);
	}
}
 
int main()
{
	int t;
	cin>>t;
	for(int w=0;w<t;w++){
		int n;
		cin>>n;
		int ele;
		long int count=0;
		for(int i=0;i<n;i++){
			cin>>ele;
			update(ele,1);
			count=count+cum(10000000)-cum(ele);
		}
		cout<<count<<"\n";
		for(int i=1;i<=10000000;i++)
			ftree[i]=0;
	}
	return 0;
}
 
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by mukul_gupta) | Reply
Change long int to long long and you will get accepted:)

P.S. Compression is not needed here. But it is an useful technique which can help you in other problems. I mean that 8 4 6 can be encoded to 3 1 2. You sort the numbers - 4 6 8 and you assign 1 to 4, 2 to 6 and 3 to 8.
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by petar1) | Reply
thanx petar1 got AC :) can u plz suggest some more problems of spoj which can be solved using binary indexed tree....i need some problems for practice.....
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by mukul_gupta) | Reply
i think this will help you,

http://problemclassifier.appspot.com/
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by innocentdrmz) | Reply
thanx innocentdrmz......
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by mukul_gupta) | Reply
http://pavelsimo.blogspot.in/2012/09/counting-inversions-in-array-using-BIT.html

this will help..
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by petar1) | Reply
why is there no need of compression here?
Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by suryansh677) | Reply
coz array of this size can be made
RSS