usaxena95's blog

By usaxena95, 9 years ago, In English

Introduction

In this post, I am going to share my little knowledge on how to solve some problems involving calculation of Sum over Subsets(SOS) using dynamic programming. Thus the name SOS DP. I have chosen this topic because it appears frequently in contests as mediu2m-hard and above problems but has very few blogs/editorials explaining the interesting DP behind it. I also have a predilection for this since I came across it for the first time in ICPC Amritapuri Regionals 2014. Since then I have created many questions based on this concept on various platforms but the number of accepted solutions always seems to be disproportionate to the lucidity of the concept. Following is a small attempt to bridge this gap 😉

Problem

I will be addressing the following problem: Given a fixed array A of 2N integers, we need to calculate ∀ x function F(x) = Sum of all A[i] such that x&i = i, i.e., i is a subset of x.

Prerequisite

  • Basic Dynamic Programming
  • Bitmasks

In no way this should be considered an introduction to the above topics.

Solutions

Bruteforce

for(int mask = 0;mask < (1<<N); ++mask){
	for(int i = 0;i < (1<<N); ++i){
		if((mask&i) == i){
			F[mask] += A[i];
		}
	}
}

This solution is quite straightforward and inefficient with time complexity of O(4N)

Suboptimal Solution

// iterate over all the masks
for (int mask = 0; mask < (1<<n); mask++){
	F[mask] = A[0];
    // iterate over all the subsets of the mask
    for(int i = mask; i > 0; i = (i-1) & mask){
    	F[mask] += A[i];
    }
}

Not as trivial, this solution is more efficient with time complexity of O(3N). To calculate the time complexity of this algorithm, notice that for each mask we iterate only over its subsets. Therefore if a mask has K on bits, we do 2K iterations. Also total number of masks with K on bits is . Therefore total iterations =

SoS Dynamic Programming solution

In this approach we will try to iterate over all subsets of mask in a smarter way. A noticeable flaw in our previous approach is that an index A[x] with x having K off bits is visited by 2K masks. Thus there is repeated recalculation.
A reason for this overhead is that we are not establishing any relation between the A[x]'s that are being used by different F[mask]'s. We must somehow add another state to these masks and make semantic groups to avoid recalculation of the group.

Denote . Now we will partition this set into non intersecting groups. , that is set of only those subsets of mask which differ from mask only in the first i bits (zero based).
For example . Using this we can denote any set as a union of some non intersecting sets.

Lets try to relate these sets of numbers. S(mask, i) contains all subsets of mask which differ from it only in the first i bits.
Consider that ith bit of mask is 0. In this case no subset can differ from mask in the ith bit as it would mean that the numbers will have a 1 at ith bit where mask has a 0 which would mean that it is not a subset of mask. Thus the numbers in this set can now only differ in the first i-1 bits. S(mask,i) = S(mask, i-1).
Consider that ith bit of mask is 1. Now the numbers belonging to S(mask, i) can be divided into two non intersecting sets. One containing numbers with ith bit as 1 and differing from mask in the next i-1 bits. Second containing numbers with ith bit as 0 and differing from mask⊕2i in next i-1 bits. S(mask, i) = S(mask, i-1) ∪ S(mask⊕2i, i-1).


The following diagram depicts how we can relate the S(mask,i) sets on each other. Elements of any set S(mask,i) are the leaves in its subtree. The red prefixes depicts that this part of mask will be common to all its members/children while the black part of mask is allowed to differ.


Kindly note that these relations form a directed acyclic graph and not necessarily a rooted tree (think about different values of mask and same value of i)
After realization of these relations we can easily come up with the corresponding dynamic programming.

//iterative version
for(int mask = 0; mask < (1<<N); ++mask){
	dp[mask][-1] = A[mask];	//handle base case separately (leaf states)
	for(int i = 0;i < N; ++i){
		if(mask & (1<<i))
			dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
		else
			dp[mask][i] = dp[mask][i-1];
	}
	F[mask] = dp[mask][N-1];
}
//memory optimized, super easy to code.
for(int i = 0; i<(1<<N); ++i)
	F[i] = A[i];
