maroonrk's blog

AtCoder Regular Contest 180 Announcement
By maroonrk, history, 2 days 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
  • +86
  • Vote: I do not like it

»
2 days ago, # |
  Vote: I like it +68 Vote: I do not like it
Not Fun Fact
→ Reply
  • »
    »
    37 hours ago, # ^ |
      Vote: I like it -58 Vote: I do not like it

    Yes, it's not fun. Downvoted.

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

Regular Contests are harder than Div2, right?

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

Hope I can get positive delta!

→ Reply
  • »
    »
    10 hours 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
»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I am excited about it.

→ Reply
»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
33 hours ago, # |
  Vote: I like it +10 Vote: I do not like it
Hope to get positive delta!
→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

D <<< B

→ Reply
  • »
    »
    31 hour(s) 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
  • »
    »
    31 hour(s) 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
    • »
      »
      »
      30 hours 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
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    Agree, I solved ACD.

    → Reply
»
31 hour(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    31 hour(s) 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
»
31 hour(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
31 hour(s) 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
  • »
    »
    31 hour(s) 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
    • »
      »
      »
      31 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes

      → Reply
      • »
        »
        »
        »
        30 hours 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
»
31 hour(s) 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
  • »
    »
    31 hour(s) 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
»
31 hour(s) ago, # |
  Vote: I like it -80 Vote: I do not like it

Atcoder Rubbish Contest 180

→ Reply
»
31 hour(s) 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
»
30 hours 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
»
30 hours 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
»
30 hours 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
  • »
    »
    30 hours 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
    • »
      »
      »
      19 hours 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
    • »
      »
      »
      18 hours 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
  • »
    »
    29 hours 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
    • »
      »
      »
      19 hours 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
      • »
        »
        »
        »
        19 hours 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
»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone detail problem D?

→ Reply
»
29 hours 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
  • »
    »
    29 hours 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
    • »
      »
      »
      22 hours 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
»
29 hours 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
»
29 hours ago, # |
  Vote: I like it +19 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
»
27 hours 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
  • »
    »
    15 hours 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
»
24 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 hours 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
»
21 hour(s) 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