### chokudai's blog

By chokudai, history, 13 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!

• +47

 » 13 months ago, # |   +2
 » 13 months ago, # |   0 How to solve F?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +13 Use $\sum_{i=0}^{M}{{N+i}\choose{i}}={{N+M+1}\choose{M}}$.
•  » » » 3 months ago, # ^ |   0 what is the name of this formula ?
•  » » » » 7 weeks ago, # ^ |   0 Hockey Stick Identity
 » 13 months ago, # |   +3 For task-D. I spent 30 mins on reading what is meant by expected value and linearity of expectation.
•  » » 13 months ago, # ^ |   0 That was unnice problem. Still don't get it why this is wrong. Somebody explain?
•  » » » 13 months ago, # ^ |   +3 You need to take care of the precision.
•  » » » » 13 months ago, # ^ |   0 It is all integer, and at the end I do division by 2. What can be wrong with precision there?
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Have a look https://atcoder.jp/contests/abc154/submissions/10011578 The final answer need not to be an integer.
•  » » » 13 months ago, # ^ |   0 I really am not the correct guy to explain but I could provide my submission here
•  » » » 13 months ago, # ^ | ← Rev. 3 →   +4 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.
•  » » » » 13 months ago, # ^ |   0 Thanks, got it.
 » 13 months ago, # |   0 can anyone explain a solution for E?
 » 13 months ago, # |   0 Hack in problem E :  10000 3
•  » » 13 months ago, # ^ |   0 whats correct output?
•  » » » 13 months ago, # ^ |   +3 2916
 » 13 months ago, # |   0 Submission 10000000 goes to user lmdexpr! https://atcoder.jp/contests/abc154/submissions/10000000
 » 13 months ago, # |   0 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.
•  » » 13 months ago, # ^ |   +3 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.
•  » » 13 months ago, # ^ |   +3 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.
•  » » » 13 months ago, # ^ |   0 Thank you very much mnbvmar for actually taking the time to edit my code and explain.
• »
»
»
12 days ago, # ^ |
-18

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[2000002],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[0]=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;

}

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