Atcoder ABC 169 F - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

My observation is : Let an array A has length n and a subset of A is B. Now, if B has length k then it appears also in other 2^(n-k) subsets of array A.

So I used a 2d dp dp[i][j] which denotes if I take elements upto i then how many subsets have remaining sum j. And the ans is dp[n][0].

Base case is when i >= n then if the remaining sum is 0 that means we got a subset having sum S. Now we have to return in how many other subsets the current segment belongs. So if remaining sum = 0 then I returned pow(2,n-k) otherwise 0;

I thought this is the correct approach. Please correct my approach. I don't understand why it is not working.

Problem Link

My Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define         pb         push_back
#define         sf(x)      scanf("%d",&x)
#define         sfl(x)     scanf("%lld",&x)
#define         pf(x)      printf("%d\n",x)
#define         pfl(x)     printf("%lld\n",x)
#define         endl       '\n'

#define        MOD 998244353


ll binPow(ll a, ll q) {
    a %= MOD;
    if (q == 0) return 1;
    return ((q % 2 == 1 ? a : 1) * binPow(a * a, q / 2)) % MOD;
}

ll n;

ll ar[4000];

ll dp[3009][3009];


ll sol(ll i,ll remaining_sum,ll cnt)
{
    if(i>=n)
    {
        if(remaining_sum == 0)
        {
            return binPow(2ll,n-cnt);
        }
        else return 0;
    }


    if(dp[i][remaining_sum] != -1)return dp[i][remaining_sum];

      if(remaining_sum == 0)
        {
            return binPow(2ll,n-cnt);
        }

    ll ans = 0;

    ans = (ans + sol(i+1,remaining_sum-ar[i],cnt+1) +  sol(i+1,remaining_sum,cnt))%MOD;

    return dp[i][remaining_sum] = ans;
}

int main()
{
    ll i,j,k,l,m,s;

    sfl(n);
    sfl(s);

    for(i=0;i<n;i++)sfl(ar[i]);

    memset(dp,-1,sizeof dp);

    pfl(sol(0,s,0));
}

Comments (1)

Show archived | Write comment?

CatFirstSearch

8 months ago, # |

I think you will have to introduce another state in your dp to get the correct solution but it would be too slow then , you can define your dp ij as till prefix i , what is the sum of count of subsequences such that their sum is j and then the transitions are straightforward.

Solution:You can refer my submission here to get a hint

→ Reply

LIFE_GOES_ON's blog