Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### jayantjha1109's blog

By jayantjha1109, history, 4 years ago,

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;

code-

https://codeforces.com/contest/1400/submission/91190026

The question is irrelevant in this link. Only the code is relevant

• +1

| Write comment?
 » 4 years ago, # |   0 Auto comment: topic has been updated by jayantjha1109 (previous revision, new revision, compare).
 » 4 years ago, # |   0 Auto comment: topic has been updated by jayantjha1109 (previous revision, new revision, compare).
 » 4 years ago, # |   0 Auto comment: topic has been updated by jayantjha1109 (previous revision, new revision, compare).
 » 4 years ago, # |   0 Use inverse modulo under 2 instead of just dividing the number.
•  » » 4 years ago, # ^ |   0 Sorry for being silly but what is (inverse modulo under 2) supposed to mean?
•  » » » 4 years ago, # ^ |   0 If you are dividing some number a by any other number by b and you need to take modulo also after or before the division operation like ans = (a / b ) % MOD. Then you cannot do this directly, you have to calculate the inverse modulo of b under MOD then do this:ans = a % MOD * (inv(b)) % MOD.To calculate you can use fermate little theorem if MOD is prime: inv(b) = bᴹᴼᴰ⁻² % MOD. Now you are done, you can find inv(b) efficiently by power expo.
•  » » » » 4 years ago, # ^ |   0 Thanks it got accepted. I did not know this property before. So, thanks for introducing it to me.
•  » » » » 3 years ago, # ^ |   0 Late thanks here! This helped me quite a lot.
•  » » » » » 16 months ago, # ^ |   0 +1
•  » » » » » 2 months ago, # ^ |   0 +1