MONSTER - Editorial

PROBLEM LINK:

Practice
Contest

Author: Trung Nguyen
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

DIFFICULTY:

MEDIUM

PREREQUISITES:

sqrt-decomposition, 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:

template<typename T>
void sum_overmasks(T l, T r) {
    if(r - l == 1) {
        return;
    }
    T m = l + (r - l) / 2;
    sum_overmasks(l, m);
    sum_overmasks(m, r);
    int n = m - l;
    for(int i = 0; i < n; i++) {
        l[i] += l[i + n];
    }
}

This function takes iterators l and r to the begin and the end of subarray (i.e. semi-interval [l;r)). After this if r-l 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.
Tester’s solution can be found here.

RELATED PROBLEMS:

3 Likes

Is anybody able to view the Author’s and Tester’s solution?

1 Like

No not able to view the solutions

This can be solved using Parallel binary search and SOS DP too.

5 Likes

Can anyone please explain how to solve this problem using SOS DP? Thanks.

1 Like

can you please explain?

1 Like

What is SOS DP?

SOS DP please … I am reading again and again that blog and but not get it

2 Likes

Sum Over Subsets - Dynamic Programming

1 Like

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).

2 Likes

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)

2 Likes

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.

2 Likes

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.

8 Likes

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 1-bits)
then count the numbers X that have at least one common 1-bit with S by inclusion - exclusion principle”

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

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??

1 Like

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.

1 Like

Can we solve using tries?

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})
Doesn’t the complexity mentioned in the editorial miss this term - \mathcal{O}(n\log{n}\sqrt{q}). Or am I missing something? Even by altering the blocks size I couldn’t make sense out of the \mathcal{O}(n\sqrt{q} + q) complexity.

2 Likes

can anyone explain me why we are doing & with input of x