maroonrk's blog

AtCoder Regular Contest 180 Announcement
By maroonrk, history, 3 months ago, In English

We will hold AtCoder Regular Contest 180.

The point values will be 400-600-600-700-800-1100.

We are looking forward to your participation!

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

»
3 months ago, # |
  Vote: I like it +71 Vote: I do not like it
Not Fun Fact
→ Reply
»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Regular Contests are harder than Div2, right?

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

Hope I can get positive delta!

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

    B and C are both ez to implement, but need some brave observation(guessing). Like them.

    Solved ABD.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am excited about it.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited for this contest, good way to start the weekend!

→ Reply
»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it
Hope to get positive delta!
→ Reply
»
3 months ago, # |
  Vote: I like it +33 Vote: I do not like it

D <<< B

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

    Really? We can bruteforce B. N only 500. I stucked on problem C.

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

    I think B<<<<D. B is easy to construct the answering pairs when you guessed the number of operations.

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

      Guess is really not easy for me xD.

      But D just needs a little observation and it's a trivial ds problem :)

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

    Agree, I solved ACD.

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

I could only do O($$$n^4$$$) for B :(

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 5   Vote: I like it -18 Vote: I do not like it

    You can do O(N^2 log(N))

    First, you can only swap all numbers with index l where l <= N-K. And you want to swap from the smallest number first (the more small number on right hand side, the more operation you can perform).

    Then, for each index l, you just need to collect all possible index to swap. Then swapped it with l from the biggest to the lowest.

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

Ohhhh, I got my 3rd rk145 in arc! So unbelievable!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Passed B by guessing a greedy approach according to the sample output.

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

    was the greedy approach to swap $$$(i,j)$$$ with min difference and minimum $$$a[i]$$$?

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

      Yes

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

        Well, I swapped $$$(i,j)$$$ such as $$$a_j$$$ is the biggest and $$$a_i$$$ is the smallest.

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

I think that problem C is solvable in $$$O(n^2max|A_i|)$$$

Submission

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

    Yeah, mine is also $$$O(n^2max|A_i|)$$$. My submission

    $$$dp_{i,j,0/1}$$$ means that for $$$A_1,A_2,\dots,A_i$$$, sum of chosen numbers is $$$j$$$, and whether the last chosen number equals to $$$j$$$ (true-->0, false-->1)

    → Reply
»
3 months ago, # |
  Vote: I like it -83 Vote: I do not like it

Atcoder Rubbish Contest 180

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

Spent $$$1.5 hr$$$ on Problem A trying to find DP solution.

Failed miserably.

Problem B looked doable and spent the rest of the time on it.

Missed AC by meagre $$$33 s$$$

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

was B that easy? i spent an hour and had no idea at all tried several things, but could not get the solution!!

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

Problem E was one of the best problems I've ever seen, I think it's really cool.

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

It was completely out of my imagination that $$$[x^n]f(x,y)=c_ny^{(A+1)n}$$$. Are there any implicit reasons for this form or is it just randomly coming to your mind? orz

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

    Okay, I guess that if you believe it's a polynomial of $$$y$$$ (otherwise this problem would seem impossible to solve?) and then you can get this thing real quick.

    But noticing that the $$$1$$$ in the formula is actually the upper bound of $$$x_i$$$ is also hard

    orz maroonrk

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

      I think it's pretty easy to see that $$$a_n(y)$$$ is proportional to $$$y^{(A+1)n}$$$ (assuming the definition of $$$a_n(y)$$$ is as I mentioned below maroonrk's post).

      Recall that $$$a_n(y)$$$ is an integral of a homogeneous function $$$e(x_1,\dots,x_n,y)$$$ of degree $$$nA$$$ over the $$$n$$$-dimensional box $$$(x_1,x_2,\dots,x_n,y)\in [0,y]^n\times \{y\}$$$. In simpler terms, if we scale all of $$$x_1\dots x_n,y$$$ by a factor of $$$r$$$ then the value of $$$e$$$ scales by $$$r^{nA}$$$.

      Suppose we have evaluated $$$a_n(y_1)$$$ for some real $$$y_1$$$ and want to relate it to $$$a_n(y_1r)$$$ for some positive real $$$r$$$. Consider the one-to-one mapping from points in the original box $$$[0,y_1]^n\times \{y_1\}$$$ to the new box $$$[0,y_1r]^n\times \{y_1r\}$$$ that scales element-wise by $$$r$$$. The value of $$$e$$$ scales by $$$r^{nA}$$$ after applying the one-to-one mapping. Also, the volume of the new box is a factor of $$$r^n$$$ larger than the volume of the old box. Multiplying these two factors gives that $$$a_n(y_1r)=r^{n(A+1)}a_n(y_1)$$$, from which it follows that $$$a_n(y)$$$ is a polynomial in $$$y$$$ of degree $$$n(A+1)$$$.

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

      But noticing that the 1 in the formula is actually the upper bound of $$$x_i$$$ is also hard

      I think you can still solve the problem even if $$$1$$$ in the formula was some other constant $$$c$$$. It would just add one extra step. Compute $$$h(z)$$$ in the same way as before, then replace $$$[z^N] \exp h(z)$$$ in the answer with $$$[z^N]\exp (ch(z))$$$.

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

    $$$x^A$$$ term can be interpreted as $$$x$$$ having $$$A$$$ children that are leaves. So the problem is about counting something on tree of $$$n(A+1)$$$ non-root vertices, and that's the intuition behind the observation.

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

      https://atcoder.jp/contests/arc180/editorial/10317

      I think the definition of $$$a_n(y)$$$ in the editorial is off by a factor of $$$y^n$$$. From the way it is currently defined it is proportional to $$$y^{An}$$$, not $$$y^{(A+1)n}$$$. Instead of the expected value, it should be the $$$n$$$-dimensional integral.

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

        You are right, and I fixed it now. Thanks for pointing it out.

        → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone detail problem D?

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

