Xenomorphing_19's blog

By Xenomorphing_19, 3 years ago, In English

I've been trying a Problem: Target Sum in Dynamic Programming. I tried solving it by two methods: 1. recursion with memorization 2. Tabular DP In the second method, I'm receiving a WA verdict for the cases having all the elements equal. I've checked multiple sources if there is an error in my code but the codes which I found on those sites are also giving wrong answers[identical to my code]. I am unable to get my code work correctly. Here are both the codes I've written. Thanks in Advance.

Tabular DP

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(auto it:nums) sum+=it;
        int n=nums.size();
        sum+=target;
        if(sum%2!=0) return 0;
        sum/=2;
        int dp[n+1][sum+1];
        sort(nums.begin(),nums.end());
        for(int i=0;i<=sum;i++) dp[0][i]=0;
        for(int i=0;i<=n;i++) dp[i][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=sum;j++)
            {
                if(nums[i-1]<=j) dp[i][j] = dp[i-1][j-nums[i-1]] + dp[i-1][j];
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][sum];
    }
};

Recursion with Memoization

class Solution {
public:
    map <pair<int,int>,int> mp;
    int solve(vector <int> &A,int target, int ind, int sum)
    {
        if(ind==A.size())
        {
            if(sum==target) return 1;
            return 0;
        }
        if(mp.find({ind,sum})!=mp.end()) return mp[{ind,sum}];
        int a=solve(A,target,ind+1,sum+A[ind]);
        int b=solve(A,target,ind+1,sum-A[ind]);
        return mp[{ind,sum}] = (a+b);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        mp.clear();
        return solve(nums,target,0,0);
    }
};

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

By Xenomorphing_19, history, 3 years ago, In English

The problem I'm trying to solve is: Problem I'm implementing Fenwick Trees in a 2D matrix. Also I've been using Fast i/o but I'm still getting a TLE. I'm not sure if this approach would work. Please help me with this. Thanks in advance. My Code:

#include <bits/stdc++.h>
using namespace std;
vector <long long> freq[1030];
long long n;
void update(long long x,long long y,long long val)
{
    while(y<=n)
    {
        freq[x][y]+=val;
        y = y + (y & -y);
    }
}
long long sum(long long x,long long ind)
{
    long long s=0;
    while(ind>0)
    {
        s+=freq[x][ind];
        ind = ind - (ind & -ind);
    }
    return s;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        for(long long i=0;i<=n;i++)
        {
            freq[i].clear();
            freq[i].resize(n+5,0);
        }
        char s[100] ="hehe";
        while(strcmp(s,"END")!=0)
        {
            scanf("%s",s);
            if(strcmp(s,"SET")==0)
            {
                long long x,y,v;
                scanf("%lld %lld %lld",&x, &y, &v);
                x++;
                y++;
                update(x,y,v-freq[x][y]);
            }
            else if(strcmp(s,"SUM")==0)
            {
                long long ans=0;
                long long x1,x2,y1,y2;
                scanf("%lld %lld %lld %lld",&x1, &y1, &x2, &y2);
                x1++;
                y1++;
                x2++;
                y2++;
                for(long long i=x1;i<=x2;i++)
                {
                    ans+=sum(i,y2)-sum(i,y1-1);
                }
                printf("%lld\n",ans);
            }
        }
    }
}

Full text and comments »

By Xenomorphing_19, history, 3 years ago, In English

I have written the following code for the problem Linova and Kingdom I am getting a WA on some test cases. I am unable to identify the error. Please help me out.

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
vector <ll> vec[200006],contri(200006,0),sub(200006,1);
void solve(ll node, ll parent, ll level)
{
    int cnt=0;
    for(auto it:vec[node])
    {
        if(it!=parent)
        {
            solve(it,node,level+1);
            cnt+=sub[it];
        }
    }
    sub[node]+=cnt;
    contri[node] = level-sub[node];
}
int main()
{
    ll n,k;
    cin>>n>>k;
    for(ll i=0;i<n-1;i++)
    {
        ll u,v;
        cin>>u>>v;
        vec[v].pb(u);
        vec[u].pb(v);
    }
    solve(1,0,1);
    sort(contri.begin(),contri.end(),greater<ll>());
    ll ans=0;
    for(ll i=0;i<k;i++)
    {
        ans+=contri[i];
    }
    cout<<ans;
}

Thanks in advance

Full text and comments »

By Xenomorphing_19, 4 years ago, In English

I have used the following approach but it is getting me a WA. Please help me out if you can.

  • Sorting the elements in descending order while the friends in ascending order.
  • distributing elements (highest to lowest) one by one among friends.

ex: E: 7 7 6 6 3 2 1| F: 1 1 2 3

distribution: (7) — — -| (7) (7) — -| (7) (7) (6) -| (7) (7) (6) (6)| (7) (7) (6,3) (6)| (7) (7) (6,3) (6,2)| (7) (7) (6,3) (6,2,1)|

Under which testcase will this give a wrong solution

Full text and comments »