Блог пользователя atcoder_official

Автор atcoder_official, история, 4 месяца назад, По-английски

We will hold AtCoder Beginner Contest 360.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +79
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully my rating doesn't rotate 360 degrees in this contest

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why ABC is scheduled on Sunday instead of Saturday?

»
4 месяца назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where can one get the test cases for the AtCoder Beginner Contests? The test cases seem missing after ABC 355 on the Dropbox link they provided on their site.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

excited!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why did this contest comes in Sunday.But ABC361 is on Saturday.

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Problem FG got wrong answer in 4 test cases in total, but none of them got accepted.

Can anyone tell me why my solution of F get wa*3 ??

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

is there $$$O(1)$$$ solution for problem E?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have $$$O(log(k))$$$ (which come from power).

    The formula is $$$\frac{\frac{n(n + 1)}{2}a + (n^2 - 2n)^{k}}{n^{2k}}$$$ where $$$a=\frac{n^{2k} - (n^2 -2n)^{k}}{n}$$$. Actually number of cases, that the black ball end up at position $$$i$$$ is $$$a$$$ if $$$i$$$ is not $$$1$$$. For $$$1$$$, it is $$$a + (n^2 - 2n)^{k}$$$. Since the number of possible cases for doing the operation $$$k$$$ times is $$$n^{2k}$$$, we can get the mentioned value of $$$a$$$.

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Hi there,

      Could you please elaborate on reaching (deriving) the above formula for a?

      Thank you.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I got $$$\mathbb{E}[\text{X}] = \left(1 - \frac{2}{N}\right)^k + \left(1-\left(1 - \frac{2}{N}\right)^k \right)\left(\frac{N+1}{2}\right)$$$

    I first solved for $$$k=1$$$, then for the general case, assume $$$a_{t,k}$$$ be the probability of reaching $$$t$$$ in $$$k$$$ operations, then got the recursion (inspired from calculations of $$$k=1$$$ case) : $$$a_{t,k} = \frac{2}{N^2} + \left(1-\frac{2}{N}\right)(a_{t,k-1})$$$ with initial conditions as $$$a_{t,0} = 0$$$, if $$$t \neq 1$$$; $$$a_{t,0} = 1$$$ else.

    Now, writing the expression of the expectation and the probability derived from above, remains long amounts of simplifications T_T.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why my solution for problem b is getting wrong. Any test cases

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

D not having a single sample with unsorted X was unnecessarily evil IMO.

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

When will the ratings be updated?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Also wondering. Seems kind of slow this time.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It is very slow.Is seemeds that this contest have some bugs……

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Apparently they are discussing what to do with the fact that Problem B is set wrongly. I don't get how this takes so much time though, or maybe I'm just being karen. Anyways, I acknowledge their efforts but there's nothing we can do but wait.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody tell me why am i getting 3wr on F?

https://atcoder.jp/contests/abc360/submissions/55102148

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ok, I figured D is reduced to finding the number of intersecting interval pairs. Then I tried to sweep maintaining the current number of open intervals (+1 at a start, -1 at an end+1), but how do I make sure I don't over-count the same interval pair?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I need solution of problem F please.

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

When will the ratings be updated?

Edit: Damn, I'm not used to waiting for Atcoder rating change updates. It feels like forever, even though it's only been 2 days.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you go on clarification tab they have said it will take few days for rating to be updated as they have provided wrong constraints on problem B due to which many participants were getting wrong answer.so they are looking into it

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Is it unrated?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For G, wouldn't just setting $$$A[0] = 0$$$ and then finding the LIS work? Or am I missing something?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it unrated?And why my G is wrong last 3(after_contest).

Who can help me My code

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I would like to share my ideas about problem F. At first, note that the original integers don't matter, and for each segment, we only care about at most six integers, l-1,l,l+1,r-1,r,r+1. Thus, we could compress them and use at most 6n integers (after compression). Then, we fix the left point, and try to find the right point which gives us the maximum value. For a fixed left point denoted as 'low', all the segments with [l, r] can be divided into three cases, which are,

Case1: l < low. It contributes 1 to the final value, if and only if the right point, denoted as 'high', satisfies high > r, and thus we can use a segment tree to add 1s to [r + 1, 6n]

Case2: l == low. It contributes nothing, but we should update after we set low++

Case3: l > low. It contributes 1 to the final value, if and only if high belongs to [l + 1, r — 1], and thus we can use the segment tree again to add 1s to [l + 1, r — 1].

Be careful that, the zero point, 0, must be added after compression.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will rating update?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    If you go on clarification tab they have said it will take few days for rating to be updated as they have provided wrong constraints on problem B due to which many participants were getting wrong answer

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There is no announcement about the rating updation yet!

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    According to the clarification, rating updation will be delayed due to B's incorrect problem statement.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ok

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Not doing

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why don't I get any rating so far?

