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.

Bro C was just too difficult for me.

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)

In D, does the solution described for the entire array ("We iterate backwards on the array [...] is the largest, we do nothing") not work on

11 1 6 9 4 7 4 4 10 3 2 3

in sample? I get 1313 when it should be 1568

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;

For D solution, why 31? 2 divisors

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 very bad at solving problem like B. Can anyone tell me what topic do i have to learn to solve this kind of problem. Thanks in advance.

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$$$

I think Problem B very Medium hmmm

In G1 editorial, while counting cnt(i,j), it should the case that j < m < i and not the other way right?

Could you please help me, what do I do if it is showing "N/A" in the solution Code page? Thank You

Can we solve D using priority queue. We store pair of {lowest value a[prev] can get, a[prev]} and check if a[i]>pair.first then we can perform the operation and pop the pair. We will then maintain answer vector where ans[i] += a[i-1] — pair.second + pair.first + a[i] * (pair.second/pair.first)

I can't understand C's solution,could someone help explain the principles clearly,it's too abstract for me.

Hori, the code is not available

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.