Editorial for Yet Another Contest 4 P5 - Signpost


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

Subtask 1

Let's consider two signs with positions x and y. The relative order of these signs on the signposts is solely determined by whether K is greater than, less than, or equal to \frac{x+y}{2}. This motivates us to consider the set S containing all values of \frac{x+y}{2} where x and y are the positions of two different signs. Then, it is clear that the only values of K that we need to consider are the elements of set S, since for any other value of K, we could move the signpost to the first element of S which is greater or lower than K without restricting the signposts that we can make.

Consider a fixed value of K. Let a_K be the number of unordered pairs of signs such that the average of their positions is equal to K. Then, the number of signposts that can be made is 2^{a_K}, since each of the pairs can be ordered either way, and the positions of all other signposts on the signpost are fixed.

At first glance, the answer to the problem appears to be \sum_{K \in S} 2^{a_K}. However, it can be seen that for any two adjacent elements of S, there is exactly one sign that can be made at both positions. Hence, the answer is 1 + \sum (2^{a_K}-1).

For ease of implementation, we can work with only integers if we instead define b_x as the number of unordered pairs of signs such that the sum of their positions is equal to x. Then, the answer is 1 + \displaystyle\sum_{x=1}^{10^6} (2^{b_x}-1). For subtask 1, it suffices to calculate b_x naively by looping over all pairs of signs.

Time complexity: \mathcal{O}(N^2)

Subtask 2

Let c_x be 1 if there is a sign at position x, and 0 otherwise. Then, it can be seen that b_x = \left\lfloor \frac 1 2 \displaystyle\sum_{i=0}^x c_i c_{x-i} \right\rfloor. Thus, we can efficiently calculate b_x using FFT.

Time complexity: \mathcal{O}(N + \max(p_i) \log(\max(p_i)))


Comments

There are no comments at the moment.