We will hold AtCoder Regular Contest 184.
- Contest URL: https://atcoder.jp/contests/arc184
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240922T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 5
- Writer: Aus21, physics0523
- Tester: Nyaan, maspy
- Rated range: 1200 ~ 2799
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!
As a writer who competed in WF, I'll give a goodbye gift for you.
Only 5 problems? Will ARC in future only has 5 problems too?
This is my first time creating ARC problems, and I hope you enjoy participating in the contest.
why cant < 1200 rated people register as a rated participant?
i get it now :)
yep i opened the first problem and got stunlocked ;-;
The $$$900-1000-1000$$$ seems a bit tough, but anyway hope I can solve 3.
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
ya a bit annoying
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.
so true
This should be rated for all, looking at the number of submissions on each tasks, I once thought this was actually an AGC.
Too hard.
An AGC round with an ARC's problem A.
Tooo hard
I think this round is harder than some AGC rounds.
*Too weird, look at the problems
I think the interactive problem(problem A) is good.
Well, I was talking about problem C (and possibly B)
What even is this....
misunderstood A
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.
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)$$$.
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.
Assigning them equal points and adopting the Codeforces rules may be reasonable.
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).
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.
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
In fact, number 35 belongs to neither the subproblem of 5 nor the subproblem of 7, it belongs to the subproblem of 35.
Some problems seem quite CNOI. B is somehow very typical. Dunno if it has something to do with the changing of admin.
Is it just me or are some of the solution links in the editorial broken.
hello, i am sorry to tell you that the official editoral on problem B's sample implementation is 404
The previous version of my editorial was used for translation. I updated the link just now, and it should be available.
Problem D editorial submission is still unavailable
Oh I'm so sorry. I also updated the link of D now.
no problem, thanks!
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.
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!