BWGAME - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. 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].
  2. 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].
  3. 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.

5 Likes

Nice problem :slight_smile:

the proof for det(A)= Pp-Np

1 Like

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.

2 Likes

I was unaware of this definition of Determinant , which seeing on net seems to be quite a popular definition . :slight_smile:

@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.

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??