atcoder_official's blog

AtCoder Regular Contest 184 Announcement
By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Regular Contest 184.

The point values will be 600-700-900-1000-1000.

This is the first ARC after the change of admin. (See details)

  • The criteria for scoring have been revised.
  • The difficulty of the later problems is lower than before.

However, due to special circumstances, the difficulty of the earlier problems has significantly increased compared to the standard difficulty target for ARC under the new admin. In the future, the earlier problems in ARC are expected to be easier than this one.

Given the even distribution of difficulty, we recommend reading all problems rather than focusing solely on solving them in order.

We are looking forward to your participation!

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

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

As a writer who competed in WF, I'll give a goodbye gift for you.

→ Reply
»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Only 5 problems? Will ARC in future only has 5 problems too?

→ Reply
»
2 months ago, # |
  Vote: I like it +51 Vote: I do not like it

This is my first time creating ARC problems, and I hope you enjoy participating in the contest.

→ Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

why cant < 1200 rated people register as a rated participant?

→ Reply
»
2 months ago, # |
  Vote: I like it +26 Vote: I do not like it

The $$$900-1000-1000$$$ seems a bit tough, but anyway hope I can solve 3.

→ Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it -76 Vote: I do not like it

people rated $$$<$$$ $$$1200$$$ can't register rated in ARC , why this decision and why no announcement?

UPD : Sorry I actually didn't know that announcement was made before but I still wanna know the reason for raising the lower-bound

→ Reply
»
2 months ago, # |
  Vote: I like it -87 Vote: I do not like it

interactive = garbage

Also, it's not even possible to debug what is wrong with the solution, since triggered asserts are considered WA instead of RE.

→ Reply
»
2 months ago, # |
  Vote: I like it -26 Vote: I do not like it

This should be rated for all, looking at the number of submissions on each tasks, I once thought this was actually an AGC.

→ Reply
»
2 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Too hard.

→ Reply
»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

An AGC round with an ARC's problem A.

→ Reply
»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Tooo hard

→ Reply
»
2 months ago, # |
  Vote: I like it -113 Vote: I do not like it

This maybe the worst ARC I've ever participated. The first problem is interactive problem.And the second one is a strange math problem. It maybe great for the grands,not for me.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Other solution for C: Let mountain curves be 1,then for point x,the value is (x/(lowbit(x)*2))%2.Use this to solve in $$$O(n^2loga)$$$.

→ Reply
»
2 months ago, # |
  Vote: I like it +55 Vote: I do not like it

Problems are all very good but putting them together in a single contest is a bit weird. Basically B,C,D (and possibly even E) are of similar difficulties, and many people are getting random points based on which particular type of problem they are more familiar with.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Assigning them equal points and adopting the Codeforces rules may be reasonable.

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

    I think atcoder should have more testers like codeforces, and they should cover most of the rating levels, in this way the difficulty will be more balanced.

    I guess the two testers (one IGM and one LGM) solve at least ABCD so they don't realize that B,C,D are almost the same level (and what's more, I think D<B).

    → Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I would possibly solve 4(ACDE) or even all of the problems if the contest was 5h long, but sadly after I solved AD, there is no time for me to solve more.

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i am wonder in problem B , the Editorial say we can divide the problem into sub-problems for each multiset of prime factors other than 2 and 3. But look at 35,we needn't not only let 5 build it ans let 7 build it ,it was build twice！ Is it the minest cost way to build 1->n

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

    In fact, number 35 belongs to neither the subproblem of 5 nor the subproblem of 7, it belongs to the subproblem of 35.

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Some problems seem quite CNOI. B is somehow very typical. Dunno if it has something to do with the changing of admin.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it just me or are some of the solution links in the editorial broken.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hello, i am sorry to tell you that the official editoral on problem B's sample implementation is 404

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

    The previous version of my editorial was used for translation. I updated the link just now, and it should be available.

    → Reply
»
2 months ago, # |
  Vote: I like it +33 Vote: I do not like it

I have a solution to problem A that uses only 910 queries.

First divide up the coins into as many odd-sized groups of 11+ as possible. In practice we can make 90 groups (89 groups of size 11 and 1 group of size 21 for example, but any arrangement into 90 groups of odd sizes is fine).

For each group, compare coins inside the group. Each group will either be all equal (in which case all coins are real) or they will split into two unequal parts. This takes $$$\text{group size} - 1$$$ queries per group, so in total this is $$$1000 - 90 = 910$$$ queries.

Now we need to handle the split groups. One easy way to finish is that we can take any real coin and compare to one coin each from the (at most 10) split groups. This gets us to 920 queries.

But we actually don't need to do that at all! I claim that once we end up with our split groups, there is only one unique way to choose one part from each group to get a total of exactly 10 coins.

Proof: let's assume for contradiction that there are two different ways to choose the parts to get a total of 10 coins. Let's look at only the groups where we chose different parts. Since each group size is odd, by parity there must be an even number of these groups, so at least 2. But then the total number of coins in those groups is at least 2 * 11 = 22, which means the two choices contain more than 20 coins in total, giving us a contradiction.

→ Reply
»
6 weeks ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I was trying to upsolve B, and was reading the editorial. I understand the part that you need to sum over $$$T(u)$$$ for all $$$u$$$ not divisible by $$$2$$$ or $$$3$$$.

I'm a bit stuck on how to compute $$$T(u)$$$. I understand the DP states, but don't quite get how to do it with fast zeta transform. (if my understanding is correct, I think fast zeta should generally be similar to SOS dp? according to this blog https://codeforces.me/blog/entry/72488 . I've done SOS DP a few times but I am not very strong :( so correct me if I'm wrong).

How does the DP work exactly? I was taking a look at tourist's solution https://atcoder.jp/contests/arc184/submissions/58027288 which doesn't seem super long, but would be useful to have some kind of high-level algorithmic explanation of what's going on there. Thanks!

→ Reply