Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### chokudai's blog

By chokudai, history, 2 weeks 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 (24)
 »
 » How to solve F?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   Use $\sum_{i=0}^{M}{{N+i}\choose{i}}={{N+M+1}\choose{M}}$.
 » 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?
•  » » » » » 2 weeks 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
•  » » » 2 weeks 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.
 » Peculiar similarity between E and 1036C - Classy Numbers, except in E you need to directly manipulate on strings.
 » How to solve E?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   Standard Digit DP problemBlog
•  » » » Thanks!