Editorial for Wesley's Anger Contest 6 Problem 8 - Crystal Disco


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: wleung_bvg

Subtask 1

For the first subtask, for each operation, we can iterate through each pair of small turntables and determine if a lamp is on the line segment between them. We can compute the angle of the line segment based on the isosceles triangle formed between the two small turntables and the large turntable. There is a lamp on the line segment if and only if the angle is a multiple of \frac{360}{N} degrees. We can then print the sum of the polish values of each of these lamps.

Time Complexity: \mathcal{O}(Q \cdot N^2)

Subtask 2

One helpful observation is that when N is odd, the answer is always 0. When N is even, it is the case that the closest \frac{N}{2} - 2 lamps to the centre contribute to the required sum if N is a multiple of 4 or \frac{N}{2} if it is not. We can precompute the sum for each of the N possible rotations of each small turntable. We can also see that rotating the large turntable clockwise is equivalent to rotating each of the smaller turntables counterclockwise. For each operation, we can print the sum of the precomputed sums for each of the smaller turntables' current rotation.

Time Complexity: \mathcal{O}(Q \cdot N)

Subtask 3

For the third subtask, we can split the operations into blocks. Given an initial rotation of each of the smaller turntables, if we can quickly compute the answer for all possible rotations of the large turntable, we can then keep a buffer of all operations on the small turntables and apply the smaller operations one by one after looking up the answer for the current rotation of the large turntable. To compute the answer for all possible rotations of the large turntable, we can observe that there are N possible rotations of the smaller turntables, with each sum of the polish values of the closest lamps to the centre contributing some number of times (between 0 and N) to the answer for each rotation of the large turntable. In fact, if we consider the frequencies of each of the rotations of the smaller turntables, we can treat this as a polynomial of degree N - 1. We can also treat the sum of the polish values of the closest lamps to the centre for each of the smaller rotations as another polynomial of degree N - 1. If we multiply these polynomials together, we can see that it will result in a polynomial of degree 2 \cdot N - 2 with the answer for each rotation i of the large turntable being the sum of all coefficients c_j where j \equiv i \bmod N. We can multiply these polynomials quickly in \mathcal{O}(N \log N) time, which means that the optimal size of the blocks of operations is approximately \sqrt{Q \log N}.

Time Complexity: \mathcal{O}((N + Q) \cdot \sqrt{Q \log N})


Comments

There are no comments at the moment.