codeforces-scrape

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

1685A.md (2341B)


      1 Source: https://codeforces.com/problemset/problem/1685/A
      2 
      3 A. Circular Local MiniMax
      4 
      5 time limit per test
      6 
      7 1 second
      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 $n$ integers $a_1, a_2, \ldots, a_n$. Is it possible to arrange them on a circle so that each number is strictly greater than both its neighbors or strictly smaller than both its neighbors?
     22 
     23 In other words, check if there exists a rearrangement $b_1, b_2, \ldots, b_n$ of the integers $a_1, a_2, \ldots, a_n$ such that for each $i$ from $1$ to $n$ at least one of the following conditions holds:
     24 
     25 * $b_{i-1} \lt b_i \gt b_{i+1}$
     26 * $b_{i-1} \gt b_i \lt b_{i+1}$
     27 
     28 To make sense of the previous formulas for $i=1$ and $i=n$, one shall define $b_0=b_n$ and $b_{n+1}=b_1$.
     29 
     30 Input
     31 
     32 The first line of the input contains a single integer $t$ ($1 \le t \le 3\cdot 10^4$)  — the number of test cases. The description of the test cases follows.
     33 
     34 The first line of each test case contains a single integer $n$ ($3 \le n \le 10^5$)  — the number of integers.
     35 
     36 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).
     37 
     38 The sum of $n$ over all test cases doesn't exceed $2\cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, if it is not possible to arrange the numbers on the circle satisfying the conditions from the statement, output $\texttt{NO}$. You can output each letter in any case.
     43 
     44 Otherwise, output $\texttt{YES}$. In the second line, output $n$ integers $b_1, b_2, \ldots, b_n$, which are a rearrangement of $a_1, a_2, \ldots, a_n$ and satisfy the conditions from the statement. If there are multiple valid ways to arrange the numbers, you can output any of them.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 4
     52 
     53 3
     54 
     55 1 1 2
     56 
     57 4
     58 
     59 1 9 8 4
     60 
     61 4
     62 
     63 2 0 2 2
     64 
     65 6
     66 
     67 1 1 1 11 111 1111
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 NO
     74 YES
     75 1 8 4 9 
     76 NO
     77 YES
     78 1 11 1 111 1 1111
     79 ```
     80 
     81 Note
     82 
     83 It can be shown that there are no valid arrangements for the first and the third test cases.
     84 
     85 In the second test case, the arrangement $[1, 8, 4, 9]$ works. In this arrangement, $1$ and $4$ are both smaller than their neighbors, and $8, 9$ are larger.
     86 
     87 In the fourth test case, the arrangement $[1, 11, 1, 111, 1, 1111]$ works. In this arrangement, the three elements equal to $1$ are smaller than their neighbors, while all other elements are larger than their neighbors.