GMEDIAN - Editorial (Unofficial)

general
, , , ,
21

Since we have to sort each subsequence
to find its median, we will sort our
original sequence (i.e. A1,A2,…,AN) at
first itself. The ordering won’t
change. For example, the good
(desired) subsequences in the sequence
[9,5,7,6,8,1] are same as that in the
sequence [1,5,6,7,8,9].

There is a logical error here. I assume that you mean that the number of good subsequences is independent of the ordering of the sequence. But consider [1, 2, 3, 2, 3] and its ordered counterpart [1, 2, 2, 3, 3]. In the former, [1, 2, 3, 2] and [1, 2, 2, 3] must be counted as two distinct good subsequences, while in the latter, [1, 2, 2, 3] is the only corresponding good subsequence.

I am surprised that this solution gets AC. Either the test cases were weak or I don’t understand the problem correctly.

22

I gather that this solution counts [1, 2, 2, 3] twice for the sequence [1, 2, 2, 3, 3] (in the step where we choose 1 number form the 2 numbers to the right of 2’s, we use 2C1 which counts both the 3’s individually). But, isn’t this wrong? The problem becomes a lot more difficult if we try to take into account that many numbers can be non-distinct and then the Vandermonde’s identity expression is invalidated!

23

In [1,2,2,3,3] -> [1,2,2,3] (with 3 of index 3) and [1,2,2,3] (with 3 of index 4), both are good subsequence

24

Its late, but thanks!:slight_smile: