-emli-'s blog

AtCoder Regular Contest 080 / AtCoder Beginner Contest 069

By -emli-, 7 years ago, In English

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.

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

Comments Comments (23)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can I see my " rating changes " after every contest at atcoder ???

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Click to competition history in user profile

    → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hints for Problem E:Young Maids?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think toposort

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to solve it using toposort can you please explain?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it
    spoiler
    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

How to solve Prime Flip?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can almost always find editorials a few minutes after the contest.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Task E is named incorrectly in editorial.

      Just to let you know

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      You are right. But what about discussing problems?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, of course, please discuss problems.

        → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not sure, but I think this is bug you're talking about.

    → Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I really like atcoder, thanks for making it available in english (´・ω・`)

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks to authors for F problem! It is very exquisite solution, I enjoyed not even solving the problem! Thanks)

→ Reply