Theo830's blog

Codeforces Round #912 (Div. 2)
By Theo830, 13 months ago, In English

Γεια σου (Hello), Codeforces once again!

Adam_GS and I are glad to invite you to participate in Codeforces Round #912 (Div. 2) which will take place on Nov/30/2023 19:35 (Moscow time). Note the unusual start time of the round. As usual, this round will be rated for participants with rating lower than 2100.

Problems were created and prepared by Adam_GS and me. We tried to make them interesting, with short and clear statements. We hope that you will enjoy them!

I would like to thank:

  • ScarletS for amazing coordination of this round.
  • Adam_GS for joining as an author after testing the contest.

You will be given $$$6$$$ problems (and one subtask) and $$$2$$$ hours and $$$15$$$ minutes to solve them.

The score distribution will also be announced shortly.

Good luck and have fun!

UPD1:

Score Distribution: $$$500-1000-1500-(1500-2500)-2250-3500$$$

UPD2:

Editorial

UPD3:

Congratulations to the winners:

Div2:

  1. DoIodu123

  2. 69JohnMouse69

  3. transfeft

  4. vflower

  5. Top2Greece

Div1 + 2:

  1. Um_nik

  2. ecnerwala

  3. Ormlis

  4. tourist

  5. noimi

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

Comments Comments (183)
| Write comment?
»
13 months ago, # |
  Vote: I like it +33 Vote: I do not like it

As a tester,the problemset is superb!Hope you enjoy it :)

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

As a tester , I wound recommend to read as many problems as you can

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    As a tester, I would also recommend solving as many problems as you can.

    → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +61 Vote: I do not like it

Nice to see a round from a person(Theo830) who was sitting to my left on IOI2023 :) And a Person(Adam_GS) Against whom I played Table tennis :))

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

As a tester i can say that the problems are fun and interesting with a Cypriot twist ;)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone ^_^

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

Tomorrow I will understand how bad doing contest late(like Chinese).

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

I might give this round and solve D1-D2

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

According to score distribution, D2 >> F .

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

As a tester, I wish you all good luck!

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +63 Vote: I do not like it

As a tester Cypriot, I hope that statements are short and pretests are strong, making our tiny island proud!

ps. I will be competing so if I lose rating Theo830 pls make it unrated

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

As a tester, I confirm the problems are interesting... hope y'all have a positive delta!

→ Reply
»
13 months ago, # |
  Vote: I like it +14 Vote: I do not like it
Div.2- F
→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Div.2- Fs are usually easily solved by most IGMs in contest, furthermore, they are usually GM level. I hope that such a group, to whom Earth puts all their faith in to solve any problem, are not only lowly GMs, so this should be factually wrong

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

    The fact that there is no account with username avengers makes me sad.

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

My sleep and the contest are at crossroads today. I will choose the contest.

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

GLHF

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

Guess — D1,D2 can be dynamic programming with varying constraints.

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

As a tester

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

As a tester, certain problems are, for the lack of a better word, based.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

mohdabuzaid15

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

At least i can blame sleep deprivation if i mess this round up

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

The start time is 00:35 for me, so I can sleep well

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

    The start time is so late to me: 23:35=)), I can't sleep tonight if I fail in this contest

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The timing of this round is awful for Chinese students, I hope I won't be late for class the next day

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

    Let's compete and see who do better this round tomorrow my school too

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

contest >> sleep >> university exam

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

    Agreed! Somehow, my love for contests grows twofold during exams. With an exam tomorrow, this contest will surely be my doom, but a beautiful doom nevertheless..

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

    literally me rn. I've got an exam tomorrow and 0 motivation to study

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

    contest >> sleep >> The first class at 8：00（+8）

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The first, I will be giving a contest at 10:05pm(India)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi

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

As a farmer, I mean tester.

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

Problem D1

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

W cyprus round

