atcoder_official's blog

AtCoder Regular Contest 217 Announcement
By atcoder_official, history, 7 weeks ago, In English

We will hold AtCoder Regular Contest 217.

We are looking forward to your participation!

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

»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

first time for ARC!

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Seems like D's trick is same as the one used in "896E Welcome home, Chtholly"

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

In B , how to find f(P)=2^N-1-S ? Why do you consider S=sigma 2^k?

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    Consider $$$g(i)$$$ = how many times $$$i$$$ is moved. we have the following recurrence: $$$g(i) = g(i+1) + g(i+2) + \ldots + g(n)$$$ + [It is possible to move $$$i$$$ before anything bigger than $$$i$$$ is moved/ $$$i$$$ is not a high element].

    We want $$$\sum g(i)$$$, to compute this we observe that $$$i$$$ contributes $$$2^{i-1}$$$ to the sum if it is a high element. Counting the complement of this is easier so we instead compute sum of $$$2^{i-1}$$$ such that $$$i$$$ is a high element.

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

Haha I believed the best method to get the largest $$$f$$$ in B is always move the rightest movable element and wrote a huge classification discussion which wasted me about one hour and finally became fake. I think C is easier than B.

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

https://atcoder.jp/contests/arc217/submissions/74715037

O(N^3) solution for C!

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/arc217/submissions/74718128

AC just 1 minute after the contest ended

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Are there any Chinese people?

→ Reply