We will hold AtCoder Regular Contest 139.
- Contest URL: https://atcoder.jp/contests/arc139
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220424T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: PCTprobability, Nyaan
- Tester: maspy
- Rated range: — 2799
The point values will be 300-500-700-700-800-1000.
We are looking forward to your participation!
Let's go in 10 minutes.
700 for C and D (o_O)
good luck guys
good luck！
I think B in this contest is really hard.Who can give me some advice?Thanks.(I'm unrated.)
sorry
Mr. Dragon,I know it is so easy for you to solve this problem .Although I tried my best to solve it by this way,I still have no idea .So can you tell me more advice?
Hey bros, contest is still running now.
e
Hey bros, contest is still running now.
Although you're unrated, there are some guys which are rated will look into this comment.
e
The Chinese CPers' jargon words in his comment(Rev. 1):
konjac=蒟蒻(jǔruò), pronounced similarly to 巨弱(jùruò), a informal word to represent the fact that CP is someone's weak point.
a province or a school is weak means students, teachers or instructional resources in it are not good.
big guy=大佬=someone good at CP.
Chinese CPers tend to be modest, so his words may be fake.
greedy . Maybe three points. https://atcoder.jp/contests/arc139/submissions/31243156
Set a threshold, and then consider that it must be B,C is the best, and then 1 completes N.
I just solved it using square root decomposition, so if either A or B is greater than $$$\sqrt{N}$$$ than there are only $$$O(\sqrt{N})$$$ cases to consider, and if they are both less than that, then there are only $$$O(\sqrt{N})$$$ possible remainders that can arise from dividing with A or B. I think I overcomplicated it lol
What a Div.0 round!
really :(
This round is toooooo hard!!!!!!!!!!
I really miss the old days when ARC's hard problems are not always modulo $$$998244353$$$ problems!
This round is harder than early AGC rounds...
Judging by this ARC and the last one, I really don't know why ARCs are not rated for reds...
damn this contest is crazy hard, compared to the other regular contest
Deleted.
Why your atcoder account has been banned?
Did you copy others code frequently?
I used to,and I'm very sorry for that.
I'm considering to delete this codeforces account.
Problem C was a nice problem. I solved it considering the function $$$f : A \mapsto B$$$, where $$$A = x + 3y$$$ and $$$B = 3x + y$$$, have to be an injective function and using the fact that $$$x = \frac{3B - A}{8}$$$ and $$$y = \frac{3A -B}{8}$$$, we can solve the problem pretty straightforwardly.
idk how but straightforward bfs from (1,1) passes.
just check if current pair (x,y) breaks condition if not include it
So beautiful solution!
Does anyone have a strong testcase for B?
I think I am very lucky to solve problem B. I didn't come up with the arguments mentioned in the tutorials, but I just guessed that it is sufficient to find out the correct answer if we implement the following two loops.
At first, we use ny to denote the number of operation "increase P by A", Then, Loop 1, we check ny from 0 to 1e6. Loop 2, we start from (n/a) to (n/a-1e6). In each loop, we could compute the number of the other two operations, and thus we could update the answer.
I got the above "guess", since recently when I was trying to solve this problem, https://mirror.codeforces.com/contest/466/problem/B, I realize there may exist a general pattern. In this pattern, at first sight, we have to do bruteforce from 1 to 1e9, but with some observation, it is enough to reduce it to two independent loops, one from 1 to 1e6, and the other from 1e9 to 1e9-1e6. I am sorry that this is not a strict and precise description of this pattern, because I really don't know how to give it a clear statement, but you may find it out by yourself if you take a look at the problem of the above link.
anyone pls explain the logic of this submission , task A . https://atcoder.jp/contests/arc139/submissions/31236419
Think the problem in a greedy way. We should make each $$$a_i(1\le i\le n)$$$ as small as it can be.
Then Absolutely, $$$a_1=2^{t_1}$$$.Let $$$b_i=a_i\div 2^{t_i}$$$.
Because $$$a_i>a_{i-1}(2\le i\le n)$$$, the smallest $$$b_i=\lfloor\dfrac{a_{i-1}}{2^{t_i}}\rfloor+1$$$.
As $$$\operatorname{ctz}(a_i)=t_i$$$, $$$b_i$$$ should always be odd.If $$$b_i$$$ is an even number, then do $$$b_i\leftarrow b_i+1$$$.
Im not sure if I understand the editorial of B, can anyone explain please?
First of all, consider the price/performance ratio, and sort it according to the price/performance ratio. Definitely, the higher price/performance ratio will be preferred, but there will be a problem, that is, when choosing the higher price/performance ratio, it takes up the space of the second price/performance ratio, making the choice of the second price/performance ratio and the third price/performance ratio not optimal. At this time, you can imagine that this deviation will not be very big, or even a three-point function? Then you can pass this question by setting a threshold.
B can be solved in $$$O(log^2)$$$, if we solve the subproblem: Find the minimum $$$x(l\leq Ax\%B\leq r)$$$ in $$$O(log)$$$ time. The subproblem once appeared in arc127f.
how to solve E,I cannot understand the Editorial of problem E.
if H is odd,why it can reach the upperbound for L $$$(H \times \frac{W-1}{2})$$$
Hope someone can give an example
In editorial of B, how did the we get this conclusion: "Thus, we can solve the problem by trying all possible numbers of uses of the operation “increase P by A” if ⌊N/A⌋<A−1, and those of the operation “increase P by B” otherwise"
I am getting this condition: try all x such that (N-A*x)/B <= A-1; x < N/A. This gives time complexity of : O(N/A)
By the way, when will the English editorial of ABC249 be released?
PCTprobability Kodaman
Could anyone explain how we would go about implementing B? Reading the editorial i got the fact that number of operations for A would be less than equal to floor(N/A) whereas those of B would be less than A-1. But how would one one implement in O(sqrt(N)) time?
Can anyone tell me in problem B, how the person who has submitted this code made an assumption on line 52 that iteration will less than 100000 times