PROBLEM LINK:
Author: Sergey Kulik
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran
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 Min-Heaps, where heap[i] is a Min-heap that stores all the segments which start in the i^{th} column.
In order to calculate the determinant, you can follow the below strategy:
- Pick a segment of 1’s that starts in the first column, if there are a many of them, pick the shortest one, just pop out the minimum element in the heap[1].
- Let its length be X, Now you can subtract this segment from all the segments that start at the first column as well, but since they weren’t chosen, they’re longer than this one (if there is a segment with the equal length, the determinant is zero). Subtracting all the segments will be same as shifting all the segments from heap[1] to heap[X + 1].
- Now we’ve obtained the situation, where there is only one row that has non-zero element in the first column. Here, according to Laplace’s theorem, we can just eliminate the first column and this row and find the det of new matrix and multiply it by some (-1)^(row_number + column_number) and go on, but here we will have only the matrix of the size that is one unit less than the size of the original matrix.
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.
