Hori's blog

Codeforces Global Round 27
By Hori, 7 weeks ago, In English

Hello, Codeforces!

We are pleased to announce the resumption of the Global Rounds. Thanks to XTX Markets for supporting the initiative! In 2024, we will hold 4 such rounds. The series results will take into account the best 3 participations out of 4.

On Oct/27/2024 17:35 (Moscow time) we will host Codeforces Global Round 27.

Codeforces Global Round 27 marks the third round in the 2024 series of Codeforces Global Rounds. These rounds are open and rated for everyone.

The prizes for this round are as follows:

  • The top 30 participants will receive a t-shirt.
  • 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.

The prizes for the 4-round series in 2024:

  • In each round, the top-100 participants get points according to the table.
  • A participant's final score will be the sum of the points they earned in their 3 highest-placing rounds.
  • The top 20 participants across the series will receive sweatshirts and placement certificates.

We extend our gratitude to XTX Markets for supporting the global rounds initiative in 2024!

The 8 problems were authored by our 8 authors: Benq, lunchbox, oursaco, sum, willy108, Hori, turtletortles, and last but not least ChatGPT.

We would also like to thank:

Round Information:

  • Duration: 180 minutes
  • Number of problems: 8 problems with 1 subtask
  • Score distribution: 250 — 500 — 1000 — 1500 — 2000 — 2250 — (2250 — 2000) — 4500

We look forward to your participation!

UPD: Congrats to the winners

  1. Kevin114514
  2. 275307894a
  3. jiangly
  4. JoesSR
  5. ksun48
  6. turmax
  7. dXqwq
  8. hos.lyric
  9. Rewinding
  10. jiangbowen

UPD2: First solves

A: dXqwq
B: hos.lyric
C: dorijanlendvaj
D: riantkb
E: turmax
F: taeyeon_ss
G1: taeyeon_ss
G2: Kevin114514
H: orz (only in contest solve!)

UPD3: Editorial

Announcement of Codeforces Global Round 27
  • Vote: I like it
  • +467
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

As a setter, I was unable to get a picture of myself eating [] before this blog was posted.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

As a tester, I am glad willy108 was unable to eat [] before this blog was posted.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

As a tester, love the contest, love the problems!

and orz willy108

→ Reply
»
4 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

As a setter, I can confirm this contest is one of the contests of all time.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

orz

→ Reply
»
4 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

I love newbies just as much as I love ChatGPT

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

    im a newbie, could u plz help me getting z best benefit of this "codeforces" , i am really confused with it ..

    i have some questions i just need u to awenser it for me :) 1- where and how to find problems to solve Gradually? 2- when i will be ready to enroll one of these contests that is published on here? 3- how much time should i spend here a day? thanks in advance :)

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

      First of all you are not a newbie :)

      1. problemset is right there. Start from 800 rated problems. (b/w I also use USACO and Cses problemset)
      2. you came to cf you are eligible.
      3. hmm.. i never counted probs or no of hrs. we are just starting here so need to spend some good amount of time.
      → Reply
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

BENQ ROUND ORZ

→ Reply
»
4 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

TAKE THIS ROUND

→ Reply
»
4 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

As a tester who has not tested yet, the problems are very good and you should take the contest!

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    orz

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

    If you hasn't tested, said that it's good, but in fact it will be bad, I'll find you.

    → Reply
»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Hope to see tourist register for this contest.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

orz

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

keys is gonna cook

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

Orz

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

orz Sugar_fan

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

Chatgpt authored a problem!??

→ Reply
»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

non-negative votes for comments, blog.

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

Benq round orz

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

Funny time is comiing

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

How can ChatGPT be an Author? :). How can I make questions using ChatGPT?

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

as a tester...

→ Reply
»
4 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

As a tester, I want to orz willy108 for also playing Arknights.

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

Is there a rating?

→ Reply
»
4 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

Would unrated registration will ever be available on div.1s? It seems like this is the 4-th div.1 that could have unrated registration enabled.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

qp

→ Reply
»
4 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

Hoping to become purple after this contest!

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

lesgo

→ Reply
»
4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

wanna see tourist vs jiangly today

→ Reply
»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Hoping to see jiangly reach tourist!

→ Reply
»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope to reach expert today!

