We will hold AtCoder Regular Contest 217.
- Contest URL: https://atcoder.jp/contests/arc217
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20260405T2100&p1=248
- Duration: 120 minutes
- Writer: nok0, sounansya
- Tester: maspy
- Rated range: 1200 ~ 2799
- Point Values: 500-700-700-700-900
We are looking forward to your participation!
first time for ARC!
me too
Seems like D's trick is same as the one used in "896E Welcome home, Chtholly"
In B , how to find f(P)=2^N-1-S ? Why do you consider S=sigma 2^k?
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.
I understand,Thanks!
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.
https://atcoder.jp/contests/arc217/submissions/74715037
O(N^3) solution for C!
https://atcoder.jp/contests/arc217/submissions/74718128
AC just 1 minute after the contest ended
Are there any Chinese people?
yes