Problem A: I could understand how inverting even letters would help find out patterns like A, BAB, BABABAB etc.

But for this example ABAB we can just make this whole AAAA when last B will not go isn't very obvious. Any more reading material on perhaps a simple topic

"In competitive programming, a well-known technique is using parity to perform inversions. Let’s apply it to this problem."

Couldn't find anything online.

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

    Exactly! I didn't find/understand anything online for that question. Would be great help if someone can explain the intuition behind the question.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Here's how I make the observation for problem A.

      Consider string ABAB. There are 2 different operations we can perform, which are reduce ABA B and A BAB. Notice that either way, the resulting string would be AB. So, there are 2 different string you can make for ABAB --> ABAB and AB.

      Try with longer string, ABABA. Different operations you can perform are ABA BA , A BAB A , and AB ABA. Whichever you choose, the resulting string is the same, ABA. You can choose either to perform the operation again or not. Finally, there are 3 different strings you can get, ABABA, ABA, and A.

      Up to this point, you can infer the pattern if the strings are alternating (ABABABAB... or BABABAB....).

      What happened when we find 2 consecutive characters, such as ABAB AAAA. You will notice that you can reduce ABABA to (ABABA, ABA, A) with the above methods but you can't change the last substrings (AAAA).

      Therefore, the number of possible strings you can have depends on the alternating characters.

      For example: BBABABAABABAAAABA. You can separate this string into several alternating substrings. B | BABABA | ABABA | AA | ABA. Ignore non alternating substrings such as B and AA. Find the number of different substrings you can create for each alternating substrings and multiply it to get the result.

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

Can some one explain problem C how the Dp state changes

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

thanks for the contest, liked the problems!

However, maroonrk please remove your template when providing c++ implementation for the editorial. it is really annoying to scroll through 1000 lines of code to reach the actual part, code is supposed to be clear for the editorial.

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

Is there any DP solution for problem A ?

If anyone has solved, please share once...

Thanks

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

    Actually the problem was based on the fact that whenever you are seeing a continuous alternating pattern no matter on which part you apply that operation you will end-up with same string in each case so it totally depends on size of alternating pattern only. So all you need to do is find all continuous alternating pattern and multiply and then take % here is my solution

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the solution for Problem B? Thanks in advance.

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

Please share some thoughts on C. I am not able to catch up the editorial.

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

    The way I thought about the problem: $$$dp[i][j] =$$$ number of ways to have the operations end in sum $$$j$$$ at index $$$i$$$. The transitions are relatively simple here, we can choose to not include $$$i$$$, which is $$$dp[i][j] = dp[i][j] + dp[i-1][j]$$$.

    Or we can choose to include $$$i$$$ which is $$$dp[i][j + a[i]] = dp[i][j + a[I]] + dp[i-1][j]$$$. The tricky part here is there is actually a single situation in which we will accidentally count an already included prefix.

    This is when $$$j == 0$$$ and $$$a[i] \neq 0$$$ because suppose two situations:

    1. We include $$$i$$$: Now our operations will end with sum $$$a[i]$$$. Our prefix is $$$[... a[i]]$$$

    2. We don't include $$$i$$$: Now our operations will end with sum $$$0$$$. Our prefix is still $$$[... a[i]]$$$.

    Thus, at $$$i$$$ these situations both have the same prefix, however, if sometime in the future we utilise an operation, the resulting array for both cases will be different.

    For example if we choose some $$$a[k]$$$ such that $$$k > i$$$, then it is easy to see $$$[...a[i], a[k]] \neq [...a[i], a[k] + a[i]]$$$

    So lastly when we transition for $$$dp[i][j + a[i]]$$$ when $$$j == 0$$$ and $$$a[i] \neq 0$$$ instead of adding to $$$dp[i][j + a[i]]$$$ we create a separate array $$$cnt[i][j]$$$ and $$$cnt[i][j + a[i]] = cnt[i][j + a[i]] + dp[i-1][j]$$$. Then we also must handle the transition $$$dp[i][j + a[i]] = dp[i][j + a[i]] + cnt[i-1][j]$$$.

    Lastly when considering $$$cnt[i][j + a[i]]$$$ we would also not like to overcount prefixes for the same $$$x = a[i]$$$. This is because if at two different indexes, $$$a[i] == a[j]$$$, we cannot use the same prefixes.

    Sample Code: https://pastebin.com/3xp2cxpB

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know the complexity of my solution to B https://atcoder.jp/contests/arc180/submissions/55022803

Perhaps the data is missing some case or perhaps this code happens to be faster than it seems

→ Reply