→ Reply
»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Excited to see jiangly reaching 4000 & the new name for 4000<=.

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

It was wriiten the problems are made by ChatGPT.Is this a person or literally ChatGPT ???

→ Reply
»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

tourist has registered for this contest. His rating is gonna change today. I hope he will cross $$$4100$$$

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    That's not possible cuz he will get at max +70 as rating increase is very slow at that level

    → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    He is in a position where if he didn't get the first position among RED coder's he will get mines(-)...

    → Reply
»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, I really hope yall enjoy this round!

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

omg ChatGPT has the rating better than me :penguin:

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

will this be rated

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

So you are saying ChatGPT is an expert in codeforces.

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

Best wishes

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

it is rated or unrated ??

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

So, ChatGPT is expert?

→ Reply
»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I was sweating while solving C

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

Was this rated?

→ Reply
»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

OK..Stuck on D forever with WA on pretest 2.

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

Guessforces

Nice D have to study about it

→ Reply
»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

I'm really not a fan of B, I honestly don't think I would have solved this problem in a "no internet" contest because who remembers the divisibility properties for 11...

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Why do you need it? I almost immediately understood, that the solution is written on the screen.

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

    Note that $$$33\cdot10^n$$$ is divisible by $$$66$$$.

    → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I dont think we need the divisibility properties of 11. We can only use 3 and 6 as digits, and the number is to be divisible by 66, so the number must end with 66.

    Then you need to add 33 * pow(10, x) always, and you cannot have 9 as a digit in the resultant number. So, by logic we have answer ->

    for n >= 4: concat(333333....(n — 2)times, 66) when n is even and concat(33333...(n — 4)times, 6366) when n is odd.

    Then you can handle cases for n < 4.

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

    Neither did I. Fun part: If you divided the solutions in the tests by 11 you'd get something very interesting.

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

    when I looked on "n = 500", I started observing the testcases on the screen and I got it it only about 3s.

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

    Sample just gives the answer. You can also just dp with the remainder, no need of any math.

    → Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

god D made me so pissed, I was only getting the last number from the last test wrong i changed all the MODS, reviewed all of them and still wrong

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

    u must be using mod somewhere where u shouldn't be using it

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

    Nah, I can assure you it is not that easy. Most probably, your algorithm doesn't even work on case #2 in the sample. Just check it.

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

      well I think my answer had some consistency I accumulated the distance from every number from the very least significative Bit to the first Bit, and thats the number of times I could multiply a number by 2. Then I right shifted all the numbers the amount of times they could be shifted, and for every query, I get the preffix sum of all shifted numbers + the max shifted numbers left shifted the amount of times I accumulated b4

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

rip in piece i got unlucky on D (first try AC but i way overcomplicated it)

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

    Can you verify if this approach is ok I maintain a 2 stacks one with the value and one with the potential

    the value is essentially the number that remains after we remove all the 2 from it if the last number is greater the the value of the stack we maintain we remove that and add it's potential to the potential of the current number ,and subtract (last_elem-1) * (2^its_potential) to the ans and at the end we add curr_elem * (2^curr_potentail) to the ans and stack

    cache the 2 ^ power into and array

    I spent 1 hour + on this still wa on tc 2

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

      There's a case when the power of $$$2$$$ is too big, you need to handle correctly.

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

        I think I did that

        I initialized a big array with powers of 2 and applied mod on it

        Have to see what that elusive test case is tho!

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          ← Rev. 4   Vote: I like it +1 Vote: I do not like it

          Maybe the way you use modulo. Take a look at the line 48. When you subtract, you need to add it to modulo instead of just using % operator.

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

            Just checked my submission , You are right

            while multiplting I naively assumed that it will stay in limit but it did not

            I did c += (b*d) => overflow occured

            instead of c += (b*d)%1000000007;

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

I feel so dumb, Forever stuck on D, Need to improve on my debugging and analysing skills

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

Can you please tell us which one chatGPT made?

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

Too weak for C again... GG

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

How to solve D?

→ Reply
»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

ObservationForces

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    That is what CF is supposed to be, yes.

    → Reply
»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Most of the CM / Experts(including me) tried a lot to pass (bruteforce + ternarySearch) to pass pretests for problem E.

E has some sort of

