I am trying the CSES problem set. I am getting WA on a few tests in Two Sets — II question. Here is the link for the question https://cses.fi/problemset/task/1093↵
↵
My approach is to create a dp[i][j] which stores the number of ways to get sum i using first j indices. My target is to get sum n*(n-1)/4 . Formula I use is- dp[i][j]=dp[i][j-1]+dp[i-j][j-1];↵
↵
I initialized dp[0][i] to 1 for all i<=n bcoz the only possible way is to select no indice at all.↵
And also dp[i][0] to 0 for all 1<=i<=target bcoz its not possible to create a sum using no digits at all.↵
I then print (dp[target][n])/2;↵
↵
Please help. I am getting WA on few tests.↵
↵
code- ↵
↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
#include <set>↵
#include <iomanip>↵
#include <cmath>↵
↵
#define vi vector<int>↵
#define tests int t; cin>>t; while(t--)↵
#define ll long long↵
#define vll vector<long long>↵
#define sort(v) sort(v.begin(), v.end())↵
#define sortg(v) sort(v.begin(), v.end(), greater<int> ())↵
↵
using namespace std;↵
↵
char nums[10] = { '0','1','2','3','4','5','6','7','8','9' };↵
char alphsl[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };↵
const ll MOD = 1000000007;↵
↵
using namespace std;↵
↵
↵
↵
void solve() {↵
↵
ll n;↵
cin >> n; ↵
if ((n * (n + 1))%4 != 0) {↵
cout << 0 << endl;↵
return;↵
↵
}↵
↵
ll target = (n * (n + 1)) / 4;↵
↵
vector<vector<ll>> numways(target+1, vector<ll> (n+1, 0));↵
↵
for (ll i = 0; i < n+1; i++) {↵
numways[0][i] = 1;↵
}↵
↵
for (ll i = 1; i < target+1; i++) {↵
numways[i][0] = 0;↵
}↵
↵
for (ll i = 1; i <= target; i++) {↵
for (ll j = 1; j < n+1; j++) {↵
numways[i][j] = numways[i][j - 1];↵
if (i - j >= 0) {↵
numways[i][j] += numways[i - j][j - 1];↵
}↵
numways[i][j] %= MOD;↵
}↵
}↵
↵
cout << numways[target][n]/2 << endl;↵
↵
}↵
↵
int main() {↵
↵
↵
↵
solve();↵
↵
return 0;↵
}https://codeforces.me/contest/1400/submission/91190026↵
↵
The question is irrelevant in this link. Only the code is relevant
↵
My approach is to create a dp[i][j] which stores the number of ways to get sum i using first j indices. My target is to get sum n*(n-1)/4 . Formula I use is- dp[i][j]=dp[i][j-1]+dp[i-j][j-1];↵
↵
I initialized dp[0][i] to 1 for all i<=n bcoz the only possible way is to select no indice at all.↵
And also dp[i][0] to 0 for all 1<=i<=target bcoz its not possible to create a sum using no digits at all.↵
I then print (dp[target][n])/2;↵
↵
Please help. I am getting WA on few tests.↵
↵
code- ↵
↵
#include <vector>↵
#include <algorithm>↵
#include <set>↵
#include <iomanip>↵
#include <cmath>↵
↵
#define vi vector<int>↵
#define tests int t; cin>>t; while(t--)↵
#define ll long long↵
#define vll vector<long long>↵
#define sort(v) sort(v.begin(), v.end())↵
#define sortg(v) sort(v.begin(), v.end(), greater<int> ())↵
↵
using namespace std;↵
↵
char nums[10] = { '0','1','2','3','4','5','6','7','8','9' };↵
char alphsl[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };↵
const ll MOD = 1000000007;↵
↵
using namespace std;↵
↵
↵
↵
void solve() {↵
↵
ll n;↵
cin >> n; ↵
if ((n * (n + 1))%4 != 0) {↵
cout << 0 << endl;↵
return;↵
↵
}↵
↵
ll target = (n * (n + 1)) / 4;↵
↵
vector<vector<ll>> numways(target+1, vector<ll> (n+1, 0));↵
↵
for (ll i = 0; i < n+1; i++) {↵
numways[0][i] = 1;↵
}↵
↵
for (ll i = 1; i < target+1; i++) {↵
numways[i][0] = 0;↵
}↵
↵
for (ll i = 1; i <= target; i++) {↵
for (ll j = 1; j < n+1; j++) {↵
numways[i][j] = numways[i][j - 1];↵
if (i - j >= 0) {↵
numways[i][j] += numways[i - j][j - 1];↵
}↵
numways[i][j] %= MOD;↵
}↵
}↵
↵
cout << numways[target][n]/2 << endl;↵
↵
}↵
↵
int main() {↵
↵
↵
↵
solve();↵
↵
return 0;↵
}
↵
The question is irrelevant in this link. Only the code is relevant
