J. Alien Abduction Again
Author: Felix Halim
(link to problem J)
This problem was prepared by Felix Halim (author) and Risan (tester). I didn’t interfere with their work on this problem, but from what I see, I think Felix Halim was very strict with this problem. He specifically asked me to put the note “your program must be very-very efficient” in the problem statement. He also didn’t want Risan’s Segment Tree solution to get accepted. Felix’s solution run in ~1.5 seconds while Risan’s run in ~12 seconds, but after a lot of (crazy?) optimization, Risan managed to cut down his running time to ~6 seconds. For this kind problem, even a constat factor in your algorithm plays an important role. You have to understand your algorithm well (not just the Big-Oh). This problem not only tests your problem solving skill, but also your programming skill.
As a side note, Felix managed to convey a “secret” message to someone (special?) in the problem statement, but he said that the message was too secret such that the target didn’t notice that ((:. This message has nothing to do with the problem or the contest at all.
Given up to N functions fp(x) = ax3 + bx2 + cx + d, each with different range [xp1, xp2]. These functions are added incrementally. As the functions get added, there queries asking about the total sum of the values of the functions that intersects with range [x1, x2] at integral values of x.
Approach #1 – Bruteforce
For each query, iterate through all the functions and iterate on the [x1, x2] range. This clearly will get TLE.
Approach #2 – Segment Tree
The first observation is that each power can be computed/maintained separately (i.e, the sum of values for ax3 can be maintained in a separate data structure from bx2). Thus we can have 4 (identical) data structure to maintain the sum. The data structure suitable for this is (Lazy) Segment Tree.
This solution is not supposed to work.
Firstly, it will require more than 64MB memory (will not work for Java solutions, however, for C++ it can still run since there is no memory limit for C++). Secondly, the problem asks for a very-very efficient program :).
Sadly, due to PC2 inability to distinguish runtime of 5 seconds vs 4 seconds, Segment Tree solutions can get accepted if it is implemented efficient enough. That is, we set the time limit to be 4 secs in the PC2, but solutions with 5 seconds runtime were still receiving YES. Well, I was disappointed with PC2 with this glitch, but seeing there was a team from NTU spent 10 attempts to get AC, it’s justified :P.
Approach #3 – Binary Indexed Tree (Fenwick Tree)
A more efficient approach is to use Binary Indexed Tree (BIT) for each power. However, it is not that easy. You must know how to perform range updates using BIT.
Here is a pointer on how to use BIT to do Range Updates (read all the links in the comments too):
To give an example, consider the simplest case where f(x) = d. That is, the values for a, b, and c are zero. In this case, the problem is equal to a very simple BIT range update.
Here is a nice post on how to convert a (Lazy) Segment Tree into two BITs:
We can generalize this for the other powers (a, b, and c) and we will need five BITs. The runtime for this approach is less than 2 seconds and it consumes only ~20MB memory.
This problem also requires the knowledge of mod-inverse. That is, you will need to do division with modulo somewhere in the calculation.