Wednesday, 08 December, 2021

Rifat's Blog

Competitive Programming Notebook

single post

  • Home
  • HackerEarth-Faizu on a space war
DP, Solve By OJ, Solve By Topic

HackerEarth-Faizu on a space war

Problem NameFaizu on a space war
JudgeHackerEarth
Problem Linkhttps://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/practice-problems/algorithm/faizu-on-a-space-war/
Algorithms & DSDynamic Programming , BitMasking
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define sf(n) scanf("%lld",&n);
#define YES printf("YES\n");
#define NO printf("NO\n");
#define nl printf("\n");
#define PB push_back
#define VST(V) sort(V.begin(),V.end())
#define VSTrev(V) sort(V.begin(),V.end(),greater<long long int>())
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll SET(ll NUM,ll POS)
{
    return NUM | (1<<POS);
}
bool isOn(ll NUM,ll POS)
{
    return (bool)(NUM & (1<<POS));
}
ll n,mem[1<<16][17][17];
vector<ll>V;
ll dp(ll mask,ll start,ll pre)
{
    if(start!=-1&&mem[mask][start][pre]!=-1)
    {
        return mem[mask][start][pre];
    }
    ll ans=0;
    for(ll i=0; i<n; i++)
    {
        if(isOn(mask,i)==0)
        {
            ll tm_mask=SET(mask,i);
            ll x=start;
            ll previous=V[i];
            if(x==-1)
            {
                x=i;
            }
            else
            {
                previous=V[pre];
            }
            ll val=(V[i]^previous)+dp(tm_mask,x,i);
            if(mask==(1<<n)-1)
            {
                val+=(V[x]+V[i]);
            }
            ans=max(ans,val);
        }
    }
    if(start!=-1)mem[mask][start][pre]=ans;
    return ans;
}
int main()
{
    //freopen("1input.txt","r",stdin);
    fast;
    ll tcase=1;
    //cin>>tcase;
    for(ll test=1; test<=tcase; test++)
    {
        V.clear();
        cin>>n;
        for(ll i=0; i<n; i++)
        {
            string s;
            cin>>s;
            ll siz=s.size();
            ll sum=0;
            for(ll j=0; j<siz; j++)
            {
                sum+=s[j]-'a'+1;
            }
            V.PB(sum);
        }
        for(ll i=0; i<(1<<n)+10; i++)
        {
            for(ll j=0; j<=n; j++)
            {
                for(ll k=0; k<=n; k++)
                {
                    mem[i][j][k]=-1;
                }
            }
        }
        ll ans=dp(0LL,-1,0);
        cout<<ans<<"\n";
    }
    return 0;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

Created by Abu Rifat Muhammed Al Hasib
2021 © All rights reserved


error: Alert: Content is protected !!