How to solve SEAINVS ?

Can someone explain how to solve SEAINVS ? This is what I did :

Given two subarrays in the array, we need to find the number of permutations of the first subarray such that every element in it is smaller than the corresponding element in the second one. I sorted both the subarrays first, because finding the number of permutations of the first array with respect to any permutation of the second one would give the same answer. Then starting from the first position I just found out the number of ways that I can fill each position, and multiplied those to get the answer. But this is not fast enough for the large subtask.

1 Like

Your main idea is completely right.

To pass all tests you need work with intervals of consecutive elements.

You have two sorted array, let it be A and B. Imagine that their consecutive elements are united in intervals. Now you have two array of non-intersecting intervals, let it be A_S and B_S.

You can processed A_S and B_S in similar way like A and B, each answer’s multiplier will be presents the product of consecutive integers.

Number of consecutive intervals for each range [l, r] is O(\sqrt{K}). Where K - is number of inversions. Use segment tree to fast calculate arrays of intervals.

4 Likes

As @skyfire said this was indeed the main idea.

In order to avoid the construction and sorting of the two subarrays over all queries, I constructed a segment tree, where [L,R] stores the sorted subarray between [L,R]. I think it is called a Merge Sort Tree.

So, I can obtain the subarrays [L1, R1] and [L2, R2] quite easily. Now to use the idea of PnC (which is mentioned by you), I have to find for the kth number in [L2, R2], how many numbers are less than that number in the interval [L1, R1]. The result will be used in the distribution of the numbers (thereby finding the number of permutations). Note that we need to take care of the distribution for the smaller number in [L2, R2] before the number larger than it. (You must have realized that as well).

Now to find the kth number in the range [L2, R2] in my tree. This is equivalent to finding the kth order statistic in sorted [L2, R2]. Refer to the problem “MKTHNUM” - http://www.spoj.com/problems/MKTHNUM/. https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/ provides a nice explanation to this problem. Rest all can be done using the lower_bound and the upper_bound functions (logarithmic time).

My implementation - https://www.codechef.com/viewsolution/12806490

However as you can see this fetched me only 70 points. I need help in figuring out why that happened.

To get the rest 30 points, I had to use brute force :stuck_out_tongue:

100 points - https://www.codechef.com/viewsolution/12806668

P.s. This was the first ever hard level problem that I solved :smiley:

2 Likes

@utkarsh1997 , your 70-points code may be failing for some corner cases.

2 Likes

I see. Could it be that the test cases designed for 70 points subtask weren’t actually that strong?

1 Like

I understand that having a Merge Sort Tree will avoid sorting the ranges for each query,(correct me if I’m wrong) and you can quickly find how many numbers in range [L1,R1] are smaller than some number ‘k’ in [L2,R2]. But aren’t you doing that for every number in [L2,R2] (going from smallest to largest in the sorted order) ? wouldn’t that be too slow ?

1 Like

No. That will not be slow. Reason being that finding k’th element costs me O(logN) per query. Finding the number of elements smaller than the k’th element is O((logN)^2). So that shouldn’t be a problem.

final solution:
for 30 point we know must sort two interval [l1,r1] , [l2,r2] then find ans easily…
but for full point : in statement say "“original constraints plus additionally 0 ≤ number of pairs i, j (1 ≤ i < j ≤ N, Pi > Pj) over all test cases ≤ 3*10^6"” … this show our two interval have many consecutive element! so we can use segment tree and a simple merge for find all interval consecutive element for two give interval… then use vector contain interval [l2,r2] for calculate answers…
https://www.codechef.com/viewsolution/15970708