maroonrk's blog

AtCoder Regular Contest 166 Announcement
By maroonrk, history, 7 months ago, In English

We will hold AtCoder Regular Contest 166.

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

We are looking forward to your participation!

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

»
7 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Hope that I can get rating.

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

Wow, hope this round can be friendly to me noob :)

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

Plz plz give me 2 Dan I solved 4

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Let me show how I solve problem C.

I stare at the screen for 30 minutes and have no idea about it. Then I write a brute force solution at first.

Then I print down each answer of 1x1, 1x2, 1x3 ... 1xn, find it is geometric progression. For 2x2, 2x3...2xn, 3x3 ... 3xn feel the same

Then I observe the ratio, wait, Fiobnacci?

Then I calculate the product, and found it is the square of product of Fiobnacci.

Finally I get AC by last moment.

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

    How to compute $$$F_2 F_4 \dots F_n$$$ for $$$n \leq 10^{18}$$$?

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

      Thank you for correction, I haven't find a solution yet, my previous thought about using matrix multiplication is wrong.

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

how to solve B using dp? the editorial says so but doesn't give much details.

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

why my code fails in B?: https://atcoder.jp/contests/arc166/submissions/46392958

I m using int128 to avoid overflow, I m doing a simple dp and trying the multiple ways to get the multiple. done my getmultx is false :') when v%x==0 I return v+x my bad :)

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

there's a mistake in C — LU / RD Marking Editorial.Assume $$$n\leq m$$$,it's not $$$(a_2a_4...a_{2n})^2a_{2n+1}^m$$$ but $$$(a_2a_4...a_{2n})^2a_{2n+1}^{m-n}$$$.

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

    there is a explain under the C — LU / RD Marking Editorial's final formula.

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

hey Guys! So I was going through the editorial of problem C and didn't understand how exactly the formula in the last step is derived. I understand how to answer for each individual component, that is the Fibonacci number, and multiply the results of each component together as they are independent. But why are we squaring the result of the multiplication of each component? and why is the term (a2n+1)^m there in the end? I enjoyed the explanation so far and really want to understand it completely. Thanks!

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

    I figured out by just run some cases manually on paper. It's more like a observation thing.

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

      I see. I was hoping I could prove it somehow, seems like something interesting could be learned while trying to prove that final result

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

My rating rose to 2042 from 2028 but today I found it returned to 2028. Is my rating rolled back? I found no evidence that the contest will be unrated.

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

    Not only this round but also many rounds recently have the same problem. For example, ABC323.

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

      It seems the ratings are coming back! :)

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

        Yeah, but what interesting is that the rating changes of ABC322 came back, but ABC323 did not.

        → Reply