PROBLEM LINKS:
Author: Dushyant Singh
Tester: Karan Malhotra and Deepansh Parmani
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Find total length covered by all subsets of Power set.
EXPLANATION:
We can generate all subsets using bitmask technique.
[6]
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>.
Complexity : O( n ) since we precomputed all required powers of two.
POSSIBLE ERRORS:
-
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.
-
Intermediate overflow. There were solutions where first answer was calculated then atlast mod was taken. Not in this case, answer can overflow in between.
-
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.