orang soon?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems. I got 5 wrong answers and wasted 1 hr for a simple integer overflow bug in D, could've been a good contest for me.

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

    How to counter it?

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

      There are a couple of ways:

      • Use 128 bit integers if you can, though I wouldn't recommend that as a great practice as such.

      • Consider the given problem: I counted the "sum of required moves" and compared that to the number of allowed moves. Here, individual elements could take upto ~1e18 moves for large bits and considering that there are ~1e5 numbers, the sum could be as large as ~1e23. One way to avoid the overflow is to stop adding to the "required" variable once it exceeds the "allowed (k)" variable, just add an if statement (or alternatively, use min(required, k + 1)).

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

      Keep a backup of the remaining k and do the operations for each bit in an online fashion, i.e, don't wait to accmulate need for each element and then check if $$$k > need$$$. Instead, keep on subtracting from $$$k$$$, and track whether the operation was a success or not. If it wasn't, overwrite it with the old $$$k$$$.

      It is essentially the same as finding a missing number from the set $$$1, 2, 3, \times n$$$. If you do n*(n + 1)/2 - existing_sum, you face overflow issues, but if you do it in an online fashion, where you run a loop, and in each iteration, add $$$i$$$ but subtract $$$a[i]$$$, it'd work.

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

        Since all numbers start < 2^20, can't we just check if we have enough operations to get all numbers to 2^20? If so, isn't the strategy to split the remaining operations equally among the elements, i.e. the max would be (2^20 + (remaining ops)//n)? I thought there should be no need to check "required moves" for bit spots above 20, but maybe I'm missing something.

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

          Consider a single element, say, 1. It is true that it starts with one bit, but if $$$k = 10^{18}$$$, then new bits would appear.

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

    Can relate so hard to this ;_; I faced the same issue, assuming you're talking about the "long long overflow".

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

      But how in this particular problem long long can overflow? Long long is 2^64

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

        no of operations req to set ith bit in all elements.

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

      Same deal here, but I got FST as my punishment.

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

$$$E$$$ was easy to solve, but hard to implement. Thanks for cool tasks!

UPD. After checking some submissions, i can say that i am just noob and E wasn't hard to implement:)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

balanced contest with good problems

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

What the fuck is a pretest number 15 anyway

Man I had such high hopes for D2, unlucky

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

    What was your approach? It's clear that we keep the amount of steps for each i to get all numbers to i-th bit and iterate from the leftmost until we can subtract that amount from k. But then how do you find the remainder bits that also will be part of the answer?

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

    I suspect its the first max constraints test or similar.

    I coded a weird approach without realizing it was actually still $$$O(q \cdot n \cdot \log(10^{18}))$$$ in the worst case and it reaches pretest 15 before failing.

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

      What is weird, even if it is some maxtest, my verdict is not TL

      Unless I have overflow somewhere in my code (unlikely)

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the approach for C?

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

    i solved it using suffix array

    if the suffix sum is negative then it is better to merge it with previous else keep it in a new subarray

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

      ah damn I feel like I shoulda thought of that. Thanks

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

Nice E!

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Solved A,B and C. But I feels C is slightly easier than B

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Problem C and Problem D in CF EDU 66 are the same actually, isn't that enough to make this round UNRATED?

Problem D code
Todays Problem C code
→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    They are slightly different. One asks for a specific number of sub arrays and the other doesn't.

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

    They aren't the same actually (today's C allows for any number of subarrays, that EDU D requires $$$k$$$ subarrays), but the solution ideas are still almost the same (reduce the problem to sum of suffix sums).

    But no, rounds aren't made unrated because of repeated problems. Only copied problems make rounds unrated. If the problems were similar on accident, the round is kept rated.

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

    Even if they were the same, I don't think the contest would be unrated. In contest 1898, B is a classical problem appeared on other websites and D is an easier version of https://mirror.codeforces.com/contest/1513/problem/F. But the contest is still rated.

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Stop it. There are more than 20000 problems, for each problem you can find simular. But if you really search every problem, for which reason you participate in contest...

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

Come on!! The solution to Problem B was uploaded on Youtube around 40 minutes before the contest ended. That would explain the sudden rise in submissions (700+) on Problem B in the last half hour. Disappointed ://

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    so I can assume, you've googled it........

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

Not sure about visiting Cyprus after this contest

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

Great problems! Keep it going. Would love to see a div1+div2 from you next time!

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    We are planning to make a div1+2 together soon™

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

E is a really cool problem, I love how the winning condition is so simple and easy to prove.

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

