JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree?????
 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 inversionsBIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversionsBIT - 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   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>n; int ele; long int count=0; for(int i=0;i>ele; update(ele,1); count=count+cum(10000000)-cum(ele); } cout<
 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.htmlthis 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
 Re: can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? (response to post by petar1) | Reply nice
 Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm can we solve http://www.spoj.pl/problems/INVCNT/ using binary indexed tree????? Previous Thread  |  Next Thread