Introduction

I recently came across a problem in Codechef Jan 2018 long contest that I couldn’t solve due to the knowledge gap. I found a post in Codeforces that thoroughly explained it. I’m writing this blog to testify my understanding of the concept as well provide some more insights into the problems that will be solved by knowing SOS.

SOS aka Sum Over Subsets

Consider the following problem, given a fixed array A of 2^N integers calculate \(\forall x, F(x) = \sum_{ \substack{ i \epsilon S } }a_{i}, x \& i = i, i.e i \subset x.\) The brute force approach is by iterating \(\forall x \epsilon 2^N\) and then count for i < x, where x & i = i holds true. The problem can be solved using dynamic programming if we can find a inductive step for counting the occurrences. It turns out that such recurrences state exists. Consider F(X, i) that denotes count of numbers of bit length <= i, where X & i == i. So, the recurrences equation of \(F(X, i) = F(X, i-1)\), when the ith bit of X is 0 and \(F(X, i) = F(X, i-1) + F(X \oplus 2^{i}, i-1)\), when the ith bit is set 1. The latter part of the post will discuss the problems that can be solved using the above concept.

Problem - SPECIAL PAIRS

You have been given an integer array A on size N. You must report the number of ordered pairs (i,j) such that A[i] & A[j] is zero. Here ‘&’ denotes the BITWISE AND. (i,j) and (j,i) are considered different. link

Explanation

The problem is stating us to find i & j = 0 but we know way to compute i & j = i. Let’s try to reduce to a known problem. For, i & j = 0 we know for sure that when j equal 1’s complement of i the equation holds true. Wait, lets name 1’s complement of i as X, then equation also holds true for subset that \(\epsilon\) to X for which \(k \& X = k\). The previous is known to us and can be solved using SOS DP.

Solution

//
// Created by Nivin Anton Alexis lawrence on 1/16/18.
//
#include <iostream>
using namespace std;
long long int dp[1<<20][21];
int freq[1<<20];
int a[100005];
int main()
{

    int t,n ;
    memset(freq, 0, sizeof(freq));
    cin >> t;
    while(t--)
    {
        cin >> n;

        for(int i = 0 ; i < n ; i ++)
        {
            cin >> a[i];
            freq[a[i]] += 1;
        }
        for(int mask = 0 ; mask < (1 << 20) ; mask ++)
        {
            dp[mask][0] = freq[mask];
            if(mask & 1)
                dp[mask][0] += freq[mask^1];
            for(int p = 1; p <= 20; p++)
            {
                dp[mask][p] = dp[mask][p-1];
                if(mask & (1 << p))
                    dp[mask][p] += dp[mask ^ (1 << p)][p-1];
            }
        }

        long long ans = 0;
        for(int i = 0; i < n; i++)
        {
            ans += dp[(1<<20) - (a[i] + 1) ][20]; /* basically 1's complement */ 
            freq[a[i]] = 0;
        }
        cout << ans << endl;

    }


}

Problem - Compatible Numbers

Two integers x and y are compatible, if the result of their bitwise “AND” equals zero, that is, a & b = 0. For example, numbers 90 (10110102) and 36 (1001002) are compatible, as 10110102 & 1001002 = 02, and numbers 3 (112) and 6 (1102) are not compatible, as 112 & 1102 = 102. You are given an array of integers a1, a2, …, an. Your task is to find the following for each array element: is this element compatible with some other element from the given array? If the answer to this question is positive, then you also should find any suitable element.

Explanation

Same as above one.

Code

//
// Created by Nivin Anton Alexis lawrence on 1/17/18.
//
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int dp[1<<22];
int a[1000005];


int main()
{
    memset(dp, -1, sizeof(dp));
    int n, aux;
    cin >> n;
    for(int i = 0; i < n ;i ++)
    {
        cin >> a[i];
        dp[a[i]] = a[i];
    }
    for(int p = 0; p <= 21; p++)
    for(int mask =  (1<<22) - 1; mask >= 0  ; mask --)
    {
            if((mask & (1<<p)) && dp[mask^(1<< p)] > 0 )
                dp[mask] = dp[mask ^ (1 << p)];
    }
    for(int i = 0 ; i < n ; i ++)
        cout <<  dp[(1<<22) - (a[i] + 1)] << " ";

}

• ← Previous Post
• Next Post →