### maroonrk's blog

By maroonrk, history, 3 weeks ago,

We will hold AtCoder Regular Contest 139.

The point values will be 300-500-700-700-800-1000.

We are looking forward to your participation!

• +74

 » 3 weeks ago, # |   +3 Let's go in 10 minutes.700 for C and D (o_O)
 » 3 weeks ago, # |   +1 good luck guys
 » 3 weeks ago, # |   0 good luck！
 » 3 weeks ago, # |   -43 I think B in this contest is really hard.Who can give me some advice?Thanks.(I'm unrated.)
•  » » 3 weeks ago, # ^ |   -38 greedy(((
•  » » » 3 weeks ago, # ^ |   -33 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?
•  » » » » 3 weeks ago, # ^ |   +49 Hey bros, contest is still running now.
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   -26 e
•  » » 3 weeks ago, # ^ |   +36 Hey bros, contest is still running now.Although you're unrated, there are some guys which are rated will look into this comment.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   -21 e
•  » » 3 weeks ago, # ^ |   0 greedy . Maybe three points. https://atcoder.jp/contests/arc139/submissions/31243156Set a threshold, and then consider that it must be B,C is the best, and then 1 completes N.
•  » » 3 weeks ago, # ^ |   0 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
 » 3 weeks ago, # |   +33 What a Div.0 round!
•  » » 3 weeks ago, # ^ |   +20 really :(
 » 3 weeks ago, # |   +66 This round is toooooo hard!!!!!!!!!!I really miss the old days when ARC's hard problems are not always modulo $998244353$ problems!
•  » » 3 weeks ago, # ^ |   +108 This round is harder than early AGC rounds...
•  » » » 3 weeks ago, # ^ |   +26 Judging by this ARC and the last one, I really don't know why ARCs are not rated for reds...
 » 3 weeks ago, # |   +1 damn this contest is crazy hard, compared to the other regular contest
 » 3 weeks ago, # |   -78 Why do I find D easier than C?
•  » » 3 weeks ago, # ^ |   +76 Why your atcoder account has been banned?Did you copy others code frequently?
•  » » » 3 weeks ago, # ^ |   0 I used to,and I'm very sorry for that.I'm considering to delete this codeforces account.
 » 3 weeks ago, # | ← Rev. 2 →   +15 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.
•  » » 3 weeks ago, # ^ |   0 idk how but straightforward bfs from (1,1) passes.just check if current pair (x,y) breaks condition if not include it
•  » » » 2 weeks ago, # ^ |   0 So beautiful solution!
 » 3 weeks ago, # |   0 Does anyone have a strong testcase for B?
 » 3 weeks ago, # |   0 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://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.
 » 3 weeks ago, # |   0 anyone pls explain the logic of this submission , task A . https://atcoder.jp/contests/arc139/submissions/31236419
•  » » 3 weeks ago, # ^ |   +16 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$.
•  » » » 3 weeks ago, # ^ |   0 thanks understood <3
 » 3 weeks ago, # |   0 Im not sure if I understand the editorial of B, can anyone explain please?
•  » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   +9 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.
 » 3 weeks ago, # |   0 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
 » 3 weeks ago, # |   0 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⌋
 » 3 weeks ago, # |   +16 By the way, when will the English editorial of ABC249 be released?
 » 3 weeks ago, # | ← Rev. 2 →   0 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?
 » 2 weeks ago, # |   0 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