 # CPH003D - Editorial

## PROBLEM LINKS:

Contest

Author: Dushyant Singh

Tester: Karan Malhotra and Deepansh Parmani

Simple

None

## PROBLEM:

Find total length covered by all subsets of Power set.

## EXPLANATION:

We can generate all subsets using bitmask technique.

``````


However, the program written by the above logic will get TLE. The reason being, n can be as large as 10<sup>5</sup>.

We can use one observation. Every fountain will occur 2<sup>n-1</sup> times in the superset. So, contribution of each fountain in answer will be ( r[i] - l[i] + 1 ) * 2<sup>n-1</sup>.

``````

7

Complexity : O( n ) since we precomputed all required powers of two.

## POSSIBLE ERRORS:

1. There were solutions in C++ using inbuilt pow function. Note that this functions returns a double value and always gives round off answer. You can read about it here.

2. Intermediate overflow. There were solutions where first answer was calculated then atlast mod was taken. Not in this case, answer can overflow in between.

3. Multiplication overflow. Suppose we have two variables a and b which are integers and a variable ‘ans’ which is long long. Then is ans += a * b ; correct? No! Because a*b will still be of integer type, we need to convert it to long long either by typecasting or multiplying it with long long constant i.e. ans += 1LL * a * b ; is correct.