MONSTER - Editorial

editorial
, , , ,
3

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

6 Likes
4

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

1 Like
5

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
6

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
7

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
8

Can we solve using tries?

9

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
10

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

11

No not able to view the solutions

12

can you please explain?

1 Like
13

What is SOS DP?

14

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

2 Likes
15

Sum Over Subsets - Dynamic Programming

1 Like
16

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 : Programming Problems and Competitions :: HackerRank), both of these queries can be handled in (log(n))*sqrt(n).

2 Likes
17

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: Parallel Binary Search [tutorial] - Codeforces)

2 Likes
18

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”

19

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

20

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
21

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

22

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