atcoder_official's blog

AtCoder Beginner Contest 382 Announcement
By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 382.

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

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

I hope I can get a performance of 2270, then achieve 2000 in rating.

→ Reply
»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Hope the problems in this contest is better than last ABC.

→ Reply
»
2 months ago, # |
  Vote: I like it -29 Vote: I do not like it

gimme like plz

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

It seems that D will be more difficult than usual. GL&&HF!

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

My c resolve the question , but is not fast . Im sad. :(

→ Reply
»
2 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Why problem G even exists??? Did author came up with it when he was drunk and on drugs???????

→ Reply
»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it

they put a 3500 level problem in the last question of "beginner" contest that <= 3 people will solve.... again.

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

how can one approach e problem

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

E is a nice problem even though it's very classical.

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

Hello,

Can somebody explain why this is giving WA for C.

Thanks!

Submission

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

    the search space to find smallest index 'i' such that Ai <= Bj is not monotonic in your binary search . A smaller index value can also be located at a higher or lower l index so you would have to check both directions.

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

E was nice, but it for sure wasn't Python-friendly

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

In problem C, what if everyone could just eat one sushi, can we solve it in O(nlogn)?

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Yes, using ordered set

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

      This doesn't seem to work. For each sushi, we need to find a number that is greater than or equal to it and is at the front. This requires two dimensions to be ordered at the same time, but the set is ordered in one dimension and disordered in the other dimension.

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

        Okay, misunderstood with statement. Now you can solve with help of segment tree, where we store the indices of elements in first array after sorting, then every time we get some index i, where 0 — i is suitable range or more formally these people can eat, find the minimum index so this person eats and hange the index to INF so that we are not considering it again. Changing minimum element position done using precomputation where we store the position where the index is present. Hope you got it;)

        → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      binary search is enough.

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

    Binary search+ prefix max

    → Reply
»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

The Editorial(https://atcoder.jp/contests/abc382/editorial/11487) should be $$$f_i =\frac{1}{1 - g_0}\displaystyle(1+\sum_{j = 1}^{N} f_{ \max(i - j, 0) }g_j)$$$ not $$$f_i =\frac{1}{1 - g_0}\displaystyle\sum_{j = 1}^{N} f_{ \max(i - j, 0) }g_j$$$.

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

    Can you please explain how did you get the equation for "fi"?

    I am unable to understand the editorial.

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

I am confused about problem E.

I didn't consider $$$f_j$$$ transporting from itself while doing DP. But why can my code still get the right answer in some testcases(30/35)?

can anyone help answer this?

int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;++i)scanf("%lf",&p[i]),p[i]/=100.0;
    g[0][0]=1;
    for(int i=1;i<=n;++i)
    {
        g[i][0]=g[i-1][0]*(1-p[i]);
        for(int j=1;j<=i;++j)
            g[i][j]=g[i-1][j-1]*p[i]+g[i-1][j]*(1-p[i]);
    }
    f[0]=0;
    for(int i=1;i<=x;++i)
    {
        f[i]=1;
        for(int j=max(0,i-n);j<i;++j)
        {
            f[i]+=f[j]*g[n][i-j];
        }
    }
    printf("%.16lf",f[x]);
    return 0;
}
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    When some $$$p_i=100$$$, $$$g_0=0$$$, then $$$\frac{1}{1-p}=1$$$.

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

https://atcoder.jp/contests/abc382/submissions/60347732 can anyone tell me where my code is wrong? I'd really appreciate it.

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

    it passes half of the test, so most likely i think its in the segment tree. but i cannot find it

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

    I'm assuming this line 

    f.add(1, w, 1, v[i][1], v[i][1]+v[i][2]-1, 1);

    adds 1 to every elemet in the range but instead it should assign the current blocks height to the range.

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

      can this question be interpreted as all the blocks drop in the same time? if that's right，then I'm just suming up the maxmum numbers of blocks below every block and the answer is h minus the maximum number

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

      i know it, thank you very much

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

      TYSM even i was doing the same mistake

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

