codeforces-scrape

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

2033C.md (2421B)


      1 Source: https://codeforces.com/problemset/problem/2033/C
      2 
      3 C. Sakurako's Field Trip
      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 Even in university, students need to relax. That is why Sakurakos teacher decided to go on a field trip. It is known that all of the students will be walking in one line. The student with index $i$ has some topic of interest which is described as $a_i$. As a teacher, you want to minimise the disturbance of the line of students.
     22 
     23 The disturbance of the line is defined as the number of neighbouring people with the same topic of interest. In other words, disturbance is the number of indices $j$ ($1 \le j \lt n$) such that $a_j = a_{j + 1}$.
     24 
     25 In order to do this, you can choose index $i$ ($1\le i\le n$) and swap students at positions $i$ and $n-i+1$. You can perform any number of swaps.
     26 
     27 Your task is to determine the minimal amount of disturbance that you can achieve by doing the operation described above any number of times.
     28 
     29 Input
     30 
     31 The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases.
     32 
     33 Each test case is described by two lines.
     34 
     35 * The first line contains one integer $n$ ($2 \le n \le 10^5$) — the length of the line of students.
     36 * The second line contains $n$ integers $a_i$ ($1\le a_i\le n$) — the topics of interest of students in line.
     37 
     38 It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, output the minimal possible disturbance of the line that you can achieve.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 9
     50 
     51 5
     52 
     53 1 1 1 2 3
     54 
     55 6
     56 
     57 2 1 2 2 1 1
     58 
     59 4
     60 
     61 1 2 1 1
     62 
     63 6
     64 
     65 2 1 1 2 2 4
     66 
     67 4
     68 
     69 2 1 2 3
     70 
     71 6
     72 
     73 1 2 2 1 2 1
     74 
     75 5
     76 
     77 4 5 5 1 5
     78 
     79 7
     80 
     81 1 4 3 5 1 1 3
     82 
     83 7
     84 
     85 3 1 3 2 2 3 3
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 1
     92 2
     93 1
     94 0
     95 0
     96 1
     97 1
     98 0
     99 2
    100 ```
    101 
    102 Note
    103 
    104 In the first example, it is necessary to apply the operation to $i=2$, thus the array will become $[1, \textbf{2}, 1, \textbf{1}, 3]$, with the bold elements indicating those that have swapped places. The disturbance of this array is equal to $1$.
    105 
    106 In the fourth example, it is sufficient to apply the operation to $i=3$, thus the array will become $[2, 1, \textbf{2}, \textbf{1}, 2, 4]$. The disturbance of this array is equal to $0$.
    107 
    108 In the eighth example, it is sufficient to apply the operation to $i=3$, thus the array will become $[1, 4, \textbf{1}, 5, \textbf{3}, 1, 3]$. The disturbance of this array is equal to $0$.