Hi Codeforces, I would like to share some thoughts regarding a way of understanding SOS DP (This might already exist). Usually whenever I try to read about blogs on SOS DP, I find it a bit hard to comprehend the idea, why this simple 2 nested for loops works: ↵
↵
~~~~~↵
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)];↵
}↵
} ↵
}↵
~~~~~ ↵
↵
**Lets try to solve a simpler problem:** ↵
↵
Given a mask $M$ $(1 \leq M < 2^{20})$ , generate all its submasks (via recursion) ↵
↵
↵
**Solution:** ↵
↵
- We can iterate on bitwise (say from last bit to first bit) ↵
- if current bit `b` is set, we have 2 cases, either set or unset bit `b` in my submask. ↵
- if current bit `b` is unset, our submask also has this bit `b` as unset. ↵
↵
~~~~~↵
↵
void gen_submask(int b , int curmask, int submask) {↵
if(b < 0) {↵
// basecase↵
cout << submask << endl;↵
return;↵
}↵
if(curmask&(1ll << b)) {↵
gen_submask(b-1 , curmask , submask | (1ll << b)); // set↵
gen_submask(b-1 , curmask , submask); // unset↵
}↵
else {↵
gen_submask(b-1 , curmask , submask); // unset↵
}↵
}↵
↵
gen_submask(19 , mask , 0);↵
~~~~~↵
↵
the above simple recursive function would print all the submasks for a given mask. ↵
↵
**Optimisation 1:** The second and third parameters (current mask , sub mask) can be combined into a single parameter. ↵
Reason: Since we iterate on bitwise from last to first bit, say I am currently on bit `b`, the last bits (LSB .. b+1) of `current mask` is not required for my further computation, since the submask has been generated for those bits. ↵
↵
Say we are at bit `b`, We could maintain (LSB ... b+1) bits for submask and (b .. 0) bits contain information of input mask. By this way, we would always get information of bit which is under process, and also maintain generated submask in same variable. ↵
↵
Visual for better understanding of the optimisation: ↵
↵
<img src="https://pouch.jumpshare.com/preview/fzkz55htha3BfYp0fMCkef2vz74qG_meaaliaRjDNqbT9m6xq4mdHfLHmss8CF7K99TfJUTouVi3LkeS5tmsJAHzdW6jS0Ur0F3R1GI1Wek">↵
↵
**Optimised code:** ↵
↵
~~~~~↵
void gen_submask(int b , int curmask) { // current bit , current mask↵
if(b < 0) {↵
cout << curmask << endl; // basecase↵
return;↵
}↵
↵
if(curmask&(1ll << b)) { // if bit is set, we have 2 cases↵
gen_submask(b-1 , curmask); // set↵
gen_submask(b-1 , curmask ^ (1ll << b)); // unset↵
}↵
else {↵
gen_submask(b-1 , curmask); // unset↵
}↵
}↵
↵
gen_submask(19 , mask);↵
~~~~~ ↵
↵
This code is simpler to understand, and this prints all submasks, for a given input mask, which serves our purpose. ↵
**Just memoize this recursive function, thats it, SOS DP**. ↵
↵
↵
<spoiler summary="Code">↵
```↵
void gen_submask(int b , int curmask) {↵
if(b < 0) {↵
return F[curmask];↵
}↵
↵
if(dp[b][curmask] != -1) return dp[b][curmask];↵
↵
ll ans = 0;↵
if(curmask&(1ll << b)) { ↵
ans += gen_submask(b-1 , curmask);↵
ans += gen_submask(b-1 , curmask ^ (1ll << b));↵
}↵
else {↵
ans += gen_submask(b-1 , curmask);↵
}↵
return dp[b][curmask] = ans;↵
}↵
```↵
</spoiler>↵
↵
↵
↵
**Conclusion:**↵
↵
- Say any problem related to Sum of Subsets, Supersets, (or any variation of it) we could write a simple recursive function to generate all valid masks (as per the problem) and memoize it using DP. ↵
↵
**Examples:** ↵
↵
- F(Mask) = Sum of all Masks, such that (odd bits are subset, even bits are superset) ↵
↵
↵
↵
↵
↵
↵
↵
~~~~~↵
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)];↵
}↵
} ↵
}↵
~~~~~ ↵
↵
**Lets try to solve a simpler problem:** ↵
↵
Given a mask $M$ $(1 \leq M < 2^{20})$ , generate all its submasks (via recursion) ↵
↵
↵
**Solution:** ↵
↵
- We can iterate on bitwise (say from last bit to first bit) ↵
- if current bit `b` is set, we have 2 cases, either set or unset bit `b` in my submask. ↵
- if current bit `b` is unset, our submask also has this bit `b` as unset. ↵
↵
~~~~~↵
↵
void gen_submask(int b , int curmask, int submask) {↵
if(b < 0) {↵
// basecase↵
cout << submask << endl;↵
return;↵
}↵
if(curmask&(1ll << b)) {↵
gen_submask(b-1 , curmask , submask | (1ll << b)); // set↵
gen_submask(b-1 , curmask , submask); // unset↵
}↵
else {↵
gen_submask(b-1 , curmask , submask); // unset↵
}↵
}↵
↵
gen_submask(19 , mask , 0);↵
~~~~~↵
↵
the above simple recursive function would print all the submasks for a given mask. ↵
↵
**Optimisation 1:** The second and third parameters (current mask , sub mask) can be combined into a single parameter. ↵
Reason: Since we iterate on bitwise from last to first bit, say I am currently on bit `b`, the last bits (LSB .. b+1) of `current mask` is not required for my further computation, since the submask has been generated for those bits. ↵
↵
Say we are at bit `b`, We could maintain (LSB ... b+1) bits for submask and (b .. 0) bits contain information of input mask. By this way, we would always get information of bit which is under process, and also maintain generated submask in same variable. ↵
Visual for better understanding of the optimisation: ↵
↵
<img src="https://pouch.jumpshare.com/preview/fzkz55htha3BfYp0fMCkef2vz74qG_meaaliaRjDNqbT9m6xq4mdHfLHmss8CF7K99TfJUTouVi3LkeS5tmsJAHzdW6jS0Ur0F3R1GI1Wek">↵
↵
**Optimised code:** ↵
↵
~~~~~↵
void gen_submask(int b , int curmask) { // current bit , current mask↵
if(b < 0) {↵
cout << curmask << endl; // basecase↵
return;↵
}↵
↵
if(curmask&(1ll << b)) { // if bit is set, we have 2 cases↵
gen_submask(b-1 , curmask); // set↵
gen_submask(b-1 , curmask ^ (1ll << b)); // unset↵
}↵
else {↵
gen_submask(b-1 , curmask); // unset↵
}↵
}↵
↵
gen_submask(19 , mask);↵
~~~~~ ↵
↵
This code is simpler to understand, and this prints all submasks, for a given input mask, which serves our purpose. ↵
**Just memoize this recursive function, thats it, SOS DP**. ↵
↵
↵
<spoiler summary="Code">↵
```↵
void gen_submask(int b , int curmask) {↵
if(b < 0) {↵
return F[curmask];↵
}↵
↵
if(dp[b][curmask] != -1) return dp[b][curmask];↵
↵
ll ans = 0;↵
if(curmask&(1ll << b)) { ↵
ans += gen_submask(b-1 , curmask);↵
ans += gen_submask(b-1 , curmask ^ (1ll << b));↵
}↵
else {↵
ans += gen_submask(b-1 , curmask);↵
}↵
return dp[b][curmask] = ans;↵
}↵
```↵
</spoiler>↵
↵
↵
↵
**Conclusion:**↵
↵
- Say any problem related to Sum of Subsets, Supersets, (or any variation of it) we could write a simple recursive function to generate all valid masks (as per the problem) and memoize it using DP. ↵
↵
**Examples:** ↵
↵
- F(Mask) = Sum of all Masks, such that (odd bits are subset, even bits are superset) ↵
↵
↵
↵
↵
↵
↵
