chokudai's blog

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

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

How to solve F?

»
19 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.

  • »
    »
    19 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?

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

      You need to take care of the precision.

    • »
      »
      »
      19 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

    • »
      »
      »
      19 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.

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

can anyone explain a solution for E?

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

Hack in problem E : 10000 3

»
19 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

»
19 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.

  • »
    »
    19 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.

  • »
    »
    19 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.

    • »
      »
      »
      19 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      please explain where i m wrong..

      include<bits/stdc++.h>

      include <ext/pb_ds/assoc_container.hpp>

      include <ext/pb_ds/tree_policy.hpp>

      using namespace __gnu_pbds; using namespace std;

      define ff first

      define ss second

      define int long long

      define pb push_back

      define mp make_pair

      define pii pair<int,int>

      define vi vector

      define mii map<int,int>

      define pqb priority_queue

      define pqs priority_queue<int,vi,greater>

      define setbits(x) __builtin_popcountll(x)

      define zrobits(x) __builtin_ctzll(x)

      define mod 1000000007

      define inf 1e18

      define ll long long

      define ps(x,y) fixed<<setprecision(y)<<x

      define mk(arr,n,type) type *arr=new type[n];

      define w int x12;cin>>x12;while(x12--)

      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;

      }

»
19 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.

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

How to solve E?

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

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