codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2222C.md (2380B)


      1 Source: https://codeforces.com/problemset/problem/2222/C
      2 
      3 C. Median Partition
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $a$ with an odd length $n$ consisting of positive integers. You are required to partition the sequence into several subarrays$^{\text{∗}}$ with odd lengths and the same median$^{\text{†}}$. Your task is to find the maximum number of subarrays.
     22 
     23 More formally, you are required to find a strictly-increasing sequence $k$ with a length of $(p+1)$ where $k_1=1$ and $k_{p+1}=n+1$, such that for every $1\le i\le p$, the medians of the sequences $[a_{k_i},a_{k_i+1},\ldots,a_{k_{i+1}-1}]$ are all the same. The parity of $k_i$ and $k_{i+1}$ should be different. Your task is to find the biggest possible value of $p$.
     24 
     25 $^{\text{∗}}$An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
     26 
     27 $^{\text{†}}$The median of an array with an odd length $x$ is the $\lceil\frac{x}{2}\rceil$-th element of the array after it is sorted in non-decreasing order.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($1\le n \lt 5000$, $n$ is odd) — the length of $a$.
     34 
     35 The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$) — the elements of $a$.
     36 
     37 It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5000^2$.
     38 
     39 Output
     40 
     41 For each test case, output a single integer — the maximum number of subarrays.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 10
     49 
     50 5
     51 
     52 3 3 2 4 3
     53 
     54 7
     55 
     56 9 5 7 7 4 7 7
     57 
     58 9
     59 
     60 1 1 1 1 1 1 1 1 1
     61 
     62 1
     63 
     64 5
     65 
     66 3
     67 
     68 1 2 3
     69 
     70 3
     71 
     72 2 2 2
     73 
     74 5
     75 
     76 1 2 3 4 5
     77 
     78 5
     79 
     80 2 1 3 2 2
     81 
     82 7
     83 
     84 2 2 1 2 3 2 2
     85 
     86 9
     87 
     88 2 1 2 3 2 1 2 3 2
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 3
     95 
     96 3
     97 
     98 9
     99 
    100 1
    101 
    102 1
    103 
    104 3
    105 
    106 1
    107 
    108 3
    109 
    110 5
    111 
    112 5
    113 ```
    114 
    115 Note
    116 
    117 In the first test case, it is optimal to partition $a$ into $[\underline 3, \underline 3, \underline{2, 4, 3}]$.
    118 
    119 In the second test case, it is optimal to partition $a$ into $[\underline{9, 5, 7}, \underline 7, \underline{4, 7, 7}]$.
    120 
    121 In the third test case, since all the elements are the same, you can partition each element into a separate subarray.