maroonrk's blog

AtCoder Regular Contest 112 Announcement
By maroonrk, history, 4 years ago, In English

We will hold AtCoder Regular Contest 112.

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

We are looking forward to your participation!

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

Comments Comments (46)
| Write comment?
»
4 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Will the round only be rated upon submission? (as usual)

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

Really liked third problem. Fresh and new concept used.

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

Is it more difficult than a CF Div2?The first ARC I participate make me doubt my ability:(

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    You can compare first three problems of ARC to that of typical CF div2 (B/C/D)/E.

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

Thank you for the good contest! The problem is very interesting and challenging (really like problem B&C!

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

Is there a neat, less case-worky solution for 2nd problem? :(

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

    You can calculate negative min max range and positive min max range. You have to take care of only one case this way which includes zero.

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

      I calculated two intervals, one of type [-b — a1, -b + a2] and other [b — a2, b + a3] and then merged the intervals if they overlap.

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

    Only three cases, b>0,b=0,b<0

    For each case, you can do the operations in 4 ways:

    1. only operation 2
    2. do operation 2, then do operation 1
    3. do operation 1, then do operation 2
    4. do operation 1, then do operation 2, then 1

    Code

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 8   Vote: I like it +3 Vote: I do not like it

    I have something that I think is less case-worky in code, although the proof itself seems to be as case-worky as the editorial's. Note: I assume $$$[a, b]$$$ is the closed interval over the integers with endpoints $$$a, b$$$.

    With $$$B > 0$$$, it is easy to show that the solution is some subset of $$$[-B - n, B + n] \cup [B - n, B + n]$$$, by assuming that the first operation costs 0. Without the restriction $$$B > 0$$$, we can say that the solution is some subset of $$$[-B' - n, B' + n] \cup [B' - n, B' + n]$$$ where $$$B' = |B|$$$.

    If we imagine that $$$[-B' - n, B' + n]$$$ and $$$[B' - n, B' + n]$$$ are disjoint, then operation 1 just switches between them. Hence we never need to use operation 1 more that twice. This conclusion holds even if the two sets are not actually disjoint.

    If we use operation 1 zero times, we can get anything in the range $$$r_1 = [B - n, B]$$$. If we use it once, we can get the ranges $$$r_2 = [-B, -B + n']$$$ and $$$r_3 = [-B - n', -B]$$$ by using it at the start or at the end, where $$$n' = (C-1) / 2$$$. Finally, if use the operation twice, we get the range $$$r_4 = [B, B + n"]$$$. The nice thing is that this is independent of the sign of $$$B$$$.

    The answer is then $$$|r_1 \cup r_2 \cup r_3 \cup r_4$$$.

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

    You can consider b>0 and b<0 separately without intersections. From b>0 it is better to move to zero. From b<0 it is better to move to +/-INF;

    Sample

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

After getting 3 WA,I inserted b=0 and c=1 case and in problem B and it passed :D.

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

Is the answer to D, the connected components in a graph of '#' + min(rows never visited[1,n-1],columns never visited[1,m-1]) ?

I tried this and got 30 correct and 7 wrong

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

    You need to place '#' at (0,0), (h-1,0), (0,w-1), (h-1,w-1) and you will get AC because we can go there from any position.

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

      Darn, I tried to handle cases where '#' occurs in the outer square seperately. It works now, thanks!

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

Who else did brute force for B and observed the patterns to get accepted!

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

It's the first time I participate in ARC, the problems are much harder than I thought, and I only solve two of them.

Since the editorial came out as soon as the contest ended, I think ARC is much better than ABC:)

Hope everyone can be better at solving problems and have fun during the contest, like I did!

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

It was the first ARC for me. Is ARC usually a little harder than a CF Div2?

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

Can someone please explain the problem D, the 1st sample case, not able to get the problem statement.

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

How to solve problem $$$C$$$ ? I am not able to justify the solution in editorial and not able to get how to implement it .

Is following observation correct : Suppose player $$$2$$$ is on vertex $$$v$$$ and is going to decide to which children he should move . If he moves to child $$$u$$$ such that subtree at $$$u$$$ has even size , then when piece will return to $$$v$$$ back , the turn will be of $$$2nd$$$ player only.

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

(This is an abridged version. The full version will be ready in a few hours.)

Waiting for the full version of the editorial :(

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

One simple question about F. Die Siedler.

Why do numbers of the form $$$q = 2^k k! -1$$$ only have divisors which are either small or large? ($$$\min(d,\frac{q}{d})$$$ is no more than $$$1214827$$$ when $$$k\le 16$$$ in actual fact, according to which a simple big-small solution works in this task.)

Is it reasonable or just by coincidence?

BTW thanks very much for interesting problems. :)

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

    It's a coincidence. I don't think this will holds also for large $$$k$$$.

    btw still you can guess that this $$$q$$$ has only small or large factors. If a number has many small prime factors, then it will have some "medium" factor. But $$$q$$$ is not divisible by any prime number less than $$$16$$$ because $$$q+1$$$ is a multiple of $$$16!$$$, so it's likely to have large prime factors.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    It really doesn't hold for large $$$N$$$. Already for $$$N = 18$$$, the smallest prime divisor is $$$23,063,137$$$. I expect divisors to be relatively small, but that's not what matters for time complexity here.

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

in Problem D

3
...
.#.
...

when Input is something like this, when we start from (2,2), we can go anywhere, one-direct. when we start from (1,1) we cann't approach (2,2). we cann't go everywhere. is this problem real okay to start from anywhere?

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

    problem statement say that it should be efficient for "every" square. it was my misunderstood.

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

Can anyone pls tell what's the difficulty level of ABC and ARC in comparison to codeforces DIV2

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

    I read somewhere that ABC is Div2 , with A being way too easier.ARC is Div1- , and AGC is Div1

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

(This is an abridged version. The full version will be ready in a few hours.)

Still the full version is not uploaded. maroonrk, Can you please look into it.

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

Who knows how to solve E?

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

    The last operation must move either $$$a_1$$$ to the left or $$$a_N$$$ to the right. Pick one of those elements. Then, for any previous operation, we have 2 choices that don't matter — put this element to the left/right, or $$$2(N-1)$$$ choices in a smaller problem with the final sequence that doesn't contain this element. An $$$O(N^2M)$$$ DP solution is obvious from that.

    Let's say that in the end, we'd move $$$l$$$ leftmost elements of $$$a$$$ to the left (in the moves that affect them last) and $$$r$$$ rightmost elements to the right. There are two things to think about: - The remaining elements in between, of course, must be in the same order as in the original permutation. - OTOH all cases $$$l+r=N$$$ correspond to distinct sequences of moves.

    We have $$$l+r$$$ significant operations — those that move some element for the last time. There are $$$l+r \choose r$$$ ways to choose their order. If there were $$$c_k$$$ "insignificant" operations immediately after the $$$k$$$-th of them, where $$$\sum_{k=1}^{l+r} = M-l-r$$$, the number of possible sequences would be $$$\prod_{k=1}^{l+r} (2k)^{c_k}$$$. We can count them all with a DP, where states are $$$(l+r, \sum c_k)$$$, in $$$O(NM)$$$.

    Finally, check all pairs $$$(l, r)$$$ and for those that are valid, get the DP value for $$$(l+r, M-l-r)$$$, multiply by $$${l+r \choose r}$$$ and sum that up to get the answer in $$$O(N^2+NM)$$$.

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

      can you please explain " $$$2(N−1)$$$ choices in a smaller problem with the final sequence that doesn't contain this element"

      what I think/understood is you are saying about the case when this element(that we choose to be the last move ) is chosen at an earlier moment, but I don't get from where $$$2(n-1)$$$ came ?

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

        Let's say you made a sequence that has $$$a_N=N$$$ by moving $$$N$$$ to the right in the last ($$$M$$$-th) operation. In each previous operation, you can either move one of the elements $$$1, 2, \ldots, N-1$$$ to the left/right or move element $$$N$$$. There are $$$2(N-1)$$$ possible operations of the first type and the sequence you'd get by performing only these operations on the initial sequence $$$(1, 2, \ldots, N-1)$$$, i.e. ignoring all operations that move element $$$1$$$, must be $$$a_1, a_2, \ldots, a_{N-1}$$$.

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

      If you're dumb like me and can't see the smart math ideas, you can also just speed up to $$$\mathcal O(N^2 \log N)$$$ using FFT.

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

        There's a lot of problems I've solved with dumb ideas too. Especially sqrt decompositions. This isn't a hard thing to realise though — just that we need only $$$l+r$$$ for states, not $$$(l, r)$$$.

        → Reply