Editorial for Back To School '18: Function Maximization

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

For the first subtask, the intended solution was brute force.

Time Complexity: \mathcal O(NQ)

For the second subtask, we can precompute f(x) for all x in the range [K, K+5000].

Then, we can create a lazy segment tree of bitsets of size 5001, of which the i^\text{th} bit (0 indexed) of each bitset stores whether an element with value i+K exists in either of its two children (or itself if it is a leaf node). For a query, we can handle it how it would normally be handled, except when joining two bitsets, we bitwise or them together. When performing lazy propagation on a node, we can bitshift the bitset left or right depending on the lazy value (right if the lazy value is less than 0, and left if it is greater than 0).

Time Complexity: \mathcal O(\frac{5000Q\log N}{\text{bitset constant}} + 5000K)

For the third subtask, we can use some mathematical insight. Using Wilson's theorem, the function f(x) reduces to x if x is prime, or -1 otherwise. To precompute f(x), we can use a segmented sieve to generate the primes in the range [K, K+5000]. The rest is the same as subtask 2.

An alternative method of precomputing f(x) is to run the Miller-Rabin primality test for all x in the range [K, K+5000].

Time Complexity: \mathcal O(\frac{5000Q\log N}{\text{bitset constant}} + \sqrt K \log \log \sqrt K) or \mathcal O(\frac{5000Q\log N}{\text{bitset constant}} + 5000 \log^3 K)


  • 1
    thomas_li  commented on March 29, 2024, 8:54 p.m.

    I love bitset