@john_smith_3 I believe you meant “If number of blocks is set to$\sqrt \frac {q}{\log n}$ then …”
time complexity would surely be O(sqrt(q) * (nlog(n) + sqrt(q)) ) if" sos dp " applied… as sqrt(q) for each block and nlogn for sos dp and in case killed , sqrt(q)…
kjs1124,we are doing & with input of x as limit of x is 10^9 and we have index range as 2^17 so ,we need bitmask of x only till the msb of index limit,so we are truncating the extra bits of x …and so that we can store contigous x to perform sos dp…
1 Like
Thanks for the link …
do u know why here we are doing sos dp ??
after doing sos for each block what are we getting ? ?
how final answer can be computed from it ?
1 Like
but what is the use of sos here?
after doing sos dp what we r getting ??
@meooow Yes, I should have said number of blocks. Thanks for correcting me.
The argument is that with \sqrt q blocks of \sqrt q size then the time complexity is O(\sqrt q ( n \log n + \sqrt q ) ). But if the block size can be increased to \sqrt {q \log n}, then time complexity reduces slightly to O(\sqrt q ( n \sqrt { \log n } + \sqrt q ) ).
The Sum-over-subsets operation combines the actions together. After a sum-over-subsets, you have a table indexed by monster number giving the number of health points lost by each monster as a result of all the actions in a block.
Without the sum-over-subsets operation, you would apply each action to each monster individually, in n \times q steps.
With the sub-over-subsets operation, you can gather a block of actions together, and apply the combined result to the monsters. This takes time to gather, plus time to sum-over-subsets, plus time to apply to monsters. The result is faster.
1 Like