sinhachhavi3's blog

By sinhachhavi3, history, 2 years ago, In English

can someone help me with yesterday's code jam to I/O second question? particularly test set 2 How to approach the problem and how to implement it?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By sinhachhavi3, history, 2 years ago, In English

include<bits/stdc++.h>

using namespace std;

//#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

define ll long long

//#define ordered_set tree<ll,null_type,less,rb_tree_tag,tree_order_statistics_node_update>

define pb push_back

define mp make_pair

define mod (ll)1000000007

define N (int)200005

define maxN (int)1000002

define MOD (ll)998244353

//there are other prime numbers as well such as 1e9+9,1e6+69

define inf (ll)LLONG_MAX

define ninf (ll)LLONG_MIN

define F first

define S second

define pi pair<int,int>

define pll pair<long long int,long long int>

define pqi priority_queue //default max heap//multiply with -1 to convert to min heap

define pqii priority_queue <int,vector,greater>

define pq priority_queue <pi,vector , greater>

define rep(i,a,b) for(int i=a;i<(int)b;i+=1)

define fr(i,a,b) for(ll i=a;i<(ll)b;i+=1)

define fre(i,a,b) for(ll i=a;i<=(ll)b;i+=1)

define rfre(i,a,b) for(ll i=a;i>=(ll)b;i-=1)

define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

void solve() { int n;cin>>n;

vector<int> vec(n);

int sum=0;

for(int i=0;i<n;i+=1) {cin>>vec[i];sum+=vec[i];}

//int sum=0;



//there is another one that is partial sum 

if(sum%2) {cout<<0<<"\n";return;}

int x=sum/2;

bool dp[n+1][sum+1];

bool f=0;

for(int i=0;i<=n;i+=1)
{
    for(int j=0;j<=sum;j+=1) dp[i][j]=0;
}

for(int i=0;i<n;i+=1)
{
    dp[i+1][vec[i]]=1;
}

dp[0][0]=1;

//empty subset with 0 sum 
for(int i=1;i<=n;i+=1)
{
    for(int k=0;k<=sum;k+=1)
    {
        //dp[i][k] is true if the set of first i elements can yield a sum of k else no 
        if(dp[i-1][k]==1) dp[i][k]=1;
        else
        {
            if(vec[i-1]==k) dp[i][k]=1;
            else
            {
                if(vec[i-1]>k) dp[i][k]=0;
                else 
                {
                    if(dp[i-1][k-vec[i-1]]) dp[i][k]=1;
                    else dp[i][k]=0;
                }
            }
        }
    }
}

if(dp[n][x])
{
    cout<<1<<" ";
    int idx=-1;

    for(int i=0;i<n;i+=1)
    {
        if(vec[i]%2) {idx=i+1;break;}
    }

    if(idx==-1)
    {
        vector<int> arr;
        for(int i=0;i<n;i+=1)
        {
            for(int j=0;j<=12;j+=1)
            {
                if(vec[i]&(1<<j)) {arr[i]=j;break;}
            }
        }

        int ans=arr[0];
        int mn=1;
        for(int i=1;i<n;i+=1) if(arr[i]<ans) {ans=arr[i];mn=i+1;}
        cout<<mn<<"\n";
    }
    else cout<<idx<<"\n";
}
else cout<<0<<"\n";

}

int main() { fio; int tc=1;//cin>>tc; while(tc--) { solve(); } return 0; }

https://codeforces.com/contest/1516/problem/C //problem name-Baby Ehab Partitions Again i'm constantly getting runtime error on test 6,with exit code 2147483647 can someone please help me correct my code?

Full text and comments »

  • Vote: I like it
  • -26
  • Vote: I do not like it

By sinhachhavi3, history, 3 years ago, In English

Do we get the editorial for Facebook Hackercup after the contest gets over,if not proper editorial,then hints or tags maybe,something of that sort?

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it