### maroonrk's blog

By maroonrk, history, 8 months ago,

We will hold AtCoder Regular Contest 144.

The point values will be 300-400-600-700-800-900.

We are looking forward to your participation!

• +83

 » 8 months ago, # |   -25 YEAR！
 » 8 months ago, # |   +7 Thanks for the contest. I liked problem C. Also, the problem statement of problem A was a little bit confusing for me.
•  » » 8 months ago, # ^ |   0 problem C and D is pretty great ! High quality problems.
 » 8 months ago, # |   +9 Is there a way to solve C using something similar to Hall's marriage theorem?
•  » » 8 months ago, # ^ |   +6 The base idea using Hall was that I would have two sets: elements and positions; both intervals [1;N]. I am trying to find a perfect matching between elements and positions. Not any matching, the smallest lexicographically one. For each [l;r] in positions, it must be that the number of incoming edges to this interval must be >= number of unused elements in [l;r]. That is, having a incoming([l;r]) >= unused([l;r]), what is equiv. to incoming([l;r]) - unused([l;r]) >= 0. This reduces to checking if there is any position i smaller than 0, what can be done using a Segtree. A value i contributes with -1 to seg[i] and with 1 to seg[0:i-k] and seg[i+k;n-1].I would then put the smallest element in each iteration that doesn't violate this condition. That is, when trying to figure the element at position i, check if it is still feasible for [i+1;n-1] if I remove the i-th element from the structure (add 1 to seg[i] and remove 1 from seg[0:i-k] and seg[i+k;n-1]).The first problem is that Hall's isn't enough for "testing if it is feasible simulating adding x". It could be that all positions that a still unused element x could use are filled up and thus x has no out edges to [i+1;n]. Hall's worries only about saturating elements that have out edges. Thus, I would need another structure to check if I've left an element unmatched (probably another Segtree).The second problem is checking what's the minimum element is efficiently. I depends on the first problem. I guess that if all elements can reach at least two positions and that the minimum element in seg[i] is >= 1, I can just take the smallest available element. But this is already too tricky.
•  » » 8 months ago, # ^ |   0 Yes, there is :D https://atcoder.jp/contests/arc144/submissions/33347474
 » 8 months ago, # |   +13 Can anyone explain the solution of E? I can't understand why if you solve the decision problem, you can solve the original problem easily.
•  » » 8 months ago, # ^ |   +15 I was also confused about it. After thinking for a long time, I finally got it, so I'll try to explain my understanding here.As the editorial read, the decision problem has been reduced to the following: You are given some pieces of information in the form $P_v \equiv P_w + c \pmod x$. Determine whether one can set a sequence of potentials $(P_v)_v$ without contradicting them. We can easily solve it with weighted union-find or just by DFS, so the only problem we need to consider is that $x$ is not fixed in the original problem.Considering the process solving the decision problem, one can find that we only need to check if $a \equiv b \pmod x$ is true for a few pairs $(a,b)$, where both $a$ and $b$ are constants we can calculate. And we can simply do the same: the answer is just the GCD of $|a-b|$ among all of these pairs. Since the final answer will always satisfy all of these equations, we don't need to modulo anything by the current answer. And if all such pairs satisfy $a=b$, the answer is obviously $-1$.For more details, you can read some solutions for this problem, for example, the writer's submission.
•  » » » 8 months ago, # ^ |   0 Thank you very much! After trying several small cases I finally understood it.
 » 8 months ago, # |   -10 As a fan of ARC, I sadly feel it is going downhill. Neither the depth and breadth can't catch up with computer scientific research, and even other contests like opencup. That sounds sad, but that's what I feel more and more deeply everytime participating. Missing the good days, spending with the old good arc.
