codeforces-scrape

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

2247D1.md (3469B)


      1 Source: https://codeforces.com/problemset/problem/2247/D1
      2 
      3 D1. XOR Sorting (Easy Version)
      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 This is the easy version of the problem. The only difference between the versions is that in this version, $q = 0$.
     22 
     23 Note that zero-based indexing is used in this problem.
     24 
     25 For an array $b$ consisting of $m$ positive integers, define $f(b)$ as follows.
     26 
     27 For a non-negative integer $k$, we say that $b$ can be $k$-sorted if it can be sorted in non-decreasing order by performing the following operation any number of times:
     28 
     29 1. Choose two indices $i$ and $j$ ($0 \le i \lt j \le m - 1$) such that $i \oplus j \le k$$^{\text{∗}}$. Note that the condition applies to the indices $i$ and $j$, not to the elements $b_i$ and $b_j$.
     30 2. Swap the elements $b_i$ and $b_j$.
     31 
     32 The value $f(b)$ is defined as the smallest non-negative integer $k$ such that the array $b$ can be $k$-sorted.
     33 
     34 You are given an array $a$ of length $n$, consisting of positive integers. You will perform $q$ updates on $a$. Each update has the following form:
     35 
     36 * $i \; x$: assign $a_i = x$.
     37 
     38 Note that the updates are persistent. In other words, each update affects all subsequent states of the array.
     39 
     40 For each of the $q + 1$ states of $a$ — the initial state and the state after each of the $q$ updates — find the value of $f(a)$.
     41 
     42 $^{\text{∗}}$$\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)
     43 
     44 Input
     45 
     46 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     47 
     48 The first line of each test case contains two integers $n$ and $q$ ($1 \le n \le 10^6, q = 0$) — the length of the array $a$ and the number of updates.
     49 
     50 The second line of each test case contains $n$ integers $a_0, a_1, \ldots, a_{n - 1}$ ($1 \le a_i \le 10^9$) — the array $a$.
     51 
     52 The $j$-th of the following $q$ lines contains two integers $i_j$ and $x_j$ ($0 \le i_j \lt n$, $1 \le x_j \le 10^9$) — the description of the $j$-th update. This update means that the assignment $a_{i_j} = x_j$ is performed.
     53 
     54 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
     55 
     56 It is guaranteed that the sum of $q$ over all test cases does not exceed $10^6$.
     57 
     58 Output
     59 
     60 For each test case, output $q + 1$ integers — the values of $f(a)$ for the initial state of the array and after each of the $q$ updates, in order.
     61 
     62 Example
     63 
     64 Input
     65 
     66 ```
     67 3
     68 
     69 3 0
     70 
     71 2 3 4
     72 
     73 2 0
     74 
     75 1000000000 999999999
     76 
     77 6 0
     78 
     79 2 5 3 4 1 6
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 0
     86 
     87 1
     88 
     89 4
     90 ```
     91 
     92 Note
     93 
     94 In the first example, the array is $a = [2, 3, 4]$. It is already sorted, so $f(a) = 0$.
     95 
     96 In the second example, the array is $a = [10^9, 10^9 - 1]$. We can swap $a_0$ and $a_1$, transforming $a$ as follows: $[\color{red}{10^9}, \color{red}{10^9 - 1}] \rightarrow [\color{red}{10^9 - 1}, \color{red}{10^9}]$. Therefore, $f(a) = 0 \oplus 1 = 1$.
     97 
     98 In the third example, the array is $a = [2, 5, 3, 4, 1, 6]$. We can perform swaps using the index pairs $(0, 1)$ and $(0, 4)$, transforming $a$ as follows: $[\color{red}{2}, \color{red}{5}, 3, 4, 1, 6] \rightarrow [\color{red}{5}, \color{red}{2}, 3, 4, 1, 6]$, $[\color{red}{5}, 2, 3, 4, \color{red}{1}, 6] \rightarrow [\color{red}{1}, 2, 3, 4, \color{red}{5}, 6]$. It can be shown that no smaller value of $k$ is sufficient, so $f(a) = \max(0 \oplus 1, 0 \oplus 4) = 4$.