Any hints for D2?

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

    I tried separately calculating costs to set all bits going from highest to lowest, then calculating the cost to set all lesser bits after I set the i-th bit in all numbers.

    For yet unknown to me reasons, this approach does not work, or maybe I haven't anticipated overflow somewhere in my code.

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

      Yeah, I might have a suspicion why this solution won't work. So when we are searching the first bit that the final answer will contain, we do not consider that some of the numbers have it set to 1. That's why when we calculate the "lesser" bits, we do not actually sure if all the numbers have a suffix of zeros. (cause from some of them we did not subtract anything at all)

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

        Logic of my solution is something like this:

        • If all numbers share same leftmost bit — nothing happens, I look further
        • If only some numbers contain it — I don't touch them at all. Those, that do not contain that bit — I erase the suffix of such numbers (to calculate min cost)

        So, if some bit has come before, I either don't do anything with the number at all, or that bit has to erase any lesser bits anyway

        I couldn't come up with a counter example myself, I don't know if this is the part in my solution that is wrong, but I did have such concerns during the contest (but I chose to believe that my guess is correct)

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

          It sounds like this solution is $$$O(32qn)$$$...

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

            It's actually only $$$O(64^2 \cdot N + 64 \cdot Q)$$$

            Where $$$O(64^2 \cdot N)$$$ part is precalc

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

        I've explained it a little bit messy, but hope you've gotten it.

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

      If you change number x at some bit i, then you need to update the cost function for other bits

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

        That's why I have an array costs — initial cost to set bit $$$i$$$ in all numbers, and 2D array post_costs — the cost to set any bit $$$j$$$ that comes after $$$i$$$

        UPD.: nvm, I see how my solution is failing, I can't just calculate costs taking the initial bit that I've set and looking at the costs to set lesser bits.

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

          How are you handling this post_costs, I can't figure out anything except O(nlogA) per query.

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

            I tried doing precalc, but the way I'm calculating the costs later on when answering the queries is not correct.

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

    I had the idea to optimize the D1 solution using a bitwise trie. Same idea, but you traverse the bitwise trie which contains some additional information.

    I didn't manage to implement this, so could anyone say whether this is the right idea?

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      No. I thought about this idea on the contest and saw, that when we have to go to the left son in our trie(when we calculate the answer), we also have to know all information about all subtrees of the right son. We cannot maintain full information about subtrees of the right son, because it requires some additional memory and time :(

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Oh. Well then I look forward to seeing the official solution!

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

Ahhhh....Thursday....watching my favorite anime characters and my rating go down....what can be better?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any hint for problem C ?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the idea in problem C?

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

    If you start a new subarray whose left end point is i, then the change in answer would be the suffix sum: suf[i]

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can i find official solutions for this contest ?

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

    they will update the contest post with editorial after some time ( hopefully soon )

    you can check posts for previous contests, you will see the editorial link to understand how it looks

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved B but I don't know why it works, hopefully, system test passes :D

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

    may i see your solution?

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

      so I just did AND of every row ( excluding the diagonal element ) and printed that as the answer after checking if it forms the grid

              int ans[] = new int[n];
 
        for (int i = 0; i < n; i++) {
            int and = (1<<31)-1;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                and &= arr[i][j];
            }
            ans[i] = and;
        }

      after this, I just tried to create another grid ( not explicitly ) and checked if it was the same as the original grid, if NO, I said it is impossible, but I don't know why it is impossible.

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

        ok it passed, I am lucky, hopefully editorial explains it well

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

        oh same solution as me but whats this int and = (1<<31)-1; mean?

        it make you can AND in the first round of loop?

        because i did this

        vector<int> ans(n,-1);
for(int i = 0; i<n;i++){
    for(int j=0; j<n;j++){
        if(i == j)continue;
        if(ans[i] == -1)
           ans[i] = M[i][j];
        else
           ans[i] &= M[i][j];
    }
}

        Im not good at bitmask sry.

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

          They are turning on all bits but leftmost bit (which is the sign bit).

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

          oh so I started with the first member being arr[i][j] .. but it was 0 when i == 0 and j == 0 so I didn't know what first value to choose

          this and value is a binary number with 31 1's in it, which is more than any number so doing AND with it will give back the input number

          why is your whole row not zero for the first row.. because arr[0][0] is 0 so and first row will always be zero in your case.

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

            sorry I'm in a bit of a hurry mb

            this is my B solution here

            but i do from every top and right number of M[i][i] that i just realized top of M[i][i] is the same as left of M[i][i]

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

        Yeah same, I applied same thing and don't have concrete proof of why it works

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

