Link to the problem: CSES - Two Sets II
Code:
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
const int MOD = 1e9 + 7;
const ll INF = (1LL<<62);
const int MAXN = 2e5+5;
int main()
{
FASTIO
int n;
cin >> n;
ll dp[MAXN];
memset(dp,0,sizeof(dp));
dp[0] = 1;
int sum = (n*(n+1))/2;
if(!(sum&1))
{
sum /= 2;
for(int i=1; i<=n; i++)
{
for(int j=sum; j>=0; j--)
{
if(i+j <= sum)
{
dp[i+j] += dp[j];
dp[i+j] %= MOD;
}
}
}
cout << dp[sum]/2 << "\n";
}
else
cout << "0\n";
return 0;
}
The above code fails on 5 out of 25 test cases. For example,
For n = 112
Correct output: 979144036
My output: 479144032
Can anyone please point out the error in the above code?
dp[sum]/2
Print the answer modulo 10^9+7
Also Your code is much too complex.
Simpler code
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
const int p = 1e9 + 7;
void solve(){
int n;
cin>>n;
int sum = n*(n+1)/2;
if(sum&1){
cout<<"0\n";
return;
}
sum/=2;
vector<int> dp(sum+1);
dp[0] = (p+1)/2; //(1/2) in mod p
for(int i=1;i<=n;i++){
for(int j=sum;j>=i;--j){
dp[j]+=dp[j-i];
dp[j] >= p ? dp[j]-=p : 0;
}
}
cout<<dp[sum]<<"\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
1 Like
You should divide the ans by the multiplicative inverse of 2 under modulo 1e9 + 7 (because you have to give answer under modulo so you can’t simply divide it by 2 as it is not under the modular divison)
2 Likes
@everule1 What is (1/2) in mod p? And why do you set dp[j] as 0 if it is less than p, shouldn’t it be left as it is?
Oh also the other part, it’s not set to 0 is it’s less than p, it’s left as is.
It opens up to
if(dp[j]>=p){
dp[j]-=p;
}
else{
0;
}
1 Like
why my memoisation dp method failing in 4 test cases.somebody help please
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
ll n;
ll dp[501][70000];
ll f(ll i,ll s)
{
if(i==n+1 && s==0)
return 1;
else if(i==n+1)
return 0;
if(dp[i][s]!=-1)
return (dp[i][s]%mod);
ll x=0;
if(s-i>=0)
x=(f(i+1,s-i)%mod);
ll y=0;
y=(f(i+1,s)%mod);
return dp[i][s]=((x+y)%mod);
}
int main()
{
\
ios::sync_with_stdio(0);
cin.tie(NULL);
cin>>n;
if((n*(n+1)/2)&1)
cout<<"0"<<endl;
else{
memset(dp,-1,sizeof(dp));
ll ans=(f(1,(n*(n+1))/4));
cout<<ans/2<<endl;
}
return 0;
}
maybe it will give you runtime error if n=500 because the sum will be 125250 and you have taken dp array of size 70000.
Here is my code.
#include<iostream>
#include <vector>
using namespace std;
int main()
{
long long n;
cin>>n;
long long t=n;
long long k = n*(n+1)/2;
if(k%2==1){
cout<<"NO\n";
return 0;
}
else
{
long long s1=k/2;
vector<long long> a;
vector<long long> b;
while(n>0)
{
if(n<=s1)
{
s1 = s1 - n;
a.push_back(n);
if(s1==0)
{
cout<<"YES";
}
}
else
{
b.push_back(n);
}
n--;
}
cout<<endl<<a.size()<<"\n";
for (auto element : a)
{
cout<<element << " ";
}
cout<<endl<<b.size()<<"\n";
for (auto element1 : b) {
cout<<element1 << " ";
}
cout<<endl;
}
return 0;
}
Happy to hear some suggestions to improve it.
Hi, I have had the same error in this problem.
The error is that during the dp array construction, the modulo operation is done BEFORE the final division by two.
With n==112, the calculated value of dp[sum] without modulo was 1958288072.
with that value, the answer would have been the good one.
One fix I propose is to use unsigned integers and MOD2 = 2*(1e9+7).
Here a link to the hack of your code (I don’t know how to format it in C++)
https://cses.fi/paste/ce5e43773881dfff3d2665/
#include <bits/stdc++.h>
#define int long long int
int mod = 2*(1e9+7);
void solve(){
int n;
std::cin >> n;
int sum = (n*(n+1))/2;
if(sum%2){
std::cout << "0\n";
return;
}
std::vector <int> dp(sum+1);
dp[0] = 1;
for(int i=1; i<=n; i++){
for(int j=sum; j>0; j--){
if(j-i >= 0)
dp[j] = (dp[j]+dp[j-i])%mod;
}
}
std::cout << dp[sum/2]/2 << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
int t = 1;
//std::cin >> t;
while(t--){
solve();
}
}
Can u explain your solution bro