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.

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

sugim48 thanks for problems,I liked it, especially Grid Coloring that I solved with dfs.

How to solve Young Maids?

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::pair`

compiled 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 (´・ω・`)

I found a bug in my problem C after submitting and getting an AC.

I wanted to re-submit my program after fixing the bug to make sure the new program still passed tests, but I was worried that would reduce my score.

Can someone clarify if re-submit after AC could reduce your score? Thanks!

I don't believe it reduces your score after the contest is over. I resubmit the corrected code after almost every contest.

Thanks but I meant DURING the contest. (Yes I should have been working on the next problem but I was curious anyway!)

This should answer your question. It is from the AtCoder contest page. "When you solve a problem, you get a score assigned to it. Competitors are ranked first by total scores, then by penalties. The penalties are computed as (the time you spend to get your current score) + (5 minutes) * (the number of incorrect attempts). "

I see now. Thanks!

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)

In the AtCoder Beginner contest69, in the question C.4-adjacent

The testcase :

5 2 2 2 2 1

would fail if the below-mentioned code is used :

Still, many people have got the problem right, even after using this code. What am I missing ?! Or this the case of weak test cases?

Look my solution. It easy to understand.

The answer that comes out of your algo is correct for the given test case ( 5 2 2 2 2 1 ) i.e "No". But the code that I mentioned was submitted by many people and the answer comes out to be "Yes" for the above mentioned test case. Still I believe because of weak testcases, it was granted as accepted or perhaps I did not understand the question completely. However, I too did get an AC with my code, which produces "No" as an answer.

Whichever way, the above test case produces a different answer for my code and some other peoples code, still, all of us got AC!! Which means the given test case was missing.