Tutorial is loading...
author: Hori
Code: 288397475
Tutorial is loading...
author: willy108
Code: 288397529
Tutorial is loading...
author: Hori
Code: 288397556
Tutorial is loading...
Code: 288397595
Tutorial is loading...
author: lunchbox
Code: 288397611
Tutorial is loading...
author: turtletortles
Code: 288397640
Tutorial is loading...
author: sum
Code: 288397661
Tutorial is loading...
author: Benq
Code: 288397685
Tutorial is loading...
author: Hori
Code: 288397713
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?
Asked chatgpt to make a problem which was initially solving the problem for a single array with no i < j constraint (this was an existing div2a). I thought the i < j constraint would make it more interesting and solved for it. Then the solve for every prefix part was added. Also made sure to plug it back into o1-preview to make sure it couldnt solve XD
Code is not accessible.
Fixed, thanks for letting me know
cant see tutorial of D, but is it possible to solve D using knapsack?
I didn't solve it, but I think D is to be solved using the observation: if $$$a_i=2^{p_i} \cdot {q_i}$$$, there should be $$$p_i$$$ operations that greedily decrease $$$A_i$$$ and greedily increase the member of the prefix with greater or equal index and max $$$q$$$.
With this, we can compute the optimal sum for each prefix separately in quadratic time. Or, we can compute for each prefix using the the previous prefix in linear time (somewhat like DP).
Essentially, we can process the $$$i^{\text{it}}$$$ prefix as adding $$$A_i$$$ to an array $$$p$$$. By adding $$$A_i$$$, we offer a new $$$q$$$ to all of the elements that precede it. We obviously want all of $$$A_1, \cdots, A_{i-1}$$$ that are using their operations to increase an element with a lesser $$$q$$$ to instead increase $$$A_i$$$. All of the elements that precede the nearest element with a greater $$$q$$$ will not change, but those that follow will now use their operations to increase $$$A_i$$$. We can find the nearest greater element with a greater $$$q$$$ using monotonic stacks, which are well explained by the USACO Guide or CPH. With prefix sums, we can find the the factor by which $$$A_i$$$ increases, and monotonic stacks have a linear time complexity, so the solution is done in $$$O(n)$$$.
I don't see the intuition for Knapsack DP as the problem isn't looking for a subset, but maybe you're on to something.
Hii
i have used this approach first am i wrong because it leads to int overflow and would turn negative?
my reasoning was that if we can find a max number which a[i]*pow(2,2supto[i]) and add prefix where all numbers would be reduced to their max _odd and suffix would be unchanged
https://mirror.codeforces.com/contest/2035/submission/288358437
C is the hardest div2C in history. Even harder than D2 from the last div2 round (rated 2187 on CList).
what is CList?
https://clist.by/problems/
I took a look, and it doesn't seem that difficult; it only has a score of 1322.
i found it easy
What? It shows only 1322 for me. Maybe it wasn't properly updated when you saw it?
He means the last div2 D2 was 2187
Oh, I get it now. I thought they meant it is rated higher than that 2187. Turns out that they 'felt' it's harder than that.
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
you have to collect all the 2's in terms of powers and give them to the best successor possible, then calculate the sum of the remaining odds which are not considered
Ex1:1 6 5
for this, you have to give all the 2 powers to 5 which is better over 3
Ex2:4 1 3
same as above but the format is different, first you will accumulate at 1 then accumulate at 3
Ex3:4 7 2 2 2
Here for the first 2 elements, 4 will be accumulated into 7
For 3 elements, since there is no benefit of sending 4 to 2 over 7, we leave it unchanged
For 4 elements, first, we will accumulate the previous 2 and then compare 4 with 7, since 7 is bigger, the powers remain unchanged
For 5 elements, we will accumulate past 2 twos to get 8, which is in turn greater than 7, so we will send the 4 to 8 making it 32
thus we will be storing all the accumulated indices and powers in a stack, all the odds remaining after removing powers of 2 in other variables unaccumulated_odds, whenever we get a new element we try to pop elements in the stack, and try to accumulate values at new element same as shown in example 3
think like this . from a given i to previous 31 even numbers you will have a number with or without shifting 2's greater than 1e9 . since every ai is bounded by 1e9 . all other even numbers before that will lose thier 2's to largest element
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
Actually, I did notice it after thinking about it for a while. Not bad. Wouldn't have ever come up with it myself though. Thanks for the editorial.
you can solve E using ternary search too.
talk is cheap, share code.
Lol no. You can maybe pass the current testset if you are lucky but it's not "solving".
Bro C was just too difficult for me.
for C,
we can also approach it greedily
, observe ifn 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 place3, 1 before it we would get the first bit ON
which would be carried forward to get themaximum value as n.
Also in the case ofn 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!Submission link: https://pastebin.com/x0gwHdeL
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