»
4 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I am not sure if this is the right place to ask. After a simple google search I was not able to find anything. After the contest my rating hasn't changed (I'm not sure if it has for others but I assume it has since atcoder usually updates ratings quite fast.)

Next to my rating I have received a ^ sign. Here is the link to my profile. I have no idea what it means.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    If your rating color is $$$C$$$, let $$$l=$$$ the lowest rating of $$$C$$$. Then

    • If your rating is in $$$[l+0,l+99]$$$, you have $$$1$$$ Λ.
    • If your rating is in $$$[l+100,l+199]$$$, you have $$$2$$$ Λs.
    • If your rating is in $$$[l+200,l+299]$$$, you have $$$3$$$ Λs.
    • If your rating is in $$$[l+300,l+399]$$$, you have $$$4$$$ Λs.

    off-topic 1: I want a similar feature on CF too. Especially red, $$$[2400,2999]$$$ have the same visual and I want to distinguish them in one look on the standings.
    off-topic 2: How to represent the mark? ^(XOR), ∧(logical and), or Λ(Large lambda)?

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

why my G is wrong . wa*4

is there any bro could help me?

my code

i've debugged it for a whole afternoon:(

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I heard that there is something wrong with Problem B on QQ. Is that true?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes. Per https://atcoder.jp/contests/abc360/clarifications

    There was a mistake in the constraints. We have already fixed the statement. It was written as |T| < |S| but the correct constraints is |T| <= |S|.

    Also, a detailed explanation of solution of G would be much appreciated. There is a Japanese language editorial with two different solutions, but the machine translation of it does not satisfy me.

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I made sense of the solution given in https://www.cnblogs.com/Lanly/p/18277192. To describe it in English,

      Spoiler

      Per https://atcoder.jp/contests/abc360/submissions/55149393, I have gotten AC, though before that, I had a bug that failed two after contest cases (I wonder who submitted them, and what percent of "correct" solutions during the contest actually failed them).

      Also, I would still much appreciate English translation and/or further explanation of the Japanese editorial, which is difficult for me to understand in its machine translate.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Turns out when I machine translate it paragraph by paragraph using Bing Translator on mobile (as opposed to Google Translate on desktop), there is a high quality translation. So inside the spoiler its the English translation of the first solution in editorial.


        Spoiler

        The second solution seems to be the same as that which I described in the above comment.

        Last by not least, my implementation of the first solution, https://atcoder.jp/contests/abc360/submissions/55159358, still fails the last after contest test case, which is a large one that runs in 232 ms. It would be great if someone could reply with identification of the bug.

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          The bug is actually that I did not check if the value to set is greater than or equal to the one already there when calling set on the segment tree for the pending updates.

          What's interesting is the submission of mine that AC'ed, which was per the second solution in the editorial, actually had a fair share of in retrospect glaring bugs not caught even by the after contest tests. For instance, https://atcoder.jp/contests/abc360/submissions/55149393 fails on

          10
          5 7 10 2 8 2 8 7 1 3
          

          giving 3 when

          '5' '7' 10 2 '8' "9" 8 7 1 3
          

          is a length 4 subsequence.

          I propose to add this as another after contest test. Speaking of which, it would be great if the authors of the after contest tests already there could private message me; I do not know thru what channel after contest tests are typically submitted.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my code

my new solution

wa*1 :(

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

G is a nice problem for me.

After reading jp editorial, I decide to implement method 1.

after a long time of debugging, it seems that there's only 2 testcases that I can not pass. (which are also added after the contest)

I wonder what kind of testcases it is and also wonder what's the bug of my code

here's my submission link

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I found the bug.

    the main problem is that when starting with dp0[0] dp1[0], the corner case was not handled correctly, so I directly calculate dp value when n = 1, then start loop with i = 2.

    here's my ac sumbission. link

»
4 месяца назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Why are there some arrow marks near the username in the atcoder website. What does these denote?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How high the user's rating is in their name colors, I guess. Though some tampermonkey scripts had already implemented them before.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Atcoder, can we do some hacking or uploading after the contest case?

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why hasn't the rating been updated yet?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice one

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

The tests for G seem to be weak. For example this submission seems to get accepted on all tests even though it fails on this:

a = [1,3,4,2,2,4,5] the answer here is 5 but the output is 4.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Honestly, I think the mistake of problem B isn't that serious to make the whole round unrated. Wish I can get my +97 rating :)

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So did they made this round unrated?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My G got wrong answer but I couldn't find an example to debug it.

Is there any bro could help me?

https://atcoder.jp/contests/abc360/submissions/55205166

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did they make the round unrated?

I believe I registered for rated participation but now it is showing unrated

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can problem D be solved using a method similar to the reverse order pair?