Two contests AtCoder Regular Contest 080 and AtCoder Beginner Contest 069 will be held at the same time.
You can participate in whichever contest you want. (However, you can't register to both competitions.) The last two tasks in ABC are the same as the first two tasks in ARC.
ABC is significantly easier than Div2 contest in TopCoder or Codeforces. If you can enjoy Div2 contests in TC or CF, I recommend you to participate in ARC.
Time: August 6th (Sunday), 21:00 JST
・Duration: 100 minutes
・Number of Tasks: 4
・Writer: sugim48
・Rating： ARC is rated for those who have rating < 2800. ABC is rated for those who have rating < 1200. (However, note that current rating is much lower than your actual strength — if you are green or brown, I recommend you to choose ARC.)
The point values will be announced later.
We are looking forward to your participation!
Let's discuss after the contest.
UPD:
The point values are announced.
It is 100 — 200 — 400 — 400 — 800 — 1200.
Where can I see my " rating changes " after every contest at atcoder ???
Click to competition history in user profile
Hints for Problem E:Young Maids?
I think toposort
How to solve it using toposort can you please explain?
My idea is to fix the last pair which divides the aray into three parts. which we can assume as subtrees of that pair and then recurse that and find tree. For finding pair we use rmq.Now the answer will smallest lexicographical toposort of that tree assuming edges point downwards.
PS: I think idea is correct but still untested
Yes, it works. I have the same solution link
Try to determine first two numbers in the answer. (Not first two pushed, but two in the real answer)
Try to understand which pair can serve as second in the answer. This might lead to the solution.
Proper Bracket Expression
think of the process in reverse , we must choose 2 indices first such that left one is odd and right one is even and split the range into 3 parts such that pairs now can not go from one part to another , this can be done with priority queue and segtree.
I didn't manage to get AC during contest, so this might be wrong:
For the first position in permutation q, it's obvious that you can put any number that is in an odd position in p. For the second position, you can put any number in an even position to the right of the first one.
If you do this, you break the problem in (at most) three others (to the left of the first, between the first and the second and to the right of the second). You can solve this recursively and then merge the three answers. Finding the first two can be done using RMQ.
I tested locally for extreme cases and it works fast, but I received TLE during contest, though.
I done it with set and segment tree https://pastebin.com/HYb6f0DV
You have some intervals, everytime choose smallest element at odd position in some interval and than smallest even element at right side of the same interval. After it current interval split in three new intervals (and add their minimums on odd postion in set)...
To process everything fast you should save information about erased elements in another set and also you should have segment tree with min at even/odd postions.
Fine tasks, a little big gap between first two and rest, but I like it :)
How to solve Prime Flip?
You can almost always find editorials a few minutes after the contest.
Task E is named incorrectly in editorial.
Just to let you know
You are right. But what about discussing problems?
Yes, of course, please discuss problems.
Achievement unlocked: work around compiler bugs during a contest!
I submitted for C but got mysterious CE, but the same code with a custom substitute for
std::paircompiled normally. I asked the organizers and they also think this is likely a compiler bug. Perhaps I should send a bug report, if I get it right?I am not sure, but I think this is bug you're talking about.
Yes, exactly :) Thanks for the info.
I really like atcoder, thanks for making it available in english (´・ω・`)
In editorial for problem F is a statement: (Strictly speaking, this is related to distribution of primes, for example we have to prove that arbitrary even number can be a difference of two primes. We confirmed this up to the constraints of the problem experimentally.)
Does it mean that authors got a pair of primes with difference X, for each even X up to 10^7?
I thought that for some X's, primes in such pair should be very big.
Edited: OK, I understand, they shouldn't.
Thanks to authors for F problem! It is very exquisite solution, I enjoyed not even solving the problem! Thanks)