Ecrade_'s blog

By Ecrade_, 17 hours ago, In English

Sorry for the late editorial. Our problem setters were so exhausted with the offline competition yesterday that they really need some good rest.

Despite the unexpected and unpleasant incidents that occurred, we are truly surprised and grateful that so many of you still participated in this competition! We sincerely hope you enjoyed it!

(Gratitude for all you guys from Ecrade_: I felt so heartbroken when I heard about the unexpected issues, but seeing so many people in the comments comforting us, sharing thoughtful and positive messages that showed genuine empathy, and continuing to fully support our competition even after the wasted time, I was deeply moved. Thank you all! Codeforces truly embodies such a positive and uplifting community spirit!)

2082A - Binary Matrix
Idea: Ecrade_

Hint
Solution
Code

2082B - Floor or Ceil
Idea: Ecrade_, FairyWinx

Hint 1
Hint 2
Solution
Code

2081A - Math Division
Idea: Ecrade_

Hint 1
Hint 2
Hint 3
Solution
Code

2081B - Balancing
Idea: Ecrade_

Hint 1
Hint 2
Solution
Code

2081C - Quaternary Matrix
Idea: Ecrade_

Hint 1
Hint 2
Solution
Code

2081D - MST in Modulo Graph
Idea: newbiewzs

Hint
Solution
Code

2081E - Quantifier
Idea: chen_03

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code

2081F - Hot Matrix
Idea: 18Michael

Solution
Code

2081G1 - Hard Formula
Idea: Prean

Hint 1
Hint 2
Solution
Code

2081G2 - Hard Formula (Hard Version)
Idea: Prean

Hint 1
Hint 2
Solution
Code
  • Vote: I like it
  • +75
  • Vote: I do not like it

»
10 hours ago, # |
  Vote: I like it +8 Vote: I do not like it

Ecrade_ orzzzzzzzzz!

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

    yinianzhijian orzzzzzzzzz!

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

      Ecrade_ orzzzzzzzzz!

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

        Ecrade_ orzzzzzzzzz!

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

          Ecrade_ orzzzzzzzzz!

          • »
            »
            »
            »
            »
            »
            9 hours ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Ecrade_ orzzzzzzzzz!

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

              Ecrade_ orzzzzzzzzz!

              • »
                »
                »
                »
                »
                »
                »
                »
                7 hours ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                Ecrade_ orzzzzzzzzz!

»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

the solution in editorial for A is fine and quite understandable but i was expecting to see a proof for the claim, i personally did find it hard to see that the answer is max(r,c), yes changing a cell implies that r and c change by 1 but i dont see how that implies that the minimum number of operations is max(r,c), is there a way to construct this optimal matrix without brute force, maybe by some clever construction?

  • »
    »
    9 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    $$$\max(r,c)$$$ is the lower bound of the answer, since each time we can change $$$r$$$ and $$$c$$$ only by one.

    Greedily, if $$$r$$$ and $$$c$$$ are both greater than $$$0$$$, then we should make them both minus $$$1$$$; otherwise, let's assume that $$$r>0$$$ and $$$c=0$$$, then we can only make $$$r$$$ minus $$$1$$$ and $$$c$$$ plus $$$1$$$. This greedy strategy yields the lower bound $$$\max(r,c)$$$.

    You can personally perform the strategy on some small tests like $$$r=[0,0,1,1]$$$ and $$$c=[1,1,1,1]$$$, which might be helpful to your understanding.

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

      thanks for the reply! lets say that the lower bound is max(r,c) which makes sense if we greedily reduce r and c, but you haven't proven that it is always possible to transform the matrix into a good one by performing exactly max(r,c) operations or that there always exists a greedy solution, intuitively it feels like the greedy solution shouldnt always exist because +1 is always possible but apparently it does.

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

        Maybe you can create some small tests and apply the greedy solution on them. You may get some inspiration from the process.

