You are not logged in. Please login at www.codechef.com to post your questions!

×

MONSTER - Editorial

3
5

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:

This question is marked "community wiki".

asked 15 Jan, 10:05

melfice's gravatar image

4★melfice
811737
accept rate: 0%

edited 15 Jan, 21:26

admin's gravatar image

0★admin ♦♦
19.6k349497539


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.

link

answered 16 Jan, 15:43

namitp's gravatar image

3★namitp
952
accept rate: 0%

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) worldunique3★

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

link

answered 15 Jan, 22:00

arunnsit's gravatar image

6★arunnsit
1.0k1511
accept rate: 27%

1

can you please explain?

(15 Jan, 23:22) pk3013★
2

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

(16 Jan, 01:01) sonu_6284★
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) arunnsit6★
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) arunnsit6★

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"

(16 Jan, 23:09) pk3013★

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

link

answered 16 Jan, 11:35

imortalks's gravatar image

4★imortalks
312
accept rate: 0%

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.

link

answered 19 Jan, 05:16

suicune's gravatar image

5★suicune
211
accept rate: 0%

but what is the use of sos here? after doing sos dp what we r getting ??

(22 Jan, 20:48) worldunique3★
1

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.

(23 Jan, 05:31) john_smith_36★

thanks @john_smith_3 for making it clear

(07 Feb, 02:48) worldunique3★

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

link

answered 15 Jan, 21:12

sid_somani's gravatar image

4★sid_somani
536
accept rate: 0%

No not able to view the solutions

(15 Jan, 21:18) ac094★

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

link

answered 15 Jan, 22:53

i_luv_sumit001's gravatar image

4★i_luv_sumit001
04
accept rate: 0%

What is SOS DP?

(16 Jan, 01:00) melfice4★
1

Sum Over Subsets - Dynamic Programming

(16 Jan, 01:04) john_smith_36★

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

link

answered 18 Jan, 00:14

jcg9129's gravatar image

3★jcg9129
111
accept rate: 0%

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_36★

@john_smith_3 I believe you meant "If number of blocks is set to$\sqrt \frac {q}{\log n}$ then ..."

(21 Jan, 08:33) meooow ♦6★

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) namanjain0074★

@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) john_smith_36★

Can we solve using tries?

link

answered 19 Jan, 00:33

skpro19's gravatar image

3★skpro19
0
accept rate: 0%

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

link

answered 19 Jan, 21:04

kjs1124's gravatar image

1★kjs1124
463
accept rate: 12%

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) namanjain0074★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,198
×2,536
×189
×72
×4

question asked: 15 Jan, 10:05

question was seen: 6,676 times

last updated: 07 Feb, 12:41