PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:Hard PREREQUISITES:Matrix Algebra, Binary merging, heaps. PROBLEM:You are given a $N$ pairs of integers, ($L[i], R[i]$) $i$ ranging from 1 to $N$. Two players play a game. Alex can choose a permutation of integers from 1 to $N$, P[1...$N$], if and only if $L[i] <= P[i] <= R[i]$ for all $1<=i<=N$ and the number of inversions in this permutation is even. Similarly, the number of inversions should be odd for Fedya. You have to find, who among Alex and Fedya has more number of permutations. If both have same, then the answer is a Draw. EXPLANATION:Let $Pp$ = the number of permutations that are suitable for Alex, $Np$ = the number of permutations that are suitable for Fedya. By the definition, if we replace black cells with 1, and white with 0, (and obtain the matrix $A$), then determinant of matrix $A = Pp  Np$. So the problem is about the calculation of the $det A$. The first point is that the determinant will be either 1, 0, or +1. The proof can be seen in the later part of the editorial. In the matrix $A$, all the elements in the columns from $L[i]$ to $R[i]$, in the $i^{th}$ row will be equal to 1. Let us maintain an array of MinHeaps, where heap[i] is a Minheap that stores all the segments which start in the $i^{th}$ column. In order to calculate the determinant, you can follow the below strategy:
So, doing this process N times, we'll get the solution to the problem. If we see our new matrix we get in step 3 has similar properties of original matrix, i.e, all the 1s in the matrix are present contiguously in each row. The determinant of matrix of size 1 will be either 1 or 0. So by mathematical induction we can prove that if matrix of size N  1 can have values {1, 0, 1} only, then matrix of size N can also have values {1, 0, 1} only, because it just gets multiplied by (1)^(row number + column number) or 0. Now the important part is if we directly shift all the elements of one heap to another we will have a complexity of $O(N * N * logN)$, because there will be $O(N * N)$ shifts in the worst case, and each shift takes O(logN) time. So rather than shifting all elements from heap[1] to heap[X + 1] directly, lets maintain pointers to heaps for each column and then we can just shift all the elements in the smaller heap (whichever is the one, i.e either the heap pointed by 1st column or $X$ + 1th column) to the larger heap, and point $X$ + 1th column to larger heap. This ensures that there will be only $N * log N$ shifts in the worst case, because whenever an element is shifted from one heap to the other, the size of the heap it is present will become more than doubled, so any particular element will be shifted at most $log N$ times. Writing a heap class will be very helpful in implementation. AUTHOR'S AND TESTER'S SOLUTIONS:To be posted soon.
This question is marked "community wiki".
asked 15 Apr '15, 03:11

the proof for det(A)= PpNp answered 17 Apr '15, 19:12
2
This comes directly from the definition of the determinant, which is a sum of products of elements of permutations multiplied by their "sign", where the "sign" is 1 if it has an even number of inversions, 1 if it has an odd number of inversions. To be more precise, let's consider each of the N! permutations and the elements A(i,p(i)). If not all of its elements are 1 (i.e. black), then the product of their elements is zero, so they don't count when computing the determinant. If all their elements are 1 then the product of the elements is 1, and they contribute to the determinant by 1 or +1.
(17 Apr '15, 19:47)
I was unaware of this definition of Determinant , which seeing on net seems to be quite a popular definition . :)
(17 Apr '15, 19:52)
@mugurelionut yes, that's true! It was difficult to see this and relate it to the problem. Thanks for the explanation. Besides, you are very competitive.
(18 Apr '15, 15:11)

but i am not getting that this is in HARD categeries of problem,,because of finding determinent of matrix or many of person dont know this predefined defnation,,,plz tell me how can i get logic in competition for this question if i have never heard this propertie?? answered 18 Apr '15, 22:52
