can you explain the complexity of the MONSTER problem from JAN 2018 ?

i have seen the others solution for this problem, But facing difficulty in finding the complexity.
I have seen this thing in others solution that, for every block they are iterating over the indices of the array which contains Health points and for every index of that array they are iterating over the queries of each block.
According to what i have seen i can say that the complexity is BlockSize x NumberOfMonsters x NumberOfQueriesPerBlock.
I know i am missing something.
Please explain it.

Anyone please help

1 Like

I haven’t written an answer like this before - please criticise if it is wrong.

Let’s introduce some notation:

\quad q queries

\quad n monsters

\quad b blocks, each block of size s=q/b queries

There are four major steps in the solution:

  1. For each block we iterate over each query in the block. Total time O(q)
  2. We have to do b Sum-over-subset operations, each takes time O(n \log n)
  3. After each block we update the health points of each monster using a result of the Sum-over-subset operation. The update takes constant time O(1) for each monster.
  4. Each monster dies during some block. To find out precisely when takes time O(s).

Add the above items, and we have total time O(q + b n \log n + b n + n s).

O(bn) is smaller than O(bn \log n), so we can simplify the total time to O(q + b n \log n + n s).

Finally, we can choose to set number of blocks b to \sqrt q. So total time now O(q + \sqrt q n \log n).

Perhaps we could set b to \sqrt{\frac q {\log n}}, which would reduce the total time to O(q + n \sqrt{q \log n}).

Updated to include the initial iteration over each query


Thank you very much,
I understood it. My doubts are cleared now.

In every block, we are iterating over every monster, to check if each of the queries in the current block affects it or not. Where are you including that in your calculations?

Should there be a factor of b * s * n in your code?

what is the benefit of doing sum over subset operation ??
what are we getting from it ?

The sum-over-subsets method is used to avoid the b \times s \times n conclusion.

The queries are combined a block at a time, then processed by the sum-over-subsets algorithm, then applied to the monsters.

So in every block rather than iterating every query against every monster in b \times s \times n steps, we have something like b \times (s + n \log n + n) steps.

(Finally, in the block that a monster dies, we take s steps to determine when the monster dies. A monster only dies once, so this stage takes n \times s steps.


sum over subset dp method helps us in finding the total health to subtract from each monster in n*lg(n) time

1 Like

"Perhaps we could set b to \sqrt{\frac q {\log n}} ". I didn’t get this idea? We can even set the block size to \sqrt{\frac q {n}} and Time complexity reduces to O(q + {\log n} \sqrt{q n}). Am I missing something?

Total time is O(q + b n \log n + n s) and b \times s = q.

If b is large and s is small, then the b n \log n term is largest.

If s is large and b is small, then the n s term is largest.

The best balance has b = \sqrt {\frac q {\log n}} and s = \sqrt { q \log n }.

Got it, is it like finding minima of a function!

1 Like

Thanks @fr4nkesti3n
sos dp was very new so initially not getting about it …

1 Like