1

AtCoder Beginner Contest 154 Announcement

 1 year ago
source link: http://codeforces.com/blog/entry/73747
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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!

3 years ago, # |

How to solve F?

  • 3 years ago, # ^ |

    ← Rev. 2 →  

    +13

    • 23 months ago, # ^ |

      what is the name of this formula ?

3 years ago, # |

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

  • 3 years ago, # ^ |

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

    • 3 years ago, # ^ |

      You need to take care of the precision.

      • 3 years ago, # ^ |

        It is all integer, and at the end I do division by 2. What can be wrong with precision there?

    • 3 years 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.

      • 3 years ago, # ^ |

        Thanks, got it.

3 years ago, # |

Hack in problem E : 10000 3

  • 3 years ago, # ^ |

    whats correct output?

    • 3 years ago, # ^ |

3 years ago, # |

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 to and then simply evaluted.

  • 3 years ago, # ^ |

    You can do the same simplification again to eliminate the remaining summation, so you end up with a completely closed form that looks like (where , , , 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 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 . (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.

  • 3 years ago, # ^ |

    You can precompute the inverses of factorials in as well: https://atcoder.jp/contests/abc154/submissions/10024715. Then you can evaluate a single binomial in constant time instead of , and here the code runs roughly 10x quicker.

    • 3 years ago, # ^ |

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

3 years ago, # |

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

3 years ago, # |

How to solve E?

  • 3 years ago, # ^ |

    ← Rev. 2 →  

    0

    Standard Digit DP problem
    Blog

    • 3 years ago, # ^ |

      Thanks!

12 minutes ago, # |

可以用 ntt 强凹， 但因为我不知道1e9+7的ntt, 所以用的任意模数ntt的板子。 C(x+y,x) = (x+y)! / x! / y! , 则可转化为 指数型生成函数，相乘，最后将得到的每个位乘以 i! 加起来就完了。

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);

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK