atcoder_official's blog

By atcoder_official, history, 2 weeks ago, In English

We will hold AtCoder Beginner Contest 360.

We are looking forward to your participation!

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

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

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

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

Why ABC is scheduled on Sunday instead of Saturday?

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

    There's ARC on Saturday.

    Don't know their reason but for me makes sense having the ARC on Saturday instead of doing it right before div1+div2 round on Sunday.

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

    ABC is on Saturday in China......

»
2 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

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

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.

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

    They are updated late, probably after 1 month ig after the contest.

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

excited!

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

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

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

    ABC rounds are usually held on Saturdays but this time ARC round was scheduled on Saturday hence this was scheduled on Sunday.

»
2 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 ??

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    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$$$.

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hi there,

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

      Thank you.

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

    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.

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

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

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    please see my comment

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

    I was about to submit, luckily went back to confirm this from the constraints!

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the ratings be updated?

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

    Also wondering. Seems kind of slow this time.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

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

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

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

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?

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

I need solution of problem F please.

»
2 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

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

    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

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it unrated?

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

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

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

    Let $$$A=[1,2,3,1,5]$$$. If you set $$$A[4] := 4$$$ you get an answer of $$$5$$$.

    But the LIS of $$$A=[0,2,3,1,5]$$$ gives you an answer of $$$4$$$.

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

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

Who can help me My code

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

    (1) 3, 1 3 3 and (2) 5, 1 2 3 5 4 Expected : (1) --> 3, (2) --> 5 Got : (1) --> 2, (2) --> 4 :)

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

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.

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

When will rating update?

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

    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

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

There is no announcement about the rating updation yet!

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

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

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

Ok

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

Not doing

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

Why don't I get any rating so far?

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

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

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why my G is wrong . wa*4

is there any bro could help me?

my code

i've debugged it for a whole afternoon:(

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

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

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

    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.

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

      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.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

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

my code

my new solution

wa*1 :(

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

    (1) 5 $$$\newline$$$ 1 4 3 2 6 $$$\newline$$$ Expected : 4 $$$\newline$$$ Got : 3 $$$\newline$$$ :)

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

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

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

    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

»
2 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why hasn't the rating been updated yet?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice one

»
13 days ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you know the increment you'll be getting?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      search for "ac-predictor" on GreasyFork. You need to install the extension Tampermonkey to use it.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

So did they made this round unrated?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Did they make the round unrated?

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

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

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