maroonrk's blog

AtCoder Regular Contest 144 Announcement
By maroonrk, history, 2 years ago, In English

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!

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

Comments Comments (29)
| Write comment?
»
2 years ago, # |
  Vote: I like it -25 Vote: I do not like it

YEAR！

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

Thanks for the contest. I liked problem C. Also, the problem statement of problem A was a little bit confusing for me.

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

    problem C and D is pretty great ! High quality problems.

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

Is there a way to solve C using something similar to Hall's marriage theorem?

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

    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.

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

    Yes, there is :D https://atcoder.jp/contests/arc144/submissions/33347474

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

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.

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

    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.

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

      Thank you very much! After trying several small cases I finally understood it.

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

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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.

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

    That's because you got stronger.

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

How to approach C? Can someone explain their approach.

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

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.)

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

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

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

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?

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

Can anyone help me in getting the solution of A of AtCoder Regular Contest 144. I have studied the editorial but wasn`t able to understand??

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

    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.

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

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<n$$$, thus $$$T=\sum_{S=1}^{S=K}(1+K-S) \times C_{S-1}^{n-1}=\sum_{S=n}^{S=K}(1+K-S) \times C_{S-1}^{n-1}$$$.

Then, $$$T=(1+K)\sum_{S=n}^{S=K}C_{S-1}^{n-1}-\sum_{S=n}^{S=K}SC_{S-1}^{n-1}$$$.

Now, by taking advantage of this equation $$$C_{k}^{k}+C_{k+1}^{k}+...+C_{n}^{k}=C_{n+1}^{k+1}$$$, we have $$$(1+K)\sum_{S=n}^{S=K}C_{S-1}^{n-1}=(1+K)C_{K}^{n}=(1+K)\frac{K!}{n!(K-n)!}=\frac{(K+1)!}{n!(K-n)!}=\frac{(n+1)(K+1)!}{(n+1)!(K-n)!}=(n+1)C_{K+1}^{n+1}$$$, and

\begin{equation} \begin{aligned} \sum_{S=n}^{S=K}SC_{S-1}^{n-1}=\sum_{S=n}^{S=K}S\frac{(S-1)!}{(n-1)!(S-n)!}=\sum_{S=n}^{S=K}\frac{S!}{(n-1)!(S-n)!} \ &=\sum_{S=n}^{S=K}\frac{nS!}{n!(S-n)!}=n\sum_{S=n}^{S=K}C_{S}^{n}=nC_{K+1}^{n+1} \end{aligned} \end{equation}

Thus, $$$T=(n+1)C_{K+1}^{n+1}-nC_{K+1}^{n+1}=C_{K+1}^{n+1}$$$.

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

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!

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

Who can please teach me how to solve problem C ? I can't understand the Editorial. Thanks a lot!!!

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

Can anyone help me with problem b, I read the editorial but could not understand the solution

→ Reply