COCI '07 Contest 1 #5 Srednji

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


  • 1
    septence123  commented on March 12, 2017, 9:05 p.m. edited

    I currently have a 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?


    • 6
      Kirito  commented on March 12, 2017, 9:22 p.m.

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