This pattern for 3rd test case

There are multiple local minimums. How to find the optimal local minimum ?

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

    Use sqrt-decomposition. You can refer to 1954E - Chain Reaction

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

      ohhh, Understood. So for each square-root, block, we need to apply ternary search. Is that right ?

      ( haven't looked at your solution, Want to solve on my own. Will check your solution, if I can't solve it ).

      Thanks for the hint !

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

    you dont "find" the local minimum, you bruteforce!

    let A be a chain of k operation 1s and 1 operation 2 (in that order)

    optimal answer would be A repeated some amount of times -> op1 some amt (must be <= k) -> op2 some amt

    brute force through number of A repeats -> sqrt(z/k)

    if k is small (k <= 1e4) -> number of op1s is bruteforceable -> sqrt(z/k)*k = sqrt(zk) but k <= 1e4 so at worst it's 1e6 per case

    if k is large then the number of op2s so that number of op1s is >1e4 is also small (i wasnt able to exactly calculate the amt but it should run fast enough)

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

      Okay, I tried something similar, but couldn't pass.

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

        prob some bad implementation (or youre missing some optimizations) cause mine ran in ~200ms

        → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Check my 288346163. I used ternary-300 optimization to pass it. I will write a blog about it soon.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks a lot, waiting !!!!

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

      Is this guaranteed to find the global min? It looks heuristical

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Of course it is heuristical. If it wasn't, we could find global minimum of a random function. It works because the function is close to unimodal.

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

          got it. I'm wondering if there's a condition where it will provably find it.

          like maybe if f(x) is almost unimodal and there exists some unimodal function g(x) s.t. abs(f(x)-g(x)) < C then it'll find it

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

What does Authorized by ChatGPT means

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

