COCI '07 Contest 1 #5 Srednji

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

Consider a sequence A of integers, containing N integers between 1 and N. Each integer appears exactly once in the sequence.

A subsequence of A is a sequence obtained by removing some (possibly none) numbers from the beginning of A, and then from the end of A. Calculate how many different subsequences of A of odd length have their median equal to B. The median of a sequence is the element in the middle of the sequence after it is sorted. For example, the median of the sequence \{5, 1, 3\} is 3.

Input Specification

The first line contains two integers, N (1 \le N \le 100\,000) and B (1 \le B \le N).

The second line contains N integers separated by spaces, the elements of sequence A.

Output Specification

Output the number of subsequences of A whose median is B.

Sample Input 1

5 4
1 2 3 4 5

Sample Output 1

2

Sample Input 2

6 3
1 2 4 5 6 3

Sample Output 2

1

Sample Input 3

7 4
5 7 2 4 3 1 6

Sample Output 3

4

Explanation for Sample Output 3

In the third example, the four subsequences of A with median 4 are \{4\}, \{7, 2, 4\}, \{5, 7, 2, 4, 3\} and \{5, 7, 2, 4, 3, 1, 6\}.


Comments


  • 0
    septence123  commented on March 13, 2017, 1:05 a.m. edit 2

    I currently have an \mathcal{O}(N^2) algorithm in Python. Is there a better time complexity in which I can solve it? or is Python just too slow for this problem?


    • 7
      Kirito  commented on March 13, 2017, 1:22 a.m.

      Since 1 \le N \le 10^5, N^2 can be 10^{10} in a worst case, which is too slow.