chokudai's blog

By chokudai, history, 2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    Use $$$\sum_{i=0}^{M}{{N+i}\choose{i}}={{N+M+1}\choose{M}}$$$.

»
2 months 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.

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You need to take care of the precision.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I really am not the correct guy to explain but I could provide my submission here

    • »
      »
      »
      2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain a solution for E?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack in problem E : 10000 3

»
2 months 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

»
2 months 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.

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

»
2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's a good c++ compiler on MAC like dev-c++