usaxena95's blog

By usaxena95, 18 months 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 medium-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 _shil. 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  

»
17 months 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

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

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

    • »
      »
      »
      17 months 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.

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

        Could you expalain how that problem can be solved using the above technique?

      • »
        »
        »
        »
        17 months 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

»
17 months 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).

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

Very well written blog.

P.S:The spelling of prerequisites is wrong

»
17 months 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]

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

    In sub optimal solution I think outer array has mask instead of i i.e.

    // 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];
    }
    }
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. Fixed now.

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

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

  • »
    »
    17 months 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)

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

      Fixed. it should have been A[mask] not A[i].

»
17 months 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. :)

»
17 months 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.

»
17 months 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 ?

  • »
    »
    17 months 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.

    • »
      »
      »
      4 months 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 !!

»
17 months 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 !

  • »
    »
    17 months 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 :)

    • »
      »
      »
      17 months 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 !

  • »
    »
    17 months 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 :)

    • »
      »
      »
      17 months 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 !

»
17 months 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?

  • »
    »
    17 months 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".

    • »
      »
      »
      17 months 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 ).

»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

great tutorial

»
17 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    anyways the loop must start with 1<<i, because inside nothing will be done till ith bit is set.

»
14 months 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.

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

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

  • »
    »
    6 months 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]

    • »
      »
      »
      4 months 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://codeforces.com/contest/165/submission/29478386

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

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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.

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

Added a nice problem to the set. Varying Kibibits

»
7 months 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

»
7 months 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.

»
6 months 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,

»
6 months 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 ???

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

    You can take any size, that does not matter. But array will have only n elements.
    Rest all will be zeros.
    But for the answer container(/array) you are required to have a container(/array) of size 1<<N i.e. 2^N.

»
5 months 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.

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

Icannot understand this line .Please explain with a short example.

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

»
4 months 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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Accumulating F won't give you sum over all subsets, but only F[2N - 1] will. Note that N is not the size of array. If size of the array is n, then N is the minimum numbers of bits to represent n numbers, or just
    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.
»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Absolutely Perfect.

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

    Absolutely Pointless. :)

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 3   Vote: I like it -8 Vote: I do not like it

      Can you help me in solving KOSARE. I understand this article. But it seems that I am not making out the official solution of KOSARE. Here the link to a solution I found online. https://github.com/marioyc/Online-Judge-Solutions/blob/master/COCI/2011-2012/Contest%20%236/KOSARE.cpp

      for(int i = 0,r = 0;i < M;++i,r ^= 1){
              for(int j = (1 << M) - 1;j >= 0;--j){
                  dp[r][j] = dp[r ^ 1][j];
                  if(j >> i & 1) dp[r][j] += dp[r ^ 1][j ^ (1 << i)];
              }
      }
      

      What is the need of this r and r^1. I can't understand this part as well.

         for(int mask = 1;mask < (1 << M);++mask){
              int nb = __builtin_popcount(mask);
              
              if(nb & 1){
                  ans -= mod_pow(2,dp[(M - 1) & 1][mask ^ ((1 << M) - 1)]);
                  if(ans < 0) ans += MOD;
              }else{
                  ans += mod_pow(2,dp[(M - 1) & 1][mask ^ ((1 << M) - 1)]);
                  if(ans >= MOD) ans -= MOD;
              }
          }
      

      Any help would be greatly appreciated. Edit : I solved this. Why so many downvotes? I was only asking a doubt!

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

      Absolutely perfectly pointless

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

Please star my projects and contribute if you are interested. 1. https://github.com/ArmenGabrielyan16/DiceRoller 2. https://github.com/ArmenGabrielyan16/SuperLibrary

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

/* Below code is of O(2^n) complexity uses different disjoint set decomposition: (mask — 1) & mask , mask & (-mask) From BIT we know idx & (-idx) gives you the last set bit mask & (mask — 1) unsets the last set bit of mask*/

F[0] = A[0]; for(int mask = 1;mask < (1 << n);++mask) { F[mask] = F[(mask — 1)&mask] + A[mask&(-mask)]; }