for(int i = 0;i < N; ++i) for(int mask = 0; mask < (1<<N); ++mask){
	if(mask & (1<<i))
		F[mask] += F[mask^(1<<i)];
}

The above algorithm runs in O(N 2N) time.

Discussion Problem

Now you know how to calculate Sum over Subsets for a fixed array A. What would happen if A and F are SOS functions of each other 😉 . Consider following modification to the problem. Assume H1, H2 to be 32 bit integer valued hash functions (just to avoid any combinatoric approach to circumvent this problem) and can be evaluated at any point in constant time.:


I enjoyed solving this with harshil. Lets discuss the approaches in comments :)

Practice Problems

I hope you enjoyed it. Following are some problems built on SOS.

EDIT: Practice problems are now arranged in almost increasing order of difficulty.

  • Vote: I like it
  • +64
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Great tutorial! If only I knew about this before today's contest :P

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Thankyou. Did a similar problem appear in yesterday's contest ?

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      363 Div 1 C. You can add it to the list.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Well I don't think this technique is required to solve this problem. The dp recurrence does not demand any summation over subsets.DP for solving this problem would be

        where

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Good job!

You can also add this problem to the list: http://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf (problem KOSARE).

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Very well written blog.

P.S:The spelling of prerequisites is wrong

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In suboptimal solution: What is mask initialized to ? It is this line F[mask] = A[0]

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in suboptimal solution -> first for : 'i' should be 'mask'! :)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    and what's value of 'i' in this line ?! dp[mask][-1] = A[i]; //handle base case separately (leaf states)

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Great tutorial. I find bitmask concepts hard to undestand. But got a clear understanding with this one. Kudos to the author. :)

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think value of 'i' in 2nd last row of diagram should be zero in all case.

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

thanks great.

sorry, how we can prove that for(int i = mask; i > 0; i = (i-1) & mask) will pass over all subsets ?

  • »
    »
    8 years ago, # ^ |
    Rev. 6   Vote: I like it +19 Vote: I do not like it

    I will give it a try. As of now I am not able to think about an easier proof. I will try to prove it by mathematical induction.
    Note: Operation M-1 switches OFF the first ON bit and switches ON the remaining prefix. Eg 101100002 - 1 = 101011112

    Statement P(n) = Given an integer M, this algorithm will iterate over all subsets s.t. x differs from M only in the first n bits in strictly decreasing order. algorithm successfully iterates over all elements in S(M, n) in strictly decreasing order.

    Base Case P(0):

    • Case 1: if M is even The first iteration i = M successfully visits S(M,0) = {M}

    • Case 2: if M is odd First iteration i = M, second iteration i = (i-1)&M switches off the 0th bit thus visits . Algo visits in decreasing order

    Hence P(0) is true.

    Assumption: Assume P(n) to be true. Algo visits S(M, n) in descending order.

    Inductive step: To prove P(n+1) is true. Since P(n) is true, algo visits all S(M, n) in descending order.
    P(n+1) is trivially true if n + 1th bit of M is OFF since S(M,n+1) = S(M,n).

    Lets focus on case when n + 1th bit of M is ON. Since the visits of S(M,n) as assumed by P(n) are in descending order, the last integer visited by this algo would be M with first n bits OFF. For example, if M = , n = 4 the last value of i would be .

    After reaching this integer, we do i = (i-1)&M. The i-1 operation turns OFF the n + 1th bit and turns ON first n bits. Taking bitwise AND with original M copies the first n bits of M into it.

    Taking the example above, we have following transitions -> -> ->.
    Thus what we final get is .

    Since P(n) is true, we can now iterate over S(, n). But . Therefore we iterate over all elements of S(M,n+1).

    Hence P(n+1) is true.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The example in 2nd last line of the 2nd paragraph under heading "SoS Dynamic Programming solution" doesn't makes sense to me.
      This guy 101 0000 (last element in the set) when XORed with 101 1010 will produce 1010 which is no way <= (1<<3).
      Also the statement that "set of only those subsets of mask which differ from mask only in the first i bits (zero based)" conflicts with x XOR mask being <= (1<<i). It should have been x XOR mask < (1<<i). I am assuming the numbering of positions from Right to Left.
      UPD : I Figured the word it all starts from 0 out !!

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        I have the same doubt! Is it a typo or am I missing something?

        UPD: I think it should be 2^(i+1)-1.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can we just say the following invariant:

      let say j is the jth iteration then i is the jth largest value which is subset of mask

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

