codeforces-scrape

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

2033E.md (2024B)


      1 Source: https://codeforces.com/problemset/problem/2033/E
      2 
      3 E. Sakurako, Kosuke, and the Permutation
      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 Sakurako's exams are over, and she did excellently. As a reward, she received a permutation $p$. Kosuke was not entirely satisfied because he failed one exam and did not receive a gift. He decided to sneak into her room (thanks to the code for her lock) and spoil the permutation so that it becomes simple.
     22 
     23 A permutation $p$ is considered simple if for every $i$ $(1\le i \le n)$ one of the following conditions holds:
     24 
     25 * $p_i=i$
     26 * $p_{p_i}=i$
     27 
     28 For example, the permutations $[1, 2, 3, 4]$, $[5, 2, 4, 3, 1]$, and $[2, 1]$ are simple, while $[2, 3, 1]$ and $[5, 2, 1, 4, 3]$ are not.
     29 
     30 In one operation, Kosuke can choose indices $i,j$ $(1\le i,j\le n)$ and swap the elements $p_i$ and $p_j$.
     31 
     32 Sakurako is about to return home. Your task is to calculate the minimum number of operations that Kosuke needs to perform to make the permutation simple.
     33 
     34 Input
     35 
     36 The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases.
     37 
     38 Each test case is described by two lines.
     39 
     40 * The first line contains one integer $n$ ($1\le n \le 10^6$) — the length of the permutation $p$.
     41 * The second line contains $n$ integers $p_i$ ($1\le p_i\le n$) — the elements of the permutation $p$.
     42 
     43 It is guaranteed that the sum of $n$ across all test cases does not exceed $10^6$.
     44 
     45 It is guaranteed that $p$ is a permutation.
     46 
     47 Output
     48 
     49 For each test case, output the minimum number of operations that Kosuke needs to perform to make the permutation simple.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 6
     57 
     58 5
     59 
     60 1 2 3 4 5
     61 
     62 5
     63 
     64 5 4 3 2 1
     65 
     66 5
     67 
     68 2 3 4 5 1
     69 
     70 4
     71 
     72 2 3 4 1
     73 
     74 3
     75 
     76 1 3 2
     77 
     78 7
     79 
     80 2 3 1 5 6 7 4
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 0
     87 0
     88 2
     89 1
     90 0
     91 2
     92 ```
     93 
     94 Note
     95 
     96 In the first and second examples, the permutations are already simple.
     97 
     98 In the fourth example, it is sufficient to swap $p_2$ and $p_4$. Thus, the permutation will become $[2, 1, 4, 3]$ in $1$ operation.