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.
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:
For each block we iterate over each query in the block. Total time O(q)
We have to do b Sum-over-subset operations, each takes time O(n \log n)
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.
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
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?
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.
@john_smith_3
"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?