That is a great post! It really helped, thank you !!! I tryied the first problem (Special Pairs) source: http://pastebin.com/UXDiad27 But I get WA. My logic is the following: If we find 1 then because we need final result to be zero and we use AND bitwise, then we need to compare it with a number that has 0 at that position. So we go to dp[mask^(1<<i)][i-1] If we find 0 then we can have at that position 0 and 1 as well. So we are seeking in dp[mask][i-1] + dp[mask^(1<<i)][i-1]

Is the logic wrong, or just my source code ? Thanks in advance !

  • »
    »
    8 years ago, # ^ |
    Rev. 5   Vote: I like it +9 Vote: I do not like it

    Got the bug.

    if(exist[0])
        --answer;
    

    Why man why yy yy ? And I was examining your recurrence all this time :P .It is nowhere written i!=j.
    You can have a look at the diff. The correct answer was always just one less than the correct answer :P

    Anyways have fun now :)

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes! Removing that code gives AC! I thought i != j. I am sorry for your suffering checking my recurrence ! Thank you !

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    An easier way to solve this problem: for any A[i], to find how many numbers are there which has bitwise AND zero with A[i] -> it would just be a subset of one's complement of A[i]. So the answer is

    Anyways your modified recurrence shows your proper understanding of the concept :)

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Nice way! Also even if I am not so strong in bitmask I managed to think a modification because your tutorial is so clear and good that made things easier ! Thanks again !

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Given a fixed array A of 2^N integers

I'm unable to understand why 2^N integers must be there in A. Is this a typo?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually the technique was designed for 2N integers. But you can always make an arbitrary length of array to a 2N sized array by adding extra elements with value "0".

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Shouldn't it be that the number of bitmasks=2^SIZE for any integer SIZE. If SIZE itself is 2^N, then overall complexity will be SIZE*2^SIZE = 2^N * 2^( 2^N ).

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

great tutorial

»
8 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

In your memory optimized code shouldn't it be

for(int i = 0; i<(1<<N); ++i)
	F[i] = A[i];
for(int i = 0;i < N; ++i) for(int mask = (1<<N)-1; mask >= 0; --mask){
	if(mask & (1<<i))
		F[mask] += F[mask^(1<<i)];
}

mask is always greater than mask^(1<<i) if i'th bit is set. To calculate for i'th bit we need the value for (i-1)'th bit. In your code F[mask^(1<<i)] actually has the value for i'th bit because it was calculated for i'th bit before mask. If we start from (1<<N)-1 this won't be a problem because F[(mask^(1<<i))] will be calculated for i'th bit after the calculation of F[mask]. Please correct me if I'm wrong. Thanks :)

UPD: I just realized that for F[mask^(1<<i)] actually the calculated value for i'th bit and (i-1)'th bit is same because i'th bit is not set. So your code is correct. Sorry for ignoring it.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for informing was stuck on that !

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your comment inspired me!
    if the $$$i^{th}$$$ bit of mask is $$$1$$$, then the $$$i^{th}$$$ bit of (mask $$$\bigoplus 2^i$$$) will be $$$0$$$, which will not change in this cycle!
    In this case, the F[mask^(1<<i)] will remain unchanged.
    So it doesn't matter which way the mask changes

»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hello ,

Can you explain the formula

used in Vim War.Seems like inclusion exclusion to me but I cannot understand it.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://mirror.codeforces.com/contest/165/problem/E Can someone explain it ? please , can't understand dp-state.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First solve this problem — Special Pairs. Then this problem should be easy.
    However, in my solution dp state was dp[mask] =  a number from the given array such that . So we have base cases , for other masks initialize with 0.
    Now, for each array elements you need to find out another number from the array, such that their AND is 0. Note that the number you need to find will always be a subset of . So you can just print the number stored at . If it is 0 then there is no solution. [ N = minimum number of bits needed to represent all the numbers of the array]

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My idea was almost the same. But it is getting TLE on test 12. Here's the link to my submission http://mirror.codeforces.com/contest/165/submission/29478386

      Can you please check and tell me what's wrong with it?

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        Change cin/cout to scanf/printf! The 12th Case has 1e6 numbers, cin/cout will definitely make it TLE.
        Always use scanf/printf if you have some constrains > 5e5.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Thanks a lot. I never thought that it would make much of a mess..:) I got it accepted after using scanf and printf. Thanks a lot of pointing this out.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Added a nice problem to the set. Varying Kibibits

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

