Okay so D is done by ChatGPT but also oursaco. oursaco, if you don't mind, can you please tell a little bit about how you contributed to the creation of that problem? Like did you just write the prompt or did the chatGPT stuff have to be revised?

Code is not accessible.

cant see tutorial of D, but is it possible to solve D using knapsack?

C is the hardest div2C in history. Even harder than D2 from the last div2 round (rated 2187 on CList).

Yo, i've just completed tutorial for problem D in Hackmd : link

Sorry for not directly publishing tutorial in codeforces, i prefer using hackmd :)

First time getting upvoted, thanks a lot !

C odd case: since n%2==1 then l will always be 1 so it is easier to just set the last 4 to 1 3 n-1,n

Can someone share their thought process of D like how and why it works

Can E be solved by simulated annealing?I submitted serveral times, but no luck.288417811.This is the first time I wrote simulated annealing, so it may come with some mistakes. So I wonder whether it can be solved by such a approach or not.

No way in hell I can ever "notice" what the editorial tells us to notice in problem D.

Solved it by thinking about where to utilize the 2s in between the last number we have given 2s to and the current number i. If we can use these 2s to make a[i] greater than the last number we gave all the 2s, then we should give all the twos we gave the previous number to this a[i]. Else we re-use the answer from the last number we gave all the twos and give all the twos in between to a[i]. To maintain the last number we gave all the 2s we can use monotonic stack. Submission: https://mirror.codeforces.com/contest/2035/submission/288418798

you can solve E using ternary search too.

for C, we can also approach it greedily, observe if n is odd then last operation is and so we can get to less than or equal to last operation, so we choose last to be n and second last to be n-1 as (n &(n-1)) = (n-1), but what if we try to make the first bit of (n-1) on? then we can make it (n), but how to do it? observe if we place 3, 1 before it we would get the first bit ON which would be carried forward to get the maximum value as n. Also in the case of n if it is not a power of two, n would have a bit which isn't present in the sequence so we can greedily place it at the end, and have a permutation such as 1, 2, 3..., n. Rest is nicely explained in the editorial, thanks for it!

Am I the only one who found B to be harder than C and D? (and D easier than C)

One more way to solve F is (same observation(and logic) but different implementation) :

Do a normal binary search on answer , but this time instead of checking for only mid , check from mid-2*n+1 , mid , even if one turns out to be true(say for num) , hi = num-1 else lo = mid+1;

can someone help me in proving my solution for C? I brute forced some cases of $$$ 2, 1, 3, 4, .... , n $$$ and noted that we get the required $$$ k $$$ somewhere always. based on this, my solution is just $$$ x + 1, x + 2, x + 3, ......, n, 2, 1, 3, ....., x $$$ for some x such that the resultant $$$ k $$$ for $$$ 2, 1, 3, ... x $$$ is maximum and $$$ n - x $$$ is even. I cannot formally prove why the sequence $$$ 2, 1, 3, 4, ... x $$$ gives the best k always.

Submission

I just don't know why $$$O(n^2\log{a_i})$$$ does not fit in 4 seconds in problem F.

UPD: It seems to be my problem. I was submitting in G++ 17 instead of G++ 20, which is based on 32-bit architecture.

I am confused, in problem D , we can have $$$a_i$$$ > $$$a_j$$$ but it is more optimal to divide $$$a_i$$$ by 2 and multiply $$$a_j$$$ by 2

example: 20 and 9

20 + 9 = 29

but we can do: 20 / 2 / 2 = 5

and 9 × 2 × 2 = 36

and the sum becomes 41 > 29

what am I missing here ?

However, E can be solve in $$$O(z^{3/4})$$$ , only by using some optimizations in brute force. My Code

Hori

In the editorial of E problem, you have mentioned this statement.

a * b >= 2 * z , this implies that min(a,b) <= sqrt(2*z) ? Why is that ? How did we reach there ?

===> a * b >= 2 * z

===> min(a,b) * max(a,b) >= 2 * z

===> sqrt ( min (a,b) * max(a,b) ) >= 2 * z 

Just to replace few values, lets take a = 5 , b = 5, and z = 5, then a * b >= 2 * z holds true, but min(a,b) <= sqrt(2 * z) doesn't hold true.

Please can you elaborate a little here ?

is system testing done till this round !!?

For solution E, I don't understand how we got $$$\dfrac{a\cdot b}{2} \ge z$$$

The value for $$$\text{has_}i$$$ in Problem F's editorial is wrong. Should be $$$\lfloor \frac{x}{n}\rfloor + [(x\mod n)\geq i] =:\text{has_}i$$$ instead.

Hey I came up with this solution but unsure of it's correctness and having difficulty in implementing it because of large numbers and comparing them while handling mod

dp[i] = max result possible for prefix i,

so transition would be whether i place all power of 2 possible in ith index and get sum of base odd number for all 0->i-1 indexes

or

take last index where we placed all 2's before that i.e. dp[last[i-1]] + placing all 2's in range last[i-1] +1 to i to ith element can then calculate answer and take whatever is maximum and set last[i] = i or last[i-1] accordingly. can anyone help me with its correctness and how to implement it.

In F, let's say the root is 3, now is doing operation on node 1, the parities of the nodes are 0 0 1 0 0

If I do the operations as the editorial "Have all nodes toggle their own parity, but have the root toggle the parity of the node that comes directly after it. Now, that node can just fix itself, and all nodes have the same parity."

After the operations, isn't it became 1 1 1 0 1? how come to make all parity the same?

How to think of problems such as C ??

Problem E we can solve it in O(k * sqrt(z / k)) if k <= 10000, else O(1e4 + sqrt(z / k))

If k <= 10000, the brute force takes k * sqrt(z / k)

Else, we try for 1 to 1e4 upgrades without attacks between them. Then we need to calculate the points where (z + w — 1) / w * y is optimized, and these points are (in worst case) 1e4. These points can be calculated while simulating jumps of length k, so the complexity of this part is 1e4 + sqrt(z / k)

It maybe has a better complexity if we reduce the threshold of k, but I'm too lazy to calculate it xd

Seems like E can be solved in O(sqrt(z)) time, here is the code for it: 366869087 As of writing this, it also has the best execution time