### chokudai's blog

By chokudai, history, 19 months ago, We will hold AtCoder Beginner Contest 154.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation! Comments (28)
 »
 » How to solve F?
•  » » 19 months ago, # ^ | ← Rev. 2 →   Use $\sum_{i=0}^{M}{{N+i}\choose{i}}={{N+M+1}\choose{M}}$.
•  » » » what is the name of this formula ?
•  » » » » Hockey Stick Identity
 » For task-D. I spent 30 mins on reading what is meant by expected value and linearity of expectation.
•  » » That was unnice problem. Still don't get it why this is wrong. Somebody explain?
•  » » » You need to take care of the precision.
•  » » » » It is all integer, and at the end I do division by 2. What can be wrong with precision there?
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   Have a look https://atcoder.jp/contests/abc154/submissions/10011578 The final answer need not to be an integer.
•  » » » I really am not the correct guy to explain but I could provide my submission here
•  » » » 19 months ago, # ^ | ← Rev. 3 →   cout doesn't work well with big float numbers if you don't use setprecision.For example, if d is 87654321. cout << d / 2 << endl; // Prints 4.38272e+07 cout << setprecision(10) << d / 2 << endl; // Prints 43827160.5 As you can see, outputs are very different.
•  » » » » Thanks, got it.
 » can anyone explain a solution for E?
 » Hack in problem E :  10000 3
•  » » whats correct output?
•  » » » 2916
 » Submission 10000000 goes to user lmdexpr! https://atcoder.jp/contests/abc154/submissions/10000000
 » What is the intended solution for F? My solution https://atcoder.jp/contests/abc154/submissions/10004590 passed however, took 1977 ms, at which point it's just luck that it passed within the 2s time limit. So clearly either I implemented this horribly bad, or it was not the intended solution.I simplified $\sum_{i=r1}^{r2}\sum_{j=c1}^{c2}{{i+j}\choose{j}}$ to $\sum_{j=c1}^{c2}{{r2+j+1}\choose{j+1}}-{{r1+j}\choose{j+1}}$ and then simply evaluted.
•  » » You can do the same simplification again to eliminate the remaining summation, so you end up with a completely closed form that looks like $A-B-C+D$ (where $A$, $B$, $C$, $D$ are each a single binomial coefficient). my codepublic void solve(int testNumber, InputReader in, PrintWriter out) { int r1 = in.nextInt() - 1, c1 = in.nextInt() - 1; int r2 = in.nextInt(), c2 = in.nextInt(); long answer = mod.subtract(mod.add(f(r2, c2), f(r1, c1)), mod.add(f(r2, c1), f(r1, c2))); out.println(answer); } private long f(int x, int y) { return mod.subtract(mod.ncr(x + y + 2, y + 1), 1); } By the way, instead of worrying about the lower bounds, since they make it a little messier, I solved the problem for the special case of $(r_1, c_1) = (0, 0)$ and then used the fact that you can use principle of inclusion-exclusion to express an arbitrary rectangle as the sum/difference of four rectangles starting at $(0, 0)$. (Very similar to how people use [a, b) = [0, b) - [0, a) all the time when there's only one dimension.)Doing it this way makes the final answer a lot easier to come to and code up bug-free, I think.
•  » » You can precompute the inverses of factorials in $O(N)$ as well: https://atcoder.jp/contests/abc154/submissions/10024715. Then you can evaluate a single binomial in constant time instead of $O(\log \mathrm{MOD})$, and here the code runs roughly 10x quicker.
•  » » » Thank you very much mnbvmar for actually taking the time to edit my code and explain.
• »
»
»

please explain where i m wrong..

# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds; using namespace std;

# define F10 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef tree<int,null_type,less,rb_tree_tag,tree_order_statistics_node_update> pbds; int r1,r2,c1,c2,mfactorial,ans=1,nrow,ncol; int power(int a,int b) { int ans=1; while (b) { if(b%2) { ans=(ans*a)%mod; } a=(a*a)%mod; b=b/2; } return ans; } ll modExp(ll x, ll n) { if (n==0) return 1; if (n==1) return x%mod; ll ans = modExp(x,n/2); ans = (ans*ans)%mod; if (n%2) ans*=x; return ans%mod; } int combination(int n,int r ) { int ans=mfactorial[n],a,b; // a=power(mfactorial[r],mod-2); // b=power(mfactorial[n-r],mod-2); a=modExp(mfactorial[r],mod-2); b=modExp(mfactorial[n-r],mod-2); ans=(ans*a)%mod; ans=(ans*b)%mod; return ans; } int32_t main() {

cin>>r1>>c1>>r2>>c2;
mfactorial=1;
for (int i = 1; i <= 2000001; ++i) {
mfactorial[i]=(mfactorial[i-1]*i)%mod;
}
ans=combination(r1+c1,r1);
nrow=r2-r1+1;ncol=c2-c1+1;
for (int row = 1; row <=r2-r1; ++row) {
ans=(ans+((nrow-row)*
(ncol-1))%mod*combination(r1+c1+row,c1)%mod+combination(r1+c1+row,c1))%mod;
}
for (int col = 1; col <=c2-c1 ; ++col) {
ans=(ans+((nrow-1)*(ncol-col))%mod
*combination(r1+c1+col,r1)%mod+combination(r1+c1+col,r1))%mod;
}
cout<<ans;

}

 » Peculiar similarity between E and 1036C - Classy Numbers, except in E you need to directly manipulate on strings.
 » How to solve E?
•  » » 19 months ago, # ^ | ← Rev. 2 →   Standard Digit DP problemBlog
•  » » » Thanks!
 » What's a good c++ compiler on MAC like dev-c++