We will hold AtCoder Beginner Contest 360.
- Contest URL: https://atcoder.jp/contests/abc360
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240630T2100&p1=248
- Duration: 100 minutes
- Writer: MtSaka, Aotsuki, ynymxiaolongbao, sotanishy
- Tester: Nyaan, math957963
- Rated range: ~ 1999
- The point values: 100-200-250-350-450-550-625
We are looking forward to your participation!
Hopefully my rating doesn't rotate 360 degrees in this contest
Why ABC is scheduled on Sunday instead of Saturday?
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.
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.
They are updated late, probably after 1 month ig after the contest.
My scheduled post-contest discussion stream
excited!
Why did this contest comes in Sunday.But ABC361 is on Saturday.
ABC rounds are usually held on Saturdays but this time ARC round was scheduled on Saturday hence this was scheduled on Sunday.
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 ??
Assuming your username in AtCoder is SkyWave2022, you didn't even submit anything for Problem FG. What "solution of F" are you referring to?
That's not my acc.
Try this case. I found my wa*1 solution output 0 0 during the contest.
can you please see my comment below?
My solution passed this case :(
Thank you anyway
Same here
Why the hell my solution to D getting wa in 2 cases doesn't for a positive direction ant starting at X , negative directions ants starting from range X to X+(2 * T) form valid pairs only?
is there $$$O(1)$$$ solution for problem E?
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$$$.
Hi there,
Could you please elaborate on reaching (deriving) the above formula for
a?Thank you.
D not having a single sample with unsorted X was unnecessarily evil IMO.
please see my comment
I was about to submit, luckily went back to confirm this from the constraints!
When will the ratings be updated?
Also wondering. Seems kind of slow this time.
It is very slow.Is seemeds that this contest have some bugs……
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.
Can somebody tell me why am i getting 3wr on F?
https://atcoder.jp/contests/abc360/submissions/55102148
I need solution of problem F please.
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.
Is it unrated？
For G, wouldn't just setting $$$A[0] = 0$$$ and then finding the LIS work? Or am I missing something?
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$$$.
Is it unrated?And why my G is wrong last 3(after_contest).
Who can help me My code
(1) 3, 1 3 3 and (2) 5, 1 2 3 5 4 Expected : (1) --> 3, (2) --> 5 Got : (1) --> 2, (2) --> 4 :)
oh thank you
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.
When will rating update?
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
Ok
Not doing
Why don't I get any rating so far?
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.
If your rating color is $$$C$$$, let $$$l=$$$ the lowest rating of $$$C$$$. Then
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)?
I heard that there is something wrong with Problem B on QQ. Is that true?
Yes. Per https://atcoder.jp/contests/abc360/clarifications
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.
I made sense of the solution given in https://www.cnblogs.com/Lanly/p/18277192. To describe it in English,
basically, one uses the LIS algorithm to compute the LIS the head/tail element of which is index
ifor both prefixes and suffixes. After that, one does coordinate compression on the values and uses a max segment tree to at everyi, find the LIS acrosses all subsequences which end at index at mosti-2and with value<= a[i]-2.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.
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.
When editing an $$$A_i$$$ in an operation, the answer remains the same even if you edit it to $$$0$$$ if $$$i=1$$$ or to $$$A_{i−1}+1$$$ if $$$i\neq 1$$$
Proof:
Suppose the answer is $$$L+1$$$. The narrowly monotonically increasing subsequence of length $$$L+1$$$ of length $$$A$$$ after editing must consist of the LIS of $$$A$$$ before editing and the edited element. Conversely, for all LISs in $$$A$$$, it is sufficient to show that the above restriction does not affect whether a narrow monotonically increasing subsequence of length $$$L+1$$$ consisting of the LIS and the edited element can be created.
Suppose you want to edit the "gap" element of a LIS of length $$$L$$$ to create a narrow monotonically increasing subsequence of length $$$L+1$$$. It's easy to see (although it would be lengthy to prove strictly) that it's okay to impose the above restrictions on the operation in this case.
Solve with a DP that you have as one, the so-called "ear DP".
$$$dp[0][i][j]$$$:= The maximum length of a narrow monotonically increasing subsequence when the value $$$j$$$ is used last, considering the element $$$i$$$ and not yet manipulated
$$$dp[1][i][j]$$$:= The maximum length of the narrowly monotonically increasing subsequence when the value $$$j$$$ is used last, considering the element $$$i$$$ and the operation is already performed
And so on. Implementing this DP in-place (similar to the DP for determining the length of the LIS) solves this problem with a computational complexity of $$$O(N \log N)$$$
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.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
seton 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
giving
3whenis a length
4subsequence.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.
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
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
Why are there some arrow marks near the username in the atcoder website. What does these denote?
How high the user's rating is in their name colors, I guess. Though some tampermonkey scripts had already implemented them before.
In Atcoder, can we do some hacking or uploading after the contest case?
Why hasn't the rating been updated yet?
Nice one
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.
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 :)
How do you know the increment you'll be getting?
search for "ac-predictor" on GreasyFork. You need to install the extension Tampermonkey to use it.
So did they made this round unrated?
No.
Did they make the round unrated?
I believe I registered for rated participation but now it is showing unrated