codeforces-scrape

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

2268B.md (3658B)


      1 Source: https://codeforces.com/problemset/problem/2268/B
      2 
      3 B. What a SauSaGe! It's All Meat
      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 In SauSaGe City, there are $n$ different flavors of sausages. Reyhaneh, the Queen of SauSaGe City, keeps $a_i$ ($a_i \lt 16$) sausages of flavor $i$ in the royal warehouse.
     22 
     23 Over time, the royal inventory undergoes $q$ updates. Each update is given in the form $(p, x)$, which means the number of sausages of flavor $p$ in the warehouse is changed to $x$ (i.e., $a_p := x$).
     24 
     25 Reyhaneh can perform the following operation on the sausages any number of times (possibly zero):
     26 
     27 * Choose an index $1 \leq i \lt n$ and an integer $1 \leq k \leq 5$, then replace $a_i$ and $a_{i+1}$ with $a_i \oplus (3 \cdot k)$ and $a_{i+1} \oplus (3 \cdot k)$, respectively, where $\oplus$ denotes the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
     28 
     29 In SauSaGe City, a sausage flavor is called All-Meat if its quantity is divisible by $3$. Three famous sausage critics — Shafi, Shafaghi, and Ghaffari — only like flavors that are All-Meat.
     30 
     31 Before processing any updates, and after each of the $q$ updates, you need to answer the following question: If Reyhaneh performs an arbitrary number of operations optimally, what is the maximum possible number of sausage flavors that the three critics would like?
     32 
     33 Note: The operations you perform to find the answer for each state are hypothetical and do not affect the array for subsequent queries. However, the $q$ inventory updates ($a_p := x$) are permanent.
     34 
     35 Input
     36 
     37 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.
     38 
     39 The first line of each test case contains two integers $n$ and $q$ ($2 \leq n \leq 2 \cdot 10^5$, $0 \leq q \leq 2 \cdot 10^5$) — the number of sausage flavors and the number of updates, respectively.
     40 
     41 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt 16$) — the initial numbers of sausages of each flavor.
     42 
     43 Then $q$ lines follow, each containing two integers $p$ and $x$ ($1 \leq p \leq n$, $0 \leq x \lt 16$), meaning that $a_p$ is replaced with $x$.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     46 
     47 It is guaranteed that the sum of $q$ over all test cases does not exceed $2\cdot 10^5$.
     48 
     49 Output
     50 
     51 For each test case, output $q + 1$ integers. The first integer denotes the answer for the initial array. The next $q$ integers denote the answer for each update.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 3
     59 
     60 2 1
     61 
     62 10 3
     63 
     64 1 0
     65 
     66 3 3
     67 
     68 15 1 5
     69 
     70 3 0
     71 
     72 1 10
     73 
     74 2 0
     75 
     76 4 0
     77 
     78 1 2 3 4
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 2 2
     85 
     86 2 2 2 3
     87 
     88 1
     89 ```
     90 
     91 Note
     92 
     93 In the first test case, the initial array is $[10, 3]$. By choosing $i = 1$ and $k = 1$ (so we apply XOR with $3$), we obtain $[10 \oplus 3, 3 \oplus 3] = [9, 0]$, and both $9$ and $0$ are divisible by $3$. After the update, the array becomes $[0, 3]$, where both elements are already divisible by $3$, so the answer is $2$ in both states.
     94 
     95 In the second test case, the initial array is $[15, 1, 5]$. By choosing $i = 2$ and $k = 3$ (XOR with $9$), we get $[15, 1 \oplus 9, 5 \oplus 9] = [15, 8, 12]$, and $15$ and $12$ are divisible by $3$, so the answer is $2$.
     96 
     97 After the first update, the array is $[15, 1, 0]$. Again, two elements ($15$ and $0$) are divisible by $3$, so the answer is $2$.
     98 
     99 After the second update, the array is $[10, 1, 0]$. Choosing $i = 1$ and $k = 3$ (XOR with $9$) gives $[10 \oplus 9, 1 \oplus 9, 0] = [3, 8, 0]$, where $3$ and $0$ are divisible by $3$, so the answer remains $2$.