•  » » 8 months ago, # ^ |   -10 More explanation: I always feel I have seen the problems at the past. But things were not like that, at arc 126-130, there was full of adhoc problems. As a comparison, I love AGC very much. I know it's hard to create good problems, that's why I feel sad about arc these days.
•  » » » 8 months ago, # ^ |   -7 How is AGC not full of adhoc
•  » » 8 months ago, # ^ |   +29 That's because you got stronger.
 » 8 months ago, # |   0 One the one hand, time on the toilet really does help you think through problems. On the other, there's a such thing as too much of a good thing... thankfully, I chose unrated. Take care of your health, kids!
 » 8 months ago, # | ← Rev. 2 →   0 How to approach C? Can someone explain their approach.
 » 8 months ago, # | ← Rev. 3 →   +20 Thanks to the strong tests, I was so close to 2000 points.(It is really hard for me to think of treating these $K$ s in a special way.)
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Same, wasted 30min and 6 penalties on it :)
 » 8 months ago, # | ← Rev. 2 →   0 Alternative solution for problem D: Fix $c$ and the amount $p$ of $x_i \geq 0$ (defined as in the beginning of [3] in the editorial). Find the number of ways to choose the $x_i \geq 0$ and the $x_i < 0$ with stars and bars. Get the formula in [4] (method 2), with a double counting (identity (9) here). Implementation
 » 8 months ago, # |   0 After reading editorial of problem D, although I still not quite understand part [4], I get really shocked, that, it needs so many observation and mathematics. Really a complicated problem! By the way, is there any different approach that someone would like to share or talk about?
 » 8 months ago, # |   0 Can anyone help me in getting the solution of A of AtCoder Regular Contest 144. I have studied the editorial but wasnt able to understand??
•  » » 8 months ago, # ^ |   0 Consider digit 1 to digit 9. When we multiply 2 to each digit, they become: 1 -> 2 2 -> 4 3 -> 6 4 -> 8 5 -> 10 6 -> 12 7 -> 14 8 -> 16 9 -> 18 Comparing the sum of digits, SOD(), of x and 2x: SOD(1) = 1 -> SOD(2) = 2 SOD(2) = 2 -> SOD(4) = 4 SOD(3) = 3 -> SOD(6) = 6 SOD(4) = 4 -> SOD(8) = 8 SOD(5) = 5 -> SOD(10) = 1 SOD(6) = 6 -> SOD(12) = 3 SOD(7) = 7 -> SOD(14) = 5 SOD(8) = 8 -> SOD(16) = 7 SOD(9) = 9 -> SOD(18) = 9 The best "gain" is the 4th row, where the input is 4 and the output is 8. So, we should try to pack as many 4s as we can.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 I have understood a little but can you please send me the answer because being a beginner i am finding hard to code the concept that you have told.llc5pg Also thanks a lot.
 » 8 months ago, # |   0 For part [4] of the editorial of problem D, I think I have come up with a little bit different approach.As method-1 says, we are going to compute the sum of $(1+K-\sum x_i)$ overall $(x_1,x_2,..,x_n)$ with $\sum x_i \le K$. If we write $\sum x_i = S$, where $S=1,2,...,K$, then we should compute $T=\sum_{S=1}^{S=K}(1+K-S) \times C_{S-1}^{n-1}$, where $C_{S-1}^{n-1}=\frac{(S-1)!}{(n-1)!(n-S)!}$ means the number of ways to choose $x_1,x_2,..,x_n$ under the constraint of $\sum x_i = S$.Note that $C_{S-1}^{n-1}=0$ for $S  » 8 months ago, # | +1 I was so close to D!I just found that if$f(x)$for$x\le 2 ^ i$is fixed, then$f(x+2^{i+1})$could be written as$f(2^{i+1})+f(x)-f(0)$.If I had expended this fomula a little bit, I could have found the key observation that$f(x)=f(0)+\sum_{i\in x}(f(2^i)-f(0))\$, but I turned to think of DP instead.Anyway, this is a great problem. I enjoyed it and learned a lot!
 » 8 months ago, # |   0 Who can please teach me how to solve problem C ? I can't understand the Editorial. Thanks a lot!!!
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 []
•  » » » 8 months ago, # ^ |   0 This is under ARC, not ABC.
•  » » » » 8 months ago, # ^ |   0 yeah，I asked how to solve ARC problem C
 » 8 months ago, # |   0 Can anyone help me with problem b, I read the editorial but could not understand the solution
•  » » 8 months ago, # ^ | ← Rev. 2 →   +4 []
•  » » » 8 months ago, # ^ |   +3 Wrong contest.
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 Hint 1For a given value of x, can you check if you can make the lowest element of array greater than or equal to x using the given operation ?Here is a checker function. Spoilerbool check(vector &arr,int x,int a,int b){ int n = arr.size(); int hh=0; for(int i=0;ix){ hh -= (y-x)/b; } else{ hh += (x-y)/a; if((x-y)%a != 0){ hh++; } } } if(hh<=0) return true; else return false; } ` Hint 2Use Binary Search using the checker function given above.