DMOPC '14 Contest 8 P6 - Revenge of the Bins

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Tusk has N (2 \leq N \leq 10^5) bins arranged in a line. N is even. The i-th bin has size s_i (1 \leq s_i \leq N). The sizes are distinct, so they form a permutation of the numbers from 1 to N. Tusk wants to take the largest possible prefix of the bins so that he can fit the bins from the second half of the prefix into the first half of the prefix.

Formally, find the maximum x (1 \leq x \leq \dfrac{N}{2}) such that there is a permutation p_1, p_2, ..., p_x of the numbers 1 to x so that for each i from 1 to x, s_i > s_{x+p_i}. If there is no such x, output 0.

For example, if the bins' sizes are 3, 5, 4, 2, 1, 6, then the only valid value of x is 2. x=2 is valid because you can fit bin 3 into bin 2 and bin 4 into bin 1. x=1 is invalid because you can't fit bin 2 into bin 1. x=3 is invalid because bin 6 can't fit into bin 1, 2, or 3.

Input Specification

The first line contains N. The next line contains N integers: the sizes of the bins.

Output Specification

Output a single integer: the maximum value of x.

Scoring

  • Subtask 1 [10 points]: N \leq 10
  • Subtask 2 [10 points]: N \leq 1\,000
  • Subtask 3 [10 points]: N \leq 10\,000
  • Subtask 4 [70 points]: N \leq 100\,000

Sample Input

6
3 5 4 2 1 6

Sample Output

2

Comments


  • 3
    XIAOAGE  commented on Jan. 6, 2016, 3:26 p.m.

    I m not sure but it says:

    Si < Si+x

    but according to sample input 1, i think i should be other way around, Si>Si+x


    • 0
      cheesecake  commented on Jan. 6, 2016, 6:36 p.m.

      Fixed.