dp[mask][-1] = A[mask]; //handle base case separately (leaf states) .

why it doesn't give array index out of bound exception

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Because this is pseudocode.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Well technically, c++ doesn't check for boundaries so it should work...

    But, you know, unexpected behaviour.

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It's a new problem in town guys. The problem is the editorial is not explained very well ,, i guess you guys should take a look and if anyone understands may be he can shed some light for us newbies.

https://www.hackerrank.com/contests/world-codesprint-11/challenges/best-mask/editorial

It's a recent codesprint problem from hackerrank.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey can anyone explain how to approach question this. it is similar to discuss problem but i am unable to do it? thanks in advance,

»
7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In the question explained. What is the range of x ?? And the size of array is N or 2^N ???

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I can't understand this completely, maybe this is too hard for me.

»
7 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

What does F will contain? Does accumulate of F will give the sum over all subsets?
I want to ask that... What is the meaning of F[mask] in the last implementation?
If I need to find SoS then how should I proceed after calculation of F?

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. Accumulating F won't give you sum over all subsets of the array.
    2. F[mask] is the sum of A[i] such that mask & i == i, that mean the on bits of i is subset of the on bits of mask.
    3. Solve more problems, you'll find out yourself. Most of the times you'll just need to change the base case.
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Absolutely Perfect.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

1)

for(int i = 0;i < N; ++i) 
     for(int mask = 0; mask < (1<<N); ++mask){
	if(mask & (1<<i))
		F[mask] += F[mask^(1<<i)];
}

2)

for(int mask = 0; mask < (1<<N); ++mask)
    for(int i = 0;i < N; ++i){
	if(mask & (1<<i))
		F[mask] += F[mask^(1<<i)];
}

What is difference between above 2 codes? Do both codes give same result?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if(mask & (1<<i))
        dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
    else
        dp[mask][i] = dp[mask][i-1];
    

    is equivalent to first version and not the second version. The ith iteration of 1) has F[mask] = dp[mask][i]. This is not true in 2).

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      So 2nd version will not count some dp states. Right?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It will visit every state but t will calculate it wrong. When you do F[mask] += F[mask^(1<<i)]. In the ith iteration for F[mask] you actually add dp[mask^(1<<i)][N-1] instead of dp[mask^(1<<i)][i-1]. So all values are wrong.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

for ( x = y; x > 0; x = ( y & (x-1) ) )

generates all subsets of bitmask y.

How does this iteration works? Any intuitive explaination?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x starts with the value y, and everytime you subtract 1 from x, the lowest value bit that is set would become unset, and the bits ahead of the lowest set bit (now unset) would become set.

    Eg: x = y = 10100

    x-1 = 10011

    Now when you bitwise AND this with y (which was initially x), you get the common set bits between x and y ( definition of bitwise AND ).

    Eg: x=10011 and y=10100

    x&y = 10000

    Everytime you AND x with y, it is making sure that x is always a subset of y.
    Subtracting x by 1 after every iteration makes sure that you go through all combinations ( 2N ) of the mask y.
    Further proof for the same is given by usaxena95 above.

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it
»
7 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Untitled

I see it is not clear with the example above. S(1011010, 3) contains 1010000.

Let take the XOR operator: 1011010 xor 101000 = 0001010. In decimal representation, this value should be equal to 2^3 + 2^1 > 2^3, contradicting to (1011010 xor 101000)_{10} <= 2^3.

I may misunderstand. Can someone help me explain this gap?

Thanks,

Hanh Tang

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In this approach we will try to iterate over all subsets of mask in a smarter way. A noticeable flaw in our previous approach is that an index A[x] with x having K off bits is visited by 2^K masks. Thus there is repeated recalculation