misunderstood problem C summation (len of subarray_i) * sum_i :(

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

got AC in problem C without knowing what exactly I was doing LOL. Maybe it will be hacked

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

If you want to build intuition for problems like today's C. Theofanis' Nightmare, try upsolving 1132F: Clear the String. I was lucky to have upsolved it very recently and the idea instantly clicked :) (I've also added hints for 1132:F if you don't want to read the editorial.

How does intuition from one transfer to the other?

Submission

→ Reply
»
13 months ago, # |
  Vote: I like it -10 Vote: I do not like it

What is the intuition behind Problem B?

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

    It's the fact that $$$0 | x = x$$$ and $$$1 | x = 1$$$ for $$$x \in {0, 1}$$$

    This observation is enough to solve the problem.

    More Hints
    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      You probably meant to say that $$$0 \mid x = x$$$ and $$$1 \mid x = 1$$$ apply for $$$x \in \{0, 1\}$$$.

      ($$$\oplus$$$ is bitwise xor, not or)

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

Amazing round, loved solving the problems!

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

I overcomplicated C to a stupendous degree. Looking at everyone else's submissions, simply going from the back was enough. I instead viewed it as $$$\text{psum}[a_1] + 2(\text{psum}[a_2] - \text{psum}[a_1]) + 3(\text{psum}[a_3] - \text{psum}[a_2]) + \dotsc + k(\text{psum}[a_k] - \text{psum}[a_{k-1}]$$$, then expanded it to yield $$$-(\text{psum}[a_1] + \text{psum}[a_2] + \text{psum}[a_3] + \dotsc + \text{psum}[a_{k-1}]) + k \cdot \text{psum}[n]$$$,

then I iterated over $$$1 \leqslant k \leqslant n$$$ and chose the $$$k-1$$$'th minimum values of the prefix sum in order to minimise $$$\text{psum}[a_1] + \text{psum}[a_2] + \text{psum}[a_3] + \dotsc + \text{psum}[a_{k-1}]) + k \cdot \text{psum}[n]$$$, and summed them.

The way I did this was sort the prefix sum and create ANOTHER prefix sum for that prefix sum. It got pretty damn hectic.

235105543

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

    Thank to your explanation. My friends did like you as well but I don't understand until your comment LOL. They used only about 6 minutes, whereas traversing backward cost me 1 hour to come up with

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D1 using binary search?

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

    yes, but cost function can overflow long long if not careful

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

      can u plz explain your logic

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

        Try greedy from highest set bit to low. If it is possible to make all $$$a_i$$$ have the bit set with no more than $$$k$$$ then do so. Here we binary search the highest bit possible, though a loop may be sufficient. Edit: I don't think it is correct though, you can try reading editorial of this problem.

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

          Why do you need binary search? Just iterate the highest bit form high to low.

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

            That's true. In fact, my approach is probably wrong.

            Edit: I changed to loop and got accepted, my hubris :((

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

Legit random solution for F or weak systests? (Enjoy to hack)

Add all vertices to the set of answer. Repeat the following sufficient amount of times:

  • Find minimum difference between to vertices in the set
  • Randomly delete one of them, and add all vertices incident to it to the set

https://mirror.codeforces.com/contest/1903/submission/235123989

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Hacked with a bipartite graph, when there is an edge between two nodes if they have different parity.

    The answer is $$$2$$$ but there is almost no chance to find it.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tried solving D1 using this approach: While iterating from higher order to lower order bits, say you are at bit bit. Then, you check the current bitwise AND for that position. If it's not one, and we can make it 1, we should. So, for every $$$a[i]$$$ which doesn't have the bit position set, we set it. To set it, we look at its bit - 1 bit. If it is set, then we need to add $$$2^{bit - 1}$$$ (i.e, we are borrowing from the neighbor while clearing the neighbor's bit). If the neighbor is not set, the cost has to be $$$2^{bit}$$$.

Can anyone please point out the flaw with this strategy?

Submission

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

    Suppose the bit-2 bit was set, then you need to add $$$2^{bit} - 2^{bit-2}$$$. In general, you need to check all the bits with lower value than the current bit, not just the next one.

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

      Ooof, how did I miss that? Thanks. Fixed Submission

      I guess I got too involved with figuring out the borrowing strategy that I overlooked this simple fact: Each operation only increases the value by 1, so if we want to turn on the $$$i^{th}$$$ bit, then there is only one number that we'll reach first before others, i.e $$$2^i$$$ (pretend the higher order bits are zero). And also, there's just one strategy to go there, because $$$val + cost = 2^i$$$ implies that $$$cost = 2^i - val$$$.

      Since, any number can be represented as $$$\sum 2^{set\_bit\_index}$$$, we can clearly deduce the cost is $$$2^i - \sum 2^{set\_bit\_index}$$$

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

Problem D1: week test case submission case:

1 1

1

0

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I try to solve D2 with Trie but failed, does this problem solvable with Trie?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I right in that the only thing that matters in E is $$$(s_x \oplus s_y) \mod 2$$$ and whether there is more ones or zeros among $$$(x_i \oplus y_i) \mod 2$$$? If so, I love the problem, but I hate what it did to my rating haha

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

    Yes.

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

      I can't tell you how salty I am that I only got this like 5 minutes before the contest ended... It's a really nice problem though. Congrats on reaching CM by the way!

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

I got stuck in problem E because my answer is choosing "First" while the testcase says "Second" and I'm trying to figure out what is wrong in my idea while it's all correct.

So I just want to say that the most most stupid thing you can do in a contest as a problem setter is to put a testcase in a problem and say that this is not the optimal solution in the description.

I don't have to read the description cool ... and I don't have to search in all the page for a fool note.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Can't agree more! Especially comparing it to this problem. (

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

    same here...

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

    Pretty much in every interactive task no testcase has the optimal solution in it. Also, it's never mentioned that the presented interaction is optimal/not optimal, so I think there should be no problem.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Of course the output will not be the optimal solution, it's obvious I think. But the answer here is incorrect so this is a different case.

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

    Interactive problems are often like this , that's why I don't really read the sample's interaction

    → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Sounds like skill issue honestly.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good contest

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest and nice problems ! Special thanks for problem E :)

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

You can do divide and conquer on queries in d2

Crucial observation is that if we add to a certain number to make bit B on, every bit below it turns to 0, which means for future steps, the adding calculation is straightforward. I call these numbers "stragglers".

The idea is that for bits > (highest possible bit of MAXAI), either we kill or don't kill all the bits. If we kill all the bits, every number is a straggler, so it becomes easy to calculate. Else, the array stays the same. So no extra memory needed at this step.

For bits <= (highest possible bit of MAXAI), we actually care about the array. If we don't kill all the bits at this step, we store A. If do, we need roughly sz(A)/2 elements in the worst case. At least it seems.

However, notice that although the array A is big, after we kill off the biggest bit, there are only sz(A)/2 possible values. So actually, yes, at each recursive step, we only need sz(A)/2 + sz(A)/2 = sz(A) memory, so after bit <= (highest possible bit of MAXAI) we only need MAXAIlog(MAXAI) memory total.

Queries can be updated naively because the depth of the recursive calls is log(K) and we split it up into disjoint intervals, so each query is only touched log(K) times

This is my thoughts after discussing w/ adamjamil after contest. In contest, I had such a scuffed impl since I sort of handwaved the argument above, leading to a lot of extra constant factors that weren't needed. But here is the final impl, is pretty fast :) submission

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking at my graph I think I'm really a purple coder.

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

Problems were really high quality

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

Can somebody tell me why are samples in E not correct? I lost 20 minutes because of that, it is so stupid. There were few more technicalities that were so dumb. Overall, I liked the problems. Great round, better than last few.

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

    There are samples only for input example :)

    They haven't any relations with correct tactics for the problem.

    My solution goes first in the first testcase of sample)

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

      I get it, but just imagine implementing the solution that works, running it, and getting First, Second as an output, while the sample output is opposite. If both players play optimally, the winner is uniquely determined. I don't see a reason for doing this.

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

        Reason is to don't give any hints to participants.

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

          It could be done by giving a trivial test case. On the other hand, the solution is enough complex that it is very difficult to spot any pattern based on samples only.

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

Some individuals have mentioned encountering integer overflow issues with their D1 and D2. A helpful workaround involves utilizing a long double instead of an int64_t, as long double can manage cases like 1e25 or 1e1000. It's noteworthy that you can still compare a long double with an int64_t, and if the situation permits, the long double value remains equivalent to the int64_t value.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Greetings from Greece! The problems were interesting, congratulations.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

After working through the problems (since I didn't solve any in-contest), here my thoughts:

A: nice easy problem (I misread as exactly K at first, and thought I was going to have to implement something more challenging)

B: a nice problem, perfectly fits the expected difficulty

C: really nice problem, 1 observation about how to rewrite the sum, then easy short code

D1: nice problem D (fairly standard though)

D2: hard for problem D, but a really good problem in my opinion

E: nice interactive problem, observation felt the same difficulty as C to me both E and C basically just involved rewriting some summation *slightly, and then implementing something relatively simple

F: another really nice problem in my opinion, perfect fit for it's difficulty I had trouble setting up the implications in contest, but after seeing some solution and learning a very clean way of doing it --particularly from ecnerwala's solution

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My favourite problem : E

→ Reply