Saturday, 24 May 2014

Bit Manipulation is black magic to me really i just cant figure out how sum of all subsets possible is obtained by it, so just decided to dissect the vexorian's editorial code
here is it
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>

using namespace std;
#define FOR(i,a)    for(long int i = 0;i < a;i++)
#define REP(i,a,b)  for(long int i = a;i < b;i++)
static const int MAX = 100000 * 20 + 1;
bool poss[MAX];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int MinNumber(vector<int> S);
vector<int>S;
int temp,n;
cin>>n;
FOR(i,n)
{cin>>temp;
 S.push_back(temp);
}
int k=MinNumber(S);
cout<<k<<endl;
 return 0;
}
int MinNumber(vector<int> S)
{
    fill(poss, poss + MAX, false);
    int n = S.size();
    // All subsets:
    for (int mask = 0; mask < (1<<n); mask++) {
        cout<<"mask "<<mask<<endl;
        int sum = 0;
        for (int i = 0; i < S.size(); i++) {
            if (mask & (1<<i)) {
            cout<<"S[i] "<<S[i]<<" i "<<i<<endl;
                sum += S[i];
            }
        }
        poss[sum] = true;
    }
    int x = 1;
    while (poss[x]) {
        x++;
    }
    return x;
}

for input like :- 
3
1 2 3 
output is:-
mask 0
mask 1
S[i] 1 i 0
mask 2
S[i] 2 i 1
mask 3
S[i] 1 i 0
S[i] 2 i 1
mask 4
S[i] 3 i 2
mask 5
S[i] 1 i 0
S[i] 3 i 2
mask 6
S[i] 2 i 1
S[i] 3 i 2
mask 7
S[i] 1 i 0
S[i] 2 i 1
S[i] 3 i 2
7
7 is the least possible sum which cannot be generated by all the numbers of the sequence 
and i have trouble finding out how this code does it :P and i have an end semester due on monday RATS!!!!

No comments:

Post a Comment