Can someone explain me this line?

The mask: 4(100) has 2 off-bits, so 2^2=4 masks will visit the mask 4(100). How?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    An index x with k off bits is a subset to 2^k masks (hence it is visited by 2^k masks).

    In your example case 4(100) is visited by 100,101,110,111.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Excellent editorial! Kudos...

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach for discussion problem?

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

recent one DANYANUM

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks for such a nice blog

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

One more problem from a recent contest: Or Plus Max

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

can someone explain what we can't use following for(int mask = 0; mask < (1<<N); ++mask) for(int i = 0;i < N; ++i) { if(mask & (1<<i)) F[mask] += F[mask^(1<<i)]; } how to identify which one to use?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's because of compiler optimizations.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can we say that when ith bit is ON then simply S(mask,i) = 2*S(mask,i-1), Because all the subsets till (i-1)th bit now have 2 choices .Either they can pair up with ith bit as 0 or 1 ??

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the problem Pepsi Cola?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
//iterative version
for(int mask = 0; mask < (1<<N); ++mask){
	dp[mask][-1] = A[mask];	//handle base case separately (leaf states)
	for(int i = 0;i < N; ++i){
		if(mask & (1<<i))
			dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
		else
			dp[mask][i] = dp[mask][i-1];
	}
	F[mask] = dp[mask][N-1];
}

I think the address of dp[0][-1] is undetectable, will it go wrong?

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Great tutorial! Also, isn't the iterative solution akin to finding an N-dimensional prefix sum array with dimensions 2x2...x2? If this is the case, I think it could be possible to extend this idea to "bitmasks" with a different base.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you do the partition, why it is a partition? Mask is in all those sets, right?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Jersey Number is probably a better place to submit. There seems to be some problem with the testcases on ICPC Live Archive (AC on Codechef gets WA there; Noone has solved it).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The suboptimal solution is very clever

»
5 years ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like it

There is another cool way of visualizing/memorizing SOS that I learnt from errichto's video:

How do you transform a 1D array to its prefix sum? You do: a[i] += a[i - 1].
How do you transform a 2D array to its prefix sum? Normally it is done by p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j]. But notice that you can also apply the 1D prefix sum in rows and columns separately:

for i in [1, N]: for j in [1, N]: a[i][j] += a[i][j-1]  
for i in [1, N]: for j in [1, N]: a[i][j] += a[i-1][j]

Now, the sub over submasks problem can be imagined as doing a prefix sum on $$$2\times 2\times\ldots \times2$$$ hypercube! For example, lets say the mask has three bits, and you want sum over submasks for $$$101$$$. That is equivalent to taking the sum from cell $$$(0, 0, 0)$$$ to $$$(1, 0, 1)$$$ on a 3D cube.

So, you can just apply 1D prefix sum on each dimension separately. That is exactly what the final version of the code snippet is doing. It first iterates on the dimension, then does a[..][1][..] += a[..][0][..] for that dimension; in other words, takes prefix sum on that dimension. And after that, the initial array turns into the SOS!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Kindly note that these relations form a directed acyclic graph and not necessarily a rooted tree (think about different values of mask and same value of i)

can someone explain not a rooted tree more

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me out in the question — VIM WAR ? Couldn't understand the summation formula in the editorial. Thankyou.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Did you get it? I am also facing problem understanding it.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we use F[mask] = (1 << (__builtin_popcount(mask) - 1)) * a[badbit] + F[nmask] * 2; to update F[mask] in $$$O(1)$$$ where badbit = 31 - __builtin_clz(mask) and nmask = mask - (1 << badbit) ?

    F[0] = 0;
    for(int mask = 1; mask < (1 << n); mask++){

        int badbit = 32 - 1 - __builtin_clz(mask);
        int nmask = mask - (1 << badbit);
        F[mask] = (1 << (__builtin_popcount(mask) - 1)) * a[badbit] + F[nmask] * 2;

    }
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

for(int i = 0; i<(1<<N); ++i)

F[i] = A[i];

