PROBLEM LINK:Author: Trung Nguyen DIFFICULTY:MEDIUM PREREQUISITES:sqrtdecomposition, bit operations PROBLEM:There are $n$ monsters, $i^{th}$ of them initially has $h_i$ health points. You need to process $q$ queries of the kind: given $x,y$, subtract $y$ hp from all monsters which index is submask of $x$, i.e. $k ~\&~x=k $. After each query calculate number of living monsters. QUICK EXPLANATION:Break queries into blocks of $\sqrt q$ queries and after each block calculate total $hp$ loss for each enemy. When some enemy is killed, go through all queries in block to find out which query killed it. EXPLANATION:Let's break queries into $\sqrt q$ blocks. Once you read entire block, recalculate $hp$ of each enemy. You can do it by following function:
This function takes iterators $l$ and $r$ to the begin and the end of subarray (i.e. semiinterval $[l;r)$). After this if $rl$ is the power of two and we consider that subarray is indexed in such way that element under iterator $l$ has index $0$ then after this function works out, it will calculate for each index $i$ sum of elements in array such that $i$ is submask of their indices. Indeed two recursive calls will process it correctly for halves of array. After that $i$ and $i+n$ will correspond to same submask except for largest bit which will be set to $0$ in $i$ and to $1$ in $i+n$ thus $arr_i + arr_{i+n}$ will cover all overmasks of $i$. That is, given overall damage for each mask in query, you will calculate damage to each enemy. Now if some enemy got killed at particular block, you can go through all queries in this block and find particular query at which enemy got killed. That will solve the problem. Overall complexity is $O(q+n \sqrt q)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 15 Jan, 10:05

https://www.codechef.com/viewsolution/17048889 This solution contains the code for 100 marks and is very well written along with comments.. Refer this if u are stuck... Hope this will help. answered 16 Jan, 15:43
1
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 ?
(22 Jan, 19:47)

This can be solved using Parallel binary search and SOS DP too. answered 15 Jan, 22:00
1
can you please explain?
(15 Jan, 23:22)
2
SOS DP please ... I am reading again and again that blog and but not get it
(16 Jan, 01:01)
2
For each monster we can find out the query number at which they get killed using binary search and a DS which supports two types of query 1. add number y to subsets of x , 2. find the value of index x. (DS : https://www.hackerrank.com/contests/countercode/challenges/subset), both of these queries can be handled in (log(n))*sqrt(n).
(16 Jan, 09:43)
2
But if we binary search for each monster then it will be n(qlogq(logn)sqrt(n)). So we can improve this solution by removing simple binary search for each monster and using parallel binary search for all of them at once. Complexity: qlogqlognsqrt(n) .(parallel binary search: http://codeforces.com/blog/entry/45578)
(16 Jan, 09:43)
can you please explain the second part of the hackerrank problem(how to count when the number of set bits is > 8 (i understand the first part of it i.e. all the values with set bits > 8 but for didn't get the idea for < 8. They are saying : "to count the numbers X that doesn't satisify X and S = X we flip the digits of S (change every 0 to 1 and every 1 to 0) (note that S become to have at most 8 1bits) then count the numbers X that have at least one common 1bit with S by inclusion  exclusion principle"
(16 Jan, 23:09)
How you guys think that it will be done using sqrt decomposition? I gave it one day thinking of doing it using BIT. PS: I love BIT
(17 Jan, 10:54)
showing 5 of 6
show all

Can someone please breakdown and explain this to me. I do not understand what the editorialist is saying. Because I'd love to know the solution of this problem as i was stuck on it during the contest. answered 16 Jan, 11:35

An amazing tutorial on Sum Over Subsets DP can be found here. sum_overmasks mentioned in the question is similar to SOS DP with the same complexity $\mathcal{O}(n\log{n})$ answered 19 Jan, 05:16
but what is the use of sos here? after doing sos dp what we r getting ??
(22 Jan, 20:48)
1
The Sumoversubsets operation combines the actions together. After a sumoversubsets, 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 sumoversubsets operation, you would apply each action to each monster individually, in $n \times q$ steps. With the suboversubsets 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 sumoversubsets, plus time to apply to monsters. The result is faster.
(23 Jan, 05:31)
thanks @john_smith_3 for making it clear
(07 Feb, 02:48)

Is anybody able to view the Author's and Tester's solution? answered 15 Jan, 21:12

Can anyone please explain how to solve this problem using SOS DP? Thanks. answered 15 Jan, 22:53

Why the complexity is $O(q+n\sqrt{q})$, complexity of sum_overmasks is $O(n\log n)$ not $O(n)$ as is stated in editorial?? I'm missing something?? answered 18 Jan, 00:14
1
I agree  sum_overmasks is $O(n \log n)$. If block size is set to $\sqrt \frac {q}{\log n}$ then perhaps time can be $O(q + n \sqrt{q \log n})$. There is a question and answer discussing further.
(18 Jan, 02:26)
@john_smith_3 I believe you meant "If number of blocks is set to$\sqrt \frac {q}{\log n}$ then ..."
(21 Jan, 08:33)
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)..
(21 Jan, 13:14)
@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 ) )$.
(23 Jan, 05:09)

can anyone explain me why we are doing answered 19 Jan, 21:04
1
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..
(21 Jan, 13:24)