For problem E, I first got a solution that works as follows. We first calculate e = (p[1] + p[2] + p[3] + ... + p[n]) / 100.0, which is the expected number of rare cards that we can get from a pack. Then, we just compute x / e as the answer. But I find that this can not even pass the samples, and why this intuitively correct solution is not correct?

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

    How is this even intuitively correct

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

    This might work in theory if you could open fractional decks (e.g. spend 1/100th the regular amount, but the # of rare cards gained is divided by 100 as well), since you could spend infinitesimally small amounts to converge on the value $$$e$$$ above as the # of rares per unit deck opened. For the original problem, this won't work because if you have something like $$$X=1$$$ and $$$P=[100,100,...,100]$$$, then $$$X/e$$$ will yield a value smaller than 1, which is impossible. You instead have to consider the problem in terms of states and transitions, where your state is the number of rares $$$r$$$ owned, and a transition consists of opening $$$i$$$ rares in a deck with some probability, which transitions from $$$r$$$ to $$$\min(X, r+i)$$$.

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

      Thank you so~ much for your kind and detailed reply. I think your arguments really make sense, which helps me a lot. Your words "fractional decks" inspire me a lot!

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

Is there a guide on how to use the AtCoder library in python?

I got the right idea for F but my implementation of lazy segtree was too slow.

EDIT: I figured it out. NVM.

→ Reply
»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I'm not sure if I misunderstood the question due to my poor English.

But in my understanding, E ask the answer of "at least X Cards" question.

However, in the Editorial (and test data,I think),it seems to solve the "exactly X cards" question.

Because the Editorial said "we can compute f_x in a total of O(NX) time.", and I spant almost AN HOUR to debug and found that my answer of the "exactly question" is same as the the sample Input. (and I got AC of course)

I initiated a clarification but no one answer me until now.

Or maybe I actually got the answer of "at least question"? Can someone tell me ?

My code is below. I have made it concise for readability.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050;
int n,m;
long double ans,p[maxn],f[maxn];
int main(){
	n = read(),m = read();
	p[0] = 1;
	for(int i = 1; i <= n; i ++){
		long double x = read() / 100.0L;
		for(int j = i; j >= 1; j --) p[j] = p[j] * (1 - x) + p[j - 1] * x;
		p[0] *= 1 - x;
	}
	for(int i = 1; i <= m; i ++){
		f[i] = 1;
		for(int j = 1; j <= i && j <= n; j ++){
			if(i - j >= m) continue;
			f[i] += p[j] * f[i - j];
		}
		f[i] /= 1 - p[0];
	}
	printf("%.8Lf\n",f[m]);
   return 0;
}
→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Originally, I had to calculate many additional things to tally the "at least question" answers. If I hadn't accidentally discovered that the value of $$$f[m]$$$ matched the sample, I might have never solved it. XD

    And the total time I spent on the other five questions was even less than 20 minutes. :(

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    function<double(ll)> recur = [&](ll i) -> double
    {
        if (i <= 0)
            return 0.0;
        if (dp1[i] != -1.0)
            return dp1[i];
        dp1[i] = 1.0;

        for (ll j = 1; j <= n; j++)
        {
            dp1[i] += dp[0][j] * (recur(i - j));
        }

       dp1[i]/=(1.0-dp[0][0]);
        return dp1[i];
    };

    This was my code, where dp[0][j] is probability to get j cards from one pack. The statement clearly mentions "atleast X cards".

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

      I think your dp1[i] means the answer of "exactly X Cards", because the transformation looks the same as mine. Did you just output recur(m)? Then the statement was wrong and misleading.

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

        No here is why, basically it stops at the moment it gets atleast X (I'm assuming this is what you mean by M) , and why it works correctly is so in a pack we can get 0 to N cards, the 0 part is handled by the divison part, for 1 to N even if we get some amount of cards such that (i-j)<0 (this handles the atleast part)

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

          I knew why I'm wrong. Because the "1.0". If I consider it as the "exactly X cards", then the "i-j<0" part would not be counted and the sum of the probability would be less than 1. Thx anyway :)

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

problem C ,why can my code get the right answer in some testcases(28/30)?https://atcoder.jp/contests/abc382/submissions/60350177

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

    When you sort the array, you're doing sort(brr, brr+n, cmp) and using n instead of m. If you use vectors instead, you can do sort(brr.begin(), brr.end()), which avoids this risk.

    → Reply
»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I need more problems like E to practice. Anyone knows where to find them?

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

Can anyone please explain how did you get the equation for "fi" in problem E?

I am unable to understand the editorial — https://atcoder.jp/contests/abc382/editorial/11487

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain problem d time complexity??

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am confused of E. I don't understand why f_x can derive from f_x itself. The problem says we should open packs until there are at least x rare cards. This should also express that when we have at least x cards, we should stop. ( I'm extremely bad at probability and expectation.

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

How is 21C9 the maximum number of good sequences in problem D's editorial?

→ Reply