how to solve C?

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

    find patterns in sample testcases

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

      Well, I didn't find any pattern. I did simple maths. you only care about last 3 to 5 values last values

      1. If N % 2 == 1, you care about only last 4 values.
      2. If N % 2 == 0 and N is power of 2, you can about only last 5 values.
      3. Otherwise, you care about last 3 values.
      → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if odd then obviously the max you can get is just n, and if not odd, then you can set all bits that are present in the permutation, by doing the same thing as with n-1, but just adding result^(n-1) at the en

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

      so for odd I just have to print 2 1 3 4 5 6 7 8.. but what for even?? tbh I got destroyed by this C :( too tough for me

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

        You print whatever at the beggining and at the end print 1 3 n-2 n-1 (res^n-1). where res is the highest set bit in n times 2 — 1

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          ahh okay I upsolved it with little different approach that if n is a power of 2 or n is odd then max answer we can get is n and so I printed it like 2 1 and then 3,4,.. else i took the highest power close to n which is less than it call it x I printed 2 1 3 4 till x-2 and then from reverse I printed n to x-1

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

        For even $$$n$$$, the intuition is as follows,

        First of all you can show $$$k$$$ can always be $$$2^{\lfloor\log_2 n \rfloor+1} - 1$$$ if $$$n \geq 4$$$ and we are given $$$5 \leq n$$$

        Now for explanation, consider n = 10. Let $$$p_n = 2^{\lfloor\log_2 n\rfloor} = 8 = 1000$$$.

        We know $$$k = 15 = 1111$$$, so there must be an $$$x_n$$$ such that $$$8 | x_n = 1111$$$. So, $$$x_n=0111$$$ (not $$$1111$$$ as that does not exist in this permutation).

        Now, we want $$$p_{n-1} \land x_{n-1} = 0111$$$, thus $$$p_{n-1} = 0111 = 7$$$. Now we can fix $$$p_{n-2} = 6 = 0110$$$ and $$$p_{n-3} = 1 = 0001$$$ as we can observe their OR gives us $$$p_{n-1}$$$.

        Finally we just need to ensure that $$$x_{n-3}$$$ is odd so $$$p_{n-3} \land x_{n-3} \neq 0$$$. This we can do by letting all even indices from 1 to $$$n - 4$$$ be odd and odd indices from 1 to $$$n - 4$$$ be even. Thus at each OR step, we would be ORing with an odd number. Since $$$n$$$ is even $$$n-3$$$ is odd. So if we are ORing at $$$n$$$-th step, we are ANDing at $$$n-3$$$th step. But $$$n-4$$$-th step would have an odd number as per our construction so $$$x_{n-3}$$$ would be odd!

        Final permutation looks like this: $$$\text{odd}_1,\ \text{even}_2,\ \ldots \ \text{odd}_{n-4},\ 1,\ n-2,\ n-1,\ n$$$

        Here

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

nice problem D need 2 more minutes to submit :(

→ Reply
»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

In problem D, "Since this problem is too easy" killed me.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

If there's no elegant solution for B and C then they are not good, since it's casework for odd\even basically. D and E on the other hand are great, thank you.

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

    I thought there must be some proof and did not see the standings assuming it was hard, i fcdkup :)

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

    To be fair, C really just boils down to solving for $$$2 \cdot \lfloor \frac{n}{2} \rfloor$$$ so idk if it is fair to call it casework.

    → Reply
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

i hate overflow :(

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

For C, I just got the pattern for $$$n > 4$$$. if $$$n$$$ is odd, a permutation of $$$[2, 1, 3, 4, 5, \dots, n]$$$ always gives the max answer which is $$$n$$$. For even the maximum answer will be $$$2^{p+1}-1$$$, where $$$p$$$ is just the number of the leftmost bit, and it's still the same pattern but $$$2^p-1$$$ should be the last number. but if $$$n$$$ is a power of $$$2$$$ it should be the last number after the $$$2^p-1$$$. I want proof of this.

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

I solved C by guessing but got stuck on both D and E. I enjoyed the contest though, D is a great problem in my opinion. I think I was missing the case where it was a situation like [4, 4, 11, 2, 3], and the max array would be [1, 1, 176, 1, 6], not [1, 1, 176, 2, 3].

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

Can anyone Share Idea of problem C ?

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

    Try to get $$$2^{k}-1$$$ for even numbers.

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

      how to get the permutation that fits 2^k -1?

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

        • If $$$2^{k-1}<n<2^{k}$$$, the array ends with $$$[2^{k-1}-1, (2^{k-1}-1)\,\text{XOR} \,\text{lowbit}(n),n]$$$. The $$$\text{lowbit}$$$ is to ensure that $$$n$$$ can fill the zero bit that the previous item of $$$n$$$ causes.

        • If $$$n=2^k$$$, the array ends with $$$[1,3,n-2,n-1,n]$$$. $$$1$$$ is to fill the last bit that $$$n-2$$$ lacks

        • If $$$n$$$ is odd, note that $$$a\,\text{AND}\,b\le a$$$, so $$$n$$$ itself is the maximum and you can just put $$$n$$$ after your even array to reach the maximum.

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

          Thanks, I got the even/odd observation. But miss the [1,3,n-2,n-1] could be a thing... I was desperate to code a dfs and pray that I have enough luck but I guess I don't

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

        It's always possible. There is always a number m < n such that n|m gives all ones in binary so last but one should be that m which is actually odd. So its now reduced to odd case from here except for edge cases for numbers less than 5

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

Why I found D easier than C :(

IDK why it was happening while doing C my brain not Braining I was not able to focus on the pattern.

Damnnn any ideas ?

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    How to solve D?

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

      i did dp till index i such that total power of 2s <= 32 and then do greedy aferwards
      can't submit during contest, but let see if that's correct or (hopefully) atleast the idea is correct.

      → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For large enough ($$$\geq 8$$$ works) even $$$n$$$, you can just end the permutation with $$${1, 3, maxpow-2, maxpow-1, n}$$$, where $$$maxpow$$$ is the greatest power of $$$2$$$ that's $$$\leq n$$$, which ends up with having all bits that are set in at least one number $$$\leq n$$$ on, so the answer is $$$2*maxpow-1$$$. A greater answer is clearly impossible. And for large enough odd $$$n$$$ ($$$\geq 8$$$ still works), you may note that the result is bounded by the last element of the permutation, and therefore by $$$n$$$. And the result $$$n$$$ is achievable by putting $$$n$$$ at the end of the optimal permutation for $$$n-1$$$. Cases where $$$n<8$$$ can be hardcoded.

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

I am not able to solve the problems after the contest. I am getting "You can't run practice now or contest does not support practice" error.

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

    You've to wait until system testing ends.

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

      thanks for reply. how long will it take?

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

Editorial?

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

    Contest ended $$$20$$$ minutes ago. The editorial isn't usually published that early. I'm sure it will eventually appear.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      there are cases where they immediately publish an editorial

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

        There are. Not very often, and there are also cases where the editorial is published $$$3$$$ hours after the contest. I think out of the $$$12$$$ contests I participated in, editorial was published immediately twice or something like that.

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

          the fact that you almost once reached master within just 12 contests is WILDDDD, username checks out

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

            I think he is an ALT user. If not then Mad Respect. ORZ.

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

              I'm not an alt user, but I started with competitive programming (olympiads and stuff) about $$$2$$$ years before joining Codeforces, and I've been doing math olympiads even longer (which also helps).

              → Reply
»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

During this contest my mental health dropped to a new record.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

hints for F?

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

Why are global rounds always so hard :sob:

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Weak systests on E, incorrect "sqrt" decomp (~2e7 ops/tc worst case) passes in 500ms:

https://mirror.codeforces.com/contest/2035/hacks/1094322 (uphack of my own sol)

Didn't think to pick my parameter correctly. Didn't matter.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

I like the essential observation part of problem G, nice! However reading a binary search using closed interval ($$$[l, h]$$$ instead of $$$[l, h)$$$) was painful, please go learn X(

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

    I agree wholeheartedly with $$$[l, h]$$$ being painful.

    → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Pressed submit and timer ended 1 second before. Tried submitting after system testing. It was AC. :(

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

Why is the amount of wrong submissions for E more than $$$11$$$ times the amount of correct submissions, what was going on

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

    Same mentioned here.

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

    Me who submitted it 15 times: I first ran into a wrong idea that a single ternary search would work. It turned out that it doesn't work because it can have multiple local minimums. It was too late for me to carefully think of a right approach, so instead I could only try to add some extra ranges to search and hope that they are enough. None of them could pass pretests.

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

bruh, the round was sweaty to be fair. Anyway ,returned ,my expert after a disasterous div2 yestersay.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

Loved the contest, thank you! G is cool, F is nice, D is nice, E is OK, and B&C are also OK.

Missed the trivial "remove every test" case in G1 :(

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

hope to have rate soon

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

whats wrong with this approach on D? I couldn't even match the sample test cases on this one :(.

Thanks in advance.

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

    Nevermind, overlooked something in the question.

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

How to solve D?

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

My final code was edit distance 2 away from AC-ing E...:(

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Hint to D:

Let us pick $$$a_i$$$ and $$$a_j$$$ and decompose $$$a_i$$$ into $$$a_i=p_i\cdot2^{q_i}$$$ where $$$p_i$$$ is odd and $$$q_i>0$$$. Performing the operation on $$$a_i$$$ and $$$a_j$$$ is optimal if and only if $$$p_i<a_j$$$.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

Liked C a lot:

  1. Solve for evens through solve for odds, always a cool trick. I used $$$solve(2n) = [\ldots, solve(2^{\lfloor\log(2n)\rfloor} - 1), 2n]$$$.
  2. A lot of ways to solve for odds: I used $$$[\ldots, 3, 1, n - 1, n]$$$ as $$$(n & (n - 1)) = n - 1$$$ for odd numbers and $$$1 & 3 = 1$$$ that we can push to the ans as well.
  3. $$$n \ge 5$$$ is a good constraint. I hadn't to manually if cases.

Maybe a bit harder than a regular D2C, but definitely solvable (and in many approaches, whats not always a case). It's generally hard to create a good problem for position C and today it was just awesome.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Interestingly enough the answer for lower $$$n$$$ is just the identity permutation. I still decided to remove it so people didn't get confused by edge cases.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Bad decision, you should've done everything in reverse: made $$$n \geq 1$$$, made $$$1$$$ multitest in examples with $$$n=1,\ 2,\ 3,\ 4$$$ and printing identity permutations as answers for them. Doing so we would see a lot of noobies sending solutions with just printing identity permutations xD xD xD

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

      ty bro <3

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

For problem D, I didn't understand how to use the modulo. When I apply it to intermediate results, it gives me the wrong answer. If I only use it at the end, I get a TLE. I believe the numbers are getting too large. Any help?

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

    In my correct submission, I apply it while calculating answer for each index but I store numbers num = x * 2^y as (x, y) , where x is an odd number (Edit: clearly here x and y will always lie in int range as per constraints in the problem). And while comparing I use log2 of the num which is log2(x) + y, which gives correct comparison.

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

      Thank you for the explanation. but, still I didn't get why applying the modulo for every intermediate result cause a wrong answer!

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

        I don't exactly know in which steps you are applying mod, but if you apply mod and then some comparisons on some value on which mod is already applied then you should expect wrong results.

        Or else, maybe your solution which gives TLE is also wrong, just that it gives tle before detecting wrong answer in the test cases (maybe). Is there any test case which passes the TLE solution but gives wrong answer verdict on your other solution.

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

          Without applying mod on the count TLE on test 3

          Applying mod on the count Wrong answer on test 2

          so, If i'm not applying mod it works, but it gives TLE because of applying arthimetic on large number. when I apply the mod it gives wrong answer.

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

          so i realised i was applying modulo correctly but missed the 2s > 30 thing where u dont (2 ^ 2s) with the odd number, how exactly does it help in getting the correct result?

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

    Numbers quite large. So, instead of doing the multiplication, you just need to store the oddNumber, and powerOfTwo everytime you process the value. This will help in managing integer overflows ( although, in python u won't get any ).

    → Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

In problem D of this round, it has missing test cases. One missing test case that I found, which potentially could give rejected verdict on some submission:

1
3
999999986 2097152 1048576

My last submission 288365525 during contest gives correct answer for it, but my earlier submission during contest gives wrong answer. But still when I resubmitted my earlier submission 288377619 after the contest ended to check if it passes system tests, unfortunately it passed!!

Explanation of mistake in earlier submission:

My approach for above given test case:
given n = 3, and array a = {999999986 2097152 1048576} = {499999993 * 2^1, 1 * 2^21, 1 * 2^20}

for i = 1: f[a1] = a1 (obviously)

for i = 2: f[a1, a2] I first check if I can transfer power of 2 from earlier indices which have power of 2 and increase the total sum.
I check it as if last_element_having_factor_2/(power_of_2_in_it) <= current_element, then transfer the power.
Since, transferring power from a1 to a2, will reduce the total sum, so I don't do it here.
So, f[a1, a2] = (999999986 + 2097152)%1000000007;

for i = 3: f[a1, a2, a3]
last previous index which has power of 2 is a2 which is 1 * 2^21 and since 1 <= current_a3 (1 * 2^20), so I transfer the power from a2 to a3, then a3 becomes 1 * 2^41.
then last element which has power of 2 is a1 which is 499999993 * 2^1 and here is where there is silly mistake in my older submission which still passes the system test cases.
In my correct solution I check if log2(499999993) <= log2(1) + 41 , but in older submission I checked if 499999993 <= 1 * (2^41 % 1000000007), which gives wrong answer as it does satisfy the condition to transfer the power, but it should.
So, correct answer = (499999993 + 1 + 2^42)%1000000007 .
But my other submission (which passes the system tests) gives answer = (999999986 + 1 + 2^41)%1000000007 .

This modular arithmetic mistake could have been done by few (or maybe many) other users also. So Hori, would the test cases be updated and since many others might have done same mistake, would the solutions for problem D be rejudged for the contest or the updated test cases be used for further submissions only. Or test cases won't get updated as contest is over.

Edit: My flawed submission has been uphacked. I didn't know someone can uphack even after contest ends and hacking phase ends.

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

    That's a valid test case that should be in the contest. Problem setters and/or testers should have added such test cases. Nonetheless, they should add it now.

    There can be many such test cases, like
    1
    3
    999999998 2097152 1048576

    and many more, but unfortunately official test cases didn't have any of them.

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

    hm using the log seems beneficial since no issue of overflow and mod can be used when decrementing/incrementing the sum

    → Reply
»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't think D is a good question about mod.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

orz

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

Too many cheaters again today on D, submission blew up too much in the last one hour

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

    I think, D was little difficult to implement. That's why people took time to fully implement it. Even, so many Red coders submitted D in the last 1 hour of the contest. Does that mean, Red coders also cheated !

    Your assumption might be true in other cases, but IMO, today's D was actually time-consuming to implement.

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

problem D, why my code is WA ~~~~~ import sys

MOD = 1000000007

def Pow(a, b): res = 1 while b > 0: if b % 2 == 1: res = res * a a = a * a b //= 2 return res

def main(): input = sys.stdin.read data = input().split() t = int(data[0]) idx = 1

results = []
for _ in range(t):
    n = int(data[idx])
    idx += 1
    a = [0] * (n + 1)
    pre = [0] * (n + 1)
    pre2 = [0] * (n + 1)
    pre3 = [0] * (n + 1)
    Max = [0] * (n + 1)

    for i in range(1, n + 1):
        a[i] = int(data[idx])
        idx += 1
        x = a[i]
        res = 0
        while x > 0 and x % 2 == 0:
            res += 1
            x //= 2
        pre[i] = pre[i - 1] + res
        pre2[i] = pre2[i - 1] + a[i]
        pre3[i] = pre3[i - 1] + x

    a[0] = 10**18
    st = [0]

    for i in range(1, n + 1):
        while a[st[-1]] <= a[i]:
            st.pop()
        Max[i] = st[-1]
        st.append(i)

    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        dp[i] = max(
            dp[i - 1] + a[i],
            pre2[i],
            pre3[i - 1] + Pow(2, pre[i - 1]) * a[i],
            dp[Max[i]] + pre3[i - 1] - pre3[Max[i]] + Pow(2, pre[i - 1] - pre[Max[i]]) * a[i]
        )

    results.append(" ".join(str(dp[i] % MOD) for i in range(1, n + 1)))

sys.stdout.write("\n".join(results) + "\n")

if name == "__main__": main()

~~~~~

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

can anyone tell me what is i am doing wrong in my code for 4th question code---

~~~~~~~~~~~~~ #include

include

include

include

using namespace std;

int main() { long long T; cin >> T; while (T--) { long long n; cin >> n; vector nums(n); vector ans; // Store the answer for each test case priority_queue store; long long sum = 0;

for (long long i = 0; i < n; i++) {
        cin >> nums[i];
        long long power = 0;
        long long TS = 0;
        vector<long long> temp;
        vector<long long> newVec;

        // Move elements from the priority queue to temp and calculate TS
        while (!store.empty()) {
            long long Temp = store.top();
            temp.push_back(Temp);
            TS += Temp;
            store.pop();

            // Count the power of 2
            while (Temp % 2 == 0) {
                power++;
                Temp /= 2;
            }
            newVec.push_back(Temp);
        }

        // Calculate adjusted value with safety check
        long long adjustedValue = nums[i];
        if (power > 0) { // Only apply shift if power is positive
            // Check for overflow before shifting
            if (adjustedValue > numeric_limits<long long>::max() >> power) {
                adjustedValue = numeric_limits<long long>::max(); // Cap to max long long
            } else {
                adjustedValue <<= power; // Use left shift for power of 2
            }
        }

        if (TS != 0 && adjustedValue > TS) {
            // Update sum carefully
            for (long long val : temp) {
                sum -= val; // Remove old values from sum
            }
            for (long long val : newVec) {
                sum += val; // Add the new values
            }
            sum += adjustedValue;

            if (adjustedValue % 2 == 0) {
                store.push(adjustedValue);
            }
        } else {
            for (long long val : temp) {
                store.push(val); // Push back the old values
            }
            sum += nums[i]; // Directly add current number
            if (nums[i] % 2 == 0) {
                store.push(nums[i]);
            }
        }

        ans.push_back(sum);
    }

    for (long long value : ans) {
        cout << value << " ";
    }
    cout << endl;
}

return 0;

}// ~~~~~~~~~~~~~~~~~~

→ Reply
»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

why noone mentions the anime Alya Sometimes Hides Her Feelings in Russian for problem C LOL

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

After seeing D: It's doable :) After trying D: Oh hell nawwww

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

https://mirror.codeforces.com/contest/2035/submission/288461359

Could anyone tell me what exactly I’m doing wrong with the modulo operation?

My int is set to long long. The commented lines are direct multiplication and the for loop does *2 step by step.

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

like global rounds for interesting tasks

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

is system testing done till this round?

→ Reply