chokudai's blog

AtCoder Beginner Contest 154 Announcement
By chokudai, history, 5 years ago, In English

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!

  • Vote: I like it
  • +47
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Screencast + Brief Explanations

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For task-D. I spent 30 mins on reading what is meant by expected value and linearity of expectation.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That was unnice problem. Still don't get it why this is wrong. Somebody explain?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You need to take care of the precision.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack in problem E : 10000 3

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Submission 10000000 goes to user lmdexpr! https://atcoder.jp/contests/abc154/submissions/10000000

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 code

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much mnbvmar for actually taking the time to edit my code and explain.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Peculiar similarity between E and 1036C - Classy Numbers, except in E you need to directly manipulate on strings.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can use NTT to solve it, but waste some time. Because I don't know the NTT of 1e9+7, I use the board of any mod NTT. C(x+y,x) = (x+y)! / x! / y! , Then it can be converted into an exponential generating function, multiplied, and finally multiply each bit by i!. Add it up.

mod = 1e9+7
n = m = 1e6 + 10;
int lx = read(), ly = read(), rx = read(), ry = read();
for (int i = lx;i <= rx;i++) A[i] = Int(invfac[i]);
for (int i = ly;i <= ry;i++) B[i] = Int(invfac[i]);
Poly::init(n + m);
Poly::NTT(A), Poly::NTT(B);
for (int i = 0; i < Poly::lim; ++i) A[i] = A[i] * B[i];
Poly::NTT(A, 0);
ll res = 0;
for (int i = 0; i < n + m - 1; ++i) res = (res + fac[i] * A[i].get() % mod) % mod;
printf("%lld\n", res);
→ Reply