Editorial for CCC '21 S5 - Math Homework


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

The only numbers needed are 1 and 2. For every operation with Z_i=2, fill A_{X_i},A_{X_i+1},\dots,A_{Y_i} with 2. After all the operations, check if the GCDs are correct.

Time Complexity: \mathcal{O}(NM)

Subtask 2

Consider a single requirement X_i,Y_i,Z_i, we can reframe this requirement as the following two restrictions:

  1. Every single number from index X_i to Y_i to be divisible to Z_i
  2. The GCD of the subarray A_{X_i},A_{X_i+1},\dots,A_{Y_i} is minimized

For any index i, to make sure it satisfies the first restriction of all requirements that pass over it, it must be some multiple of the LCM of all Z of those requirements. Additionally, as we also want to minimize the GCD of the subarray specified in each requirement (while also satisfying the divisibility restriction), it's always optimal to take the LCM.

Thus, for each value in our final array, we collect all the requirements that pass over it, and just set it to the LCM of the Z values of those requirements. Then, we just check that our answer is valid by making sure the GCD restriction on each requirement is satisfied.

Time Complexity: \mathcal{O}(NM)

Subtask 3

There are many ways to optimize the subtask 2 solution for full points, but this solution will not involve any data structures beyond difference array because throwing segment trees at the problem is boring.

To compute which requirements pass over any given index, notice that 1 \le Z_i \le 16, so we can just use 16 difference arrays to keep track of which requirements pass over any given index.

Checking that the GCD restriction of each requirement is satisfied is a bit more complicated. In this case, we'll treat them as range GCD queries on our final array and we first group the queries by their right endpoint. We then process them offline in increasing order of right endpoint. At each right endpoint from 1, 2, \dots, N, we consider the GCD of all subarrays that end at that endpoint, and observe that as we move from the shortest to longest subarray, the GCD will change at most \log(lcm(1, 2, \dots, 16)) times. Thus, we can just maintain these GCD changes with a vector and answer all queries ending at that right endpoint with binary search.

Time Complexity: \mathcal{O}(N \max(Z_i) + (N+M) \log(\max(A_i)))


Comments

There are no comments at the moment.