for(int i = 0;i < N; ++i) for(int mask = 0; mask < (1<<N); ++mask){

if(mask & (1<<i))

    F[mask] += F[mask^(1<<i)];

}

let there be two numbers i and j such that i and j bit are set in mask then will f[mask^(1<<j)^(1<<i)] not added twice in f[mask] from above approach

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    wq

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    F[i] = A[i]????? why?, did u check your code with some examples?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      its the memory optimized code in the blog i just copied it here.

      f[i]=a[i] is initialization for all masks beacause every set is subset of itself ofc!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I use FWT to solve this problem with the same complexity? F = FWT_AND(A,B),where B=[1,1,1,1...]

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy ques, just above code: link

soln : link SAME AS ABOVE

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can I get link of the same problem which discussed above Actually I want to check a little different approach

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

issue solved

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem from csacademy uses SOS dp as a subroutine. Maybe checking it out.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

If I need to iterate over the subsets of the mask's complement , How can I apply SoS DP approach? I'm able to apply the 3^N approach easily, However N is upto 20 which would lead to A TLE verdict.


private int dp(int msk) { if (msk == (1 << n) - 1) return 0; if (memo[msk] != -1) return memo[msk]; int max = 0; int avalMsks = msk ^ ((1 << n) - 1); for (int i = avalMsks; i > 0; i = (i - 1) & (avalMsks)) { if (valid[i]) max = Math.max(max, dp(msk | i) + 1); } return memo[msk] = max; }

usaxena95 any thoughts?

here is the problem if anyone is interested :101666G - Going Dutch

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems isomorphic to this problem I ran into a few weeks ago. You'll have to change your DP from "How big is the largest valid partition of (the complement of) this mask?" to "How big is the largest valid partition of any subset of (the complement of) this mask?"

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Edit : I get it now , here is the code in case someone needs it

      private int dp(int msk) {
                  if (msk == (1 << n) - 1)
                      return 1;
                  if (memo[msk] != -1)
                      return memo[msk];
                  int max = 0;
                  for (int i = 0; i < n; i++) {
                      if ((msk & (1 << i)) == 0)
                          max = Math.max(max, dp(msk ^ (1 << i)) + (valid[msk] ? 1 : 0));
                  }
                  return memo[msk] = max;
              }
      
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Very well explained tutorial! it was very helpful. Thank you UwU

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have $$$Q \le 200000$$$ queries and set of $$$N \le 200000$$$ bitmasks. For each bitmask in query I have to calculate number of bitmasks in set that have a bitwise AND equal to $$$0$$$ with bitmask from query. How can I solve it, if bitmasks contains $$$50$$$ bits? I already can solve it for $$$20$$$ bits, but can't figure out sparse solution. I thought about something like:

We can just iterate over all parents in prefix tree from this article for all $$$N$$$ leafs and do hashmap[node]++

but it is directed acyclic graph...

»
4 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Almost same article with lot more explanations — Link

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The article linked has exactly same content. That one is blatantly copied, without even citing this blog as reference.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cant get link for Special Pairs.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's problem from CSES Problemset using this technique: https://cses.fi/problemset/task/1654.

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

A small reminder, we can change if(mask & (1<<i)) to if (!(mask & (1<<i))), then we can calculate the sum of super set (not subset).

The correctness is simple, we can just change the dp formular above a bit.

And it can easily solve problem D in yesterday contest.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you! I finally passed that problem!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    or you can keep the if condition same and do F[mask&(1<<i)] += F[mask]; Just adding supersets to the set instead of adding subsets to the set.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to prove complexity in the suboptimal solution? I haven't got how to come to 3^n through the sum.

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Sorry for necroposting, but is there a way to fix the latex/markup sections? I keep on seeing Unable to parse markup [type=CF_TEX]. usaxena95

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was reading this and started to solve the problems and suddenly whole blog just started showing this. Now I can't see the blog.

Unable to parse markup [type=CF_MARKDOWN]

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I seem to have seen this trick a long time ago, But I forgot it in today's contest ;)

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the approach involved in Covering Sets (problem 4) I get the sos dp part but how are we calculating the total sum for all triplets

»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Great tutorial, without it I would not be able to understand and solve https://mirror.codeforces.com/contest/1903/problem/D2.