COCI '07 Contest 1 #5 Srednji

Points: 12 (partial)

Time limit: 0.6s

Memory limit: 32M

Problem type

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

A subsequence of $A$ ~A~ is a sequence obtained by removing some (possibly none) numbers from the beginning of $A$ ~A~, and then from the end of $A$ ~A~. Calculate how many different subsequences of $A$ ~A~ of odd length have their median equal to $B$ ~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\}$ ~\{5, 1, 3\}~ is $3$ ~3~.

Input Specification

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

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

Output Specification

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

Sample Input 1

5 4
1 2 3 4 5

Sample Output 1

Sample Input 2

6 3
1 2 4 5 6 3

Sample Output 2

Sample Input 3

7 4
5 7 2 4 3 1 6

Sample Output 3

Explanation for Sample Output 3

In the third example, the four subsequences of $A$ ~A~ with median $4$ ~4~ are $\{4\}$ ~\{4\}~, $\{7, 2, 4\}$ ~\{7, 2, 4\}~, $\{5, 7, 2, 4, 3\}$ ~\{5, 7, 2, 4, 3\}~ and $\{5, 7, 2, 4, 3, 1, 6\}$ ~\{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)$ ~\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$ ~1 \le N \le 10^5~, $N^2$ ~N^2~ can be $10^{10}$ ~10^{10}~ in a worst case, which is too slow.