Hori's blog

Codeforces Global Round 27 Editorial
By Hori, 13 hours ago, In English
Tutorial is loading...

author: Hori

Code: 288397475

Tutorial is loading...

author: willy108

Code: 288397529

Tutorial is loading...

author: Hori

Code: 288397556

Tutorial is loading...

author: ChatGPT and oursaco

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

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

»
12 hours ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 hours ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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

    → Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Code is not accessible.

→ Reply
  • »
    »
    12 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fixed, thanks for letting me know

    → Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

    → Reply
»
11 hours ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
10 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

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

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

→ Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

you can solve E using ternary search too.

→ Reply
  • »
    »
    67 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    talk is cheap, share code.

    → Reply
  • »
    »
    57 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lol no. You can maybe pass the current testset if you are lucky but it's not "solving".

    → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Bro C was just too difficult for me.

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
94 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
31 minute(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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;

→ Reply