»
9 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

div2A was not at all obvious to me. however, I guessed it because I try not to think very hard in div2A but was hoping for better intuitions and maybe a little more understanding of the matrix properties.

div2B seriously made me happy that this round was unrated LMAO, and that carry-over logic by looking at bits does make me understand the solution, thanks. .. although I got div1 this time but I tried to do it virtually for div2

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

    div2A seems very difficult to prove on paper, because the parity of the number of "bad rows" puts some constraints on the parity of the number "bad cols" which are themselves kinda tricky to prove

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

      yes I also figgured out some stuff with parity, but didn't do much thinking because div2A and you loose score for time... I was expecting mention about that in the editorial

      just mentioning what is this parity thing — basically non zero XOR means parity of count of 1s is odd.

      • »
        »
        »
        »
        8 hours ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I also struggled with div2B because I don't how to write ceil division mathematically (x/y+1 [x%y!=0]). But I just changed order of operation in max and min and it worked ^_^

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

          a version of ceil division which people use ceilDiv(a,b) = (a + (b-1)) / b

          here b is 2 so.. (a+1)/2

          • »
            »
            »
            »
            »
            »
            8 hours ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            Yeah I got that :) But I was saying I was not been able to prove why my approach because I was not been able to write mathematical equation for ceil division

            proof

            BTW I have taken above proof from someone's comment

  • »
    »
    9 hours ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    There is a simpler solution for div2B.

    Let $$$s_1 s_2 \ldots s_k$$$ be the binary sequence representing floor and ceil operations.

    Claim: $$$01$$$ is larger than or equal to $$$10$$$.

    Proof:

    $$$\lceil \dfrac{\lfloor \frac{x}{2} \rfloor}{2} \rceil = \lfloor \dfrac{x+2}{4} \rfloor $$$
    $$$\lfloor \dfrac{\lceil \frac{x}{2} \rceil}{2} \rfloor = \lfloor \dfrac{x+1}{4} \rfloor $$$

    Greedily sort the sequence of operations. Implement it in 10-20 lines.

    P.s. is it just me or was the round very hard? I couldn't actually solve div2B without a hint.

    • »
      »
      »
      9 hours ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      it was hard for me too. after a long time struggled so much with B.

      C was also some expectation + dp which I am weak at... :( :(

    • »
      »
      »
      9 hours ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Wow that's definitely an elegant proof! Thank you for sharing it!

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

      ok, this explanation for div2B is so cool, thanks for sharing this.

      now I feel more dumb

    • »
      »
      »
      7 hours ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      Fill in the detailed reasoning steps:

      $$$ Operation 1 : \lceil \frac{\lfloor \frac{x}{2} \rfloor}{2} \rceil = \lfloor \frac{\lfloor \frac{x}{2} \rfloor + 1}{2} \rfloor = \lfloor \frac{\lfloor \frac{x + 2}{2} \rfloor }{2} \rfloor = \lfloor \frac{x + 2}{4} \rfloor $$$
      $$$ Operation 2 : \lfloor \frac{\lceil \frac{x}{2} \rceil}{2} \rfloor = \lfloor \frac{\lfloor \frac{x + 1}{2} \rfloor}{2} \rfloor = \lfloor \frac{x + 1}{4} \rfloor $$$

      Obviously,operation 1 is no worse than operation 2

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

      can't we do 11? which gives floor( (x + 3 ) / 4 ). which is bigger. how this proves 000....11 is better for max?

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

    The intended solutions of these two problems are very simple and not that hard to guess, and guessing some conclusions is, to some extent, an important skill in programming contests, as you only need to write the code instead of the proof.

    • »
      »
      »
      9 hours ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      yes I am lowkey happy that I saw some tough problem, shows me I need to grind harder. and editorial of B is also very helpful ,thanks for that ... instead of just saying "it is trival to show" LMAO

      but why won't these tears stop .... aaaaaaa!!!!!

»
9 hours ago, # |
  Vote: I like it +7 Vote: I do not like it

div2C/div1A: it is noteworthy that a closed form solution exists (that can be derived from the recurrence relation):

$$$E(x) = x/2^{n-1} + n - 2$$$
  • »
    »
    9 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    so we can just perform right bit shift n-1 and convert the remaining value int a integer + n-2?

    How did you derive this from the recurrence relation?

»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the recurrence relation mentioned in Div2 C or Div 1 A Math Division problem?

if the i'th least significant bit is 1, why is it 1/2 * (1 — f(i-1)) + f(i-1)?

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

    Assume that the current bit is $$$1$$$. If a carry-over occurs in the previous bit (with probability $$$f_{i-1}$$$), then a carry-over always occurs in the current bit; otherwise, if a carry-over doesn't occur in the previous bit (with probability $$$1-f_{i-1}$$$), then a carry-over occurs in the current bit only when we perform the ceil operation.

»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks!very interesting problem

»
8 hours ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

.

»
8 hours ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

You can also turn off your brain in Div1-A and just calculate the probability of which bit is in position and whether there is a transition through the digit

»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain solution for problem B. I am not able to understand :( what is meant by this term "carry over"

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

    it just means that can a 1 survive after the operation

    so you can carry over 1 towards right with ceil, but you can't do it with floor.

    to get max value we want to carry over, for min we don't want to carry over

»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Proud of my solution -> read editorial -> cry.

»
7 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

can someone tell me why does the following approach fail for div2B?

  1. to reach the minimal value, we use the type 2 operation whenever x is even, and type 1 operation otherwise.
  2. if any of the operations is exhausted, we terminate the above step and apply the remaining operations until x becomes 0 or 1 or until all the operations of both types are exhausted.

we repeat the same steps to find maximal value but with just one change, we use type 2 operation when x is odd and type 1 operation otherwise.

  • »
    »
    6 hours ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    At first my idea is that too, but turns out that it's not. And yeah, it's hard to see that why it's wrong. Consider the test case:

    1

    11 1 2

    The problem with that greedy idea is that, sometimes, “burning” straight away a type 1 operation could lead to “burning” one of your floor operations when it would be more beneficial to delay it. In this test case:

    • If you use Type 1 first (since it's odd), then you are left with 5. But when you must do two other Type 2 operations, it becomes 3 and 2.

    • But the optimal solution should be you use two Type 2 operations first, which leads to 6 and 3. Then, if you do a Type 1, you will yield the minimum value which is 1, not 2.

    I think most of the people thought about the "even/odd" greedy idea, and it certainly is hard to know why it's wrong.

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

      thanks for the counter example and the explanation!

      i guess thinking specifically in terms of bits does help in this particular problem.

»
7 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I might be mistaken, but shouldn't $$$l$$$ in Div1B/Div2D be ceil instead of floor?

»
6 hours ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

B was really cool. I originally thought that having to save floors for the end to reach 0 when finding min was an edge case but after thinking about binary it makes way more sense. To find the min you use ceil because ceil stacks / carries over all the 1's in the binary representation of the number and moves them left. This allows you to minimize the number of ones and have a better chance of using the floors to cut off all the 1's and make the number 0. Conversely, for max you want to keep as many 1's as possible so the floor won't be able to get to 0 and the max will be as big as possible. Great problem despite the technical difficulties, thanks for the round!

»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

plz somebody explain me c Didn't get a single word in the editorial can somebody explain me plz with good examples

»
6 hours ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

thanks for the contest Ecrade_

Div1 B, C, D, E are all good problems I think. (cant comment about F and G felt not that since especially since hardcoding solutions exist)

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

in Div1B why cant it be the case that instead of first and last elements we choose some other pair whose values have been changed. Why is it only valid if we can do the first and last element in the end.

»
67 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

div2B was very interesting