SPOJ RATING WA

general
,
1

[my solution][1]
[correct solution][2]
The algorithm i used-
i have sorted the pair of rating in non decreasing order of the left column,i.e. according to open rating.
BIT stores the freq of second column,i.e.,high school rating.
Then i loop from n to 1 and check how how many ratings are less than pair[i].rating2.
Then i use binary search to find out how many rating2 are equal to the ith rating.
Also i check how many rating1 are same
I tried many test cases.
If anyone can provide a test case that would be great.
Thanks
[1]: 5ZUP5a - Online IDE & Debugging Tool - Ideone.com
[2]: v6LBMt - Online C++ Compiler & Debugging Tool - Ideone.com

2

Hello abeyaar

I think i can answer this question well…

Let me first refine the problem statement … Given N pairs of coordinates (X,Y) for each of the coordinate Xi,Yi we need to find the number of coordinates (Xj,Yj) which follows the any of the following conditions.

  1. Xj < Xi and Yj < Yi
  2. Xj == Xi and Yj < Yi
  3. Xj < Xi and Yj == Yi

I have an idea to solve this problem using Binary Indexed Tree or Segment Tree without the use of binary search. Here,as you can see the values of the coordinates are in the range from [1,105] otherwise we can first apply coordinate compression on the coordinates and can solve the problem in the similiar fashion.

Just for the sake of convenience i am considering that all the coordinates are pairwise distinct.

Here is the simplest implementation which i could think off. (considering all the cases and Accepted solution)

Step1: First of all we can sort the pair of coordinates according to the X values. Once we have the array sorted according to the X values. We can always gurantee that the current coordinate is greater than all of the previous coordinates atleast in X values.

Step2: To count the number of coordinates for which current coordinate is also greater in Y values, we have also maintained a standard BIT which can support point update and range query. we have to just query up in the range [1,Ycurrent] to get the count of all the coordinates which are smaller than the current coordinate in both X and Y .

Case of duplicacy can be easily removed as i did in my code. Have a look please :smiley:

If you find anything difficult,feel free to ask …

2 Likes
3

Thank You i got AC :slight_smile: thanks a lot. :slight_smile:
Can you look into this??
http://discuss.codechef.com/questions/60873/spoj-picad-wa