Gheal's blog

By Gheal, history, 7 weeks ago, In English

A — The Third Three Number Problem

Authors: antontrygubO_o, Gheal

Hints
Solution
Code (C++)
Rate Problem
Post Scriptum

B — Almost Ternary Matrix

Author: Gheal

Solution
Code(C++)
Rate problem

C — The Third Problem

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

D — Almost Triple Deletions

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

E — Three Days Grace

Author: tibinyte

Solution
Code(C++)
Rate problem

If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other setters in the comments.

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

»
5 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Very Fast Tutorial, Amazing Contest

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Thank you for the hints

»
5 weeks ago, # |
  Vote: I like it +130 Vote: I do not like it

B was quite an annoying one

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

    yeah

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

    I know, right?!

    Could someone please explain the implementation? I didn't get what the solution shared in the editorial is saying exactly...

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

      Start by solving a 2x2 matrix. For the 2x4 matrix, you can flip the 2x2 matrix to the right. You can see that if you just flip the 2x2 matrix to the right every time, you can solve matrices of sizes 2x6, 2x8, and so on. The same can be applied with nx2 matrices (4x2, 6x2, 8x2 and so on), except this time you flip the 2x2 matrix down.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it +22 Vote: I do not like it

      a much easier implementation would be to notice that a pattern in the binary matrices like this

      1001
      0110
      0110
      1001
      

      and we can obtain any row x column by increasing or decreasing the rows or columns accroding to this pattern.

      for eg : a 8 x 10 will look

      like this

      so for implementing just make a 50 x 50 matrix (which is not much of a trouble if you use copy and paste) and output for given row and column

      my code :

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

        amazing

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

        bro is a true gamer

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

        OMG, I can't believe I didn't try this uff. I was unnecessarily trying to automate the process! Thank you very much.

        I realize why I didn't get this
    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      I think getting into into the graphical proof would rather be long so the setter avoided elaborating much on that, but there's actually a subtle way to approach it.

      Consider the top left cell, start filling from there recursively for some small input, you'll notice a pattern and reach some solution for it. So, now you have the answer to this small input, can you reuse this ?

      So, assuming you tried using it, did you notice some induction happening or an extension of your pattern?

      You can prove by induction that the pattern in fact safely extends for the given input!

      Code
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeap

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

    No.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Well, it didn't have any particular way to solve it, you just had to guess the structure of the matrix and I just found that pretty annoying... idk about you.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

B/E and C/D seem to have the same rate problem poll.

Edit: Thanks for fixing! Perhaps it should've been better to keep the C/D poll for C, since it's likely that most people voted for C rather than D, but it shouldn't be too major of a problem.

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

D & C have same "problem rate"

»
5 weeks ago, # |
Rev. 3   Vote: I like it -17 Vote: I do not like it

Comment Deleted

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

Thanks for the fast editorial. And the contest was amazing! Problems are great.

»
5 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

In my opinion C was relatively tough as compared to general C.

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

    Most testers said that the current C would be better as a div2 D. We did try to insert a new C between the current B and C, however this wasn't approved in the end.

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

      Ohh..that was the case...but overall contest was pretty good.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Though i couldn't do it, but C was really an interesting problem.

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

    I went on the wrong track, and even tried to implement offline fenwick tree queries lol. I thought it had something to do with the number of elements greater than a number k between the first appearance of a number from 0 to k and the last appearance of a number in the range 0 to k. The solution was much simpler lol. I didn't have time to finish this solution so idk if it works.

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

    D was too hard too, contests should be easier so they don't make me feel bad :((( Also they should make me grandmaster

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

    Here's my submission. 162794168

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

Thank you

»
5 weeks ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

.

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

    Thank you.

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

    That's the most cursed thing I have ever written, accidentally or not. Has been fixed.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I found a solution for B, but couldn't implement it in the contest (I am sure that there are other people like me). I generally think problems like B in Div. 2 should be easy to implement when you find a solution.

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

    Well, I guess that was the whole point of B, figuring out the solution was easier than standard div2B's, but the implementation was the tricky part.

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

      I mean, implementation was harder than standard B's, but not that hard. Also, the simplicity of the idea kinda makes up for it in my opinion.

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

      My implementation is pretty short, I genuinely thought the idea was the hard part.

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

There was a hint on sample tests on problem B. Sad I saw it so late

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

In solution of C, "If p[2]∈[l,r], we can say that, for every interval x,y, MEX([bl,…,br]) must be at least 3"

Shouldn't that be MEX of [bX....bY]?

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

    That is true, thank you for noticing. It has been fixed now.

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

Auto comment: topic has been updated by Gheal (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Did anyone solve problem D with segment tree?

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Please ban these kind of users

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

    I would request Mike and his team to kindly look into this since it made the contest unfair for many! ;(

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

[.]

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

Solution to B, "...with a 1-thick border."

What is that border?

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

    Like if you cover the boarder in the picture, you have a checkerboard that looks like this:

    XX..XX
    XX..XX
    ..XX..
    ..XX..
    XX..XX
    XX..XX
    

    I think that's what they meant. Hope that helps.

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

      Thank you, it wasn't clear to me neither.

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

      Are you going to be posting a screencast of this contest?

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

        Welllllll....

        I recorded an incredibly entertaining screencast and was going to post it. But for some reason my mic was set up incorrectly so there was no sound, despite my recording software visually showing me that there was sound. So I feel kind of cheated out of it, but unfortunately on screencast this time, especially because this one would have been great. :(

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

          I'm very sorry to hear this... Right when i saw you in the standings I was hyped to see a screencast. However, did you like the problems ?

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

            I did, yeah. Overall they were very interesting. The only one I downvoted was A, because I think asking a newbie questions about xor isn't very approachable. It was a neat idea, but I think a little scary for that position if you're not familiar with CP.

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

      my construction was that these 2 2X2 blocks

      01

      10

      and

      10

      01

      have to be used alternately. Sorry for the bad formatting.

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

        That's the way I thought too. I am still wondering how jiangly's brain works after seeing this solution:

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    std::cout << ((i ^ j ^ (i >> 1) ^ (j >> 1)) & 1) << " \n"[j == m - 1];
                }
            }
        

        what on earth is this

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

          It's just a more concise way of formatting writing the checkerboard thing. Essentially, it's just the parity of (i = 1 mod 2) + (j = 1 mod 2) + (i = 1 or 3 mod 4) + (j = 1 or 3 mod 4), which is exactly what you want if you look at the checkerboard.

          It would be more clear if I could post a whiteboard drawing, but in any case, I think just chewing on this type of parity stuff will make it easier to internalize/visualize/quickly convert from tilings to math.

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

          lol what a orz guy.

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

why im not able to attempt the hacks for this contest?

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

What is " \n"[j==m]; in the c++ solution of the B problem??? Doesn't it have a name??

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

    j==m can be transformed into int(j==m); " \n" is a string constant (char array).

    Then it's just the same as accessing an array.

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

      cool way to code clean!

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

        Interesting, because I felt that such kind of coding style is the complete opposite of clean coding (unless, if you think clean code == shortest possible code).

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

        As far as I know, clean code means the one which is easily understandable to others. Condensing your code so much that no one else understands it, I don't understand the logic behind it.

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

      so when we will get only " " and when we will get " \n" how it is decided ??...

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

        when j == m, the output is true which is taken as 1. and when it is less that m, the output is false, i.e 0;

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

        Let us assume s = " \n", so s[0] = ' ' and s[1] = '\n'. Here, in the for loop, he wrote " \n"[j == m], so if j == m, j == m will be 1 and " \n"[1] = '\n' will be printed, otherwise " \n"[0] = ' ' will be printed.

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

MikeMirzayanov This person's (bored_kid) submissions look very sus. example:162802356

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

    they probably could've used the time it took them to insert all these lines to actually solve the problem lol, I really don't understand those people... good job for calling them out

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

    bored_kid if you are bored, go and learn new things. Rather than copying and defaming your country by just mentioning India, instead mention your real name and institution.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

This Guy Posts Solutions on YouTubein real time. Can we do something about that? He always gets 500 to 600 views during contests

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Sorry for stupid question but I am seeing this syntax first time, From Editorial of problem B-

cout<<((i%4<=1)!=(j%4<=1))<<" \n"[j==m]; 

Can you tell what [j==m] is doing here and why there is no << before that?

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

    See this comment.

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

    if j==m, it means j is the last element of the row, so j==m is 1 and " \n"[1] is actually '\n'. Otherwise, j==m is 0 and " \n"[0] is a whitespace. This small trick is used to print whitespaces between elements, and a newline after a row of elements.

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks for the round!

In problem E, some of solution can be hacked with special testcase:


t=1

n=1000000,m=5000000

a={n numbers with a large number of divisors in [1,m]}


Especially when the solution has O(MlogMlogN) time complexitity, I recommend you to check it :)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I actually had generator with large divisors, but I think i should have considered a bigger upperbound on the number of divisors. I think it was set to be at most 50 divisors less than the maximum possible number of divisors...

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

nice editorial and thanks for the hints

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

How to prove that the sum (a⊕b)+(b⊕c)+(a⊕c) is always even in the first problem?

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

    Consider the lowest bit of the three numbers, and check all cases.

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

      Any formal proof?

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

        I included a formal proof in the solution for A.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          How we can conclude that a ⊕ b and a + b have the same parity (odd or even number of 1-bits) from the equation a + b = a ⊕ b + 2⋅(a&b)? And also how same parity ensures that (a ⊕ b)+(b ⊕ c)+(a ⊕ c) will be even?

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

            $$$2\cdot (a\text{&}b)$$$ is always even, so it would make sense that $$$a + b$$$ and $$$a ⊕ b$$$ have the same parity.

            The parity of $$$(a ⊕ b)+(b ⊕ c)+(a ⊕ c)$$$ is the same as the parity of $$$(a+b)+(b+c)+(a+c)=2 \cdot (a+b+c)$$$, which is always even.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              You are considering parity as the property of an integer of whether it is even or odd or it means parity of a number whether it contains an odd or even number of 1-bits?

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

                Parity as in whether an integer is even or odd.

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

    for odd numbers it is impossible to have a b c to satisfy the condition and for even number one possible pair is 0 n/2 n/2 so the sum is always even.hope it helps

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    last bit of all 3 elements 0 0 0

    0 0 1

    0 1 0

    0 1 1

    1 0 0

    1 0 1

    1 1 0

    1 1 1

    now xor them and add last bit will always be zero. :)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it
    PROOF FOR A
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    consider the case where n is odd which has last bit as 1, so we need last bit as 1. but if we check all cases where numbers having last bit like 1 0 0 0 1 0 0 0 1 1 1 0
    0 1 1 1 0 1 1 1 1 All cases give last bit as 0 if we try out it in given equation.

»
5 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

The observation in B is very hard .-32 in the rating thanks codeforces

»
5 weeks ago, # |
Rev. 2   Vote: I like it +48 Vote: I do not like it

Here is a way to approach problem B: (let me use "color" instead of "value")

We have to find a coloring, such that each cell has exactly 2 neighbours of a different color. IMHO, 2 neighbours of a different color are quite annoying. I've tried to avoid it, reformulating like this: each cell has 4 neighbours, so let's find a coloring, such that each cell has 4-2=2 neighbours of the same color. But it fails on the borders.

However, we can avoid "different color" part! Let's xor each cell with corresponding cell in the chess coloring. Now we have to find a coloring, such that each cell has exactly 2 neighbours of the same color.

From that side, the solution is easier: split the matrix into 2x2 squares and color neighbouring ones differently.

Here's the solution for 8x6 matrix (I've assumed black is 0, white is 1):

Interesting facts:

  • The answer is ((i/2 + j/2) % 2) ^ ((i + j) % 2)

  • The answer is the same as in the editorial

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

    can't understand from the part "however we can avoid ..." can you please explain a bit more how are you xoring with the chess board and how this approach comes into your mind

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

      Suppose you have a matrix a, such that every cell (i, j) have exactly two neighbours of the same value. Then you put the matrix on a chess board and flip those values that lay on white cells. Effectively, you assume that black is 0, white is 1 and perform xor of corresponding cells.

      Consider some black cell (the logic with white cells is pretty much the same). It has only white neighbours. That means it doesn't change value, but all the neighbours do. In result, the former cell has now exactly two neighbours with different value.

      Can't say anything about how to come up with the idea...

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How did you create the image for the editorial of problem B? It's pretty.

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

    I made it using vanilla HTML and JavaScript.

    Code
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi, could somebody explain third's logic, can't wrap my head around it.

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

On Codechef, there was a similar problem as C, it had like 20-30 solves. In editorial, there was some statement that the current requirement is equivalent to... If someone remembers, can you please share the link

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem B wasn't in expectation. Was very annoying !

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

I solved A through C. I thought that A was kind of mathy for an A, but it was okay. Problem B was kinda easy for a B as it was just figuring out how the optimal construction will look like. And I thought C was a pretty nice C. My sol was to maintain 2 pointers pointing to the left and right of the current subarray, and l = r = position of 0 at the beginning. While the MEX of the subarray was less than n, I used reverse indexing to get the position of the MEX in array a and moved my subarray to include it. Then, I calculated the amount of extra numbers(from the difference of the MEXes) that could go in the empty spaces of the subarray and I multiplied the answer by space_P_amount, where amount was the number of extra numbers that could go anywhere inside the array. 162794168

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

was B really that simple that it got 9k+ correct submission . I wanted to know as I didnt able to come with an algorithm for B even after spending 2 hrs. Its happening since past 2 contest that i got stuck on B and my rating is decreasing gradually due to this

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

    Same for me, I am surprised by the big number of solves.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      it's due to cheating B is a good problem and its difficult to observe the pattern

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

    Lol I spent more than 30 minutes coming up with a solution right now. Constructive problems are wild, eh? I saw someone's comment saying "B was easier than regular div2 B" ☠️

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

Problem A :- a=0, b=n/2 and c=n/2 also works.

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

For problems like D, really wondering how people come up with the right dp idea along with this observation? This dp method and the proof don't seem obvious to me, and I don't understand how to come up with this idea given this problem (For me, binary search or checking the maximum value of each value is more intuitive, though they can't solve this problem). (Perhaps it's just I am too bad at dp orz)

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

    Man, I never would've thought of this dp idea. I wasn't able to solve D during the contest but it seems like you can solve it kinda greedily as well. I created the can_delete matrix to store if some subarray can be deleted and then I just found out the max length possible greedily. Can't prove it tho. my submission

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

      Hmm, that's a strange solution... However you were very close to the solution, most difficult thing imo was checking weather subarray can be deleted...

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

        I figured out a solution during the contest that if we create some matrix that stores if a subarray can be deleted or not we can easily build a dp table such that dp[i] denotes the maximum number of the same elements as a[i] of which the last element is at the ith position. Just couldn't think of a way to make the matrix (matrix — isposs[i][j] = 1/0 depending on whether we could delete the subarray i...j or not respectively). The observation (n/2 must be even and max(freq[1..n]) <= n/2) was not intuitive. Link to my solution

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

      Try something like 1 2 1 2 1 2 1 2 3 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3

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

    Same here. I thought checking for each distinct value is obvious thing as it also matched the complexity O(n^2). I did try to think of some dp after that. Something like, dp[i][j] = maximum equal value j we can get from first i elements;

    then dp[i][j] = max(
    dp[i-1][j] + 1 ,if a[i]==j;
    dp[i-1][j] - 1, if a[i]!=j;
    ,
    ....more transitions here)
    

    but couldn't figure out the whole thing.

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

Can Anyone Explain the Solution of Problem C a bit more?

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

    First all, it is easy to know 0 and 1 must have the same position in 'a' as 'b'. It is easy to find examples that 'a' is not similar with 'b' if the statement is not true.

    Next, consider the interval by the position of 0 and 1. If 2 is in this interval in 'b', then 2 can be any position in the interval in 'a'. To prove this, there are several cases to consider. But it is easy to understand the reason if you use a sample to learn. And if 2 is out of the interval in 'b', then 2 must be in the same position in 'a'. After 2 is considered, continue to consider the interval by the position of 0, 1, and 2. And consider whether 3 is in the interval or is out of the interval. And so on until to n-1.

    I don't know how this formula is gotten: "(r−l+1)−k", but you can always calculate how many position are available in one interval and multiply the number to the answer.

    One sample submit: https://codeforces.cc/contest/1699/submission/162835519

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

      yeah thanks I understand now, for the formula for ex if pos of 1 is 0 and pos of 0 is 3 then the no of positions for 2 are =3-0+1-(num of pos taken by 0 and 1) which is 2 itself so 3-0+1-2=2 hence the formula (r-l+1)-k hope you can understand now

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

      I know number 0 . But why is the position of number 1 the same as that of number 1 of array a? Please indicate,thanks.

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

        If you use a sample to check it, it is not difficult to find that is true. If 1 is on right side of 0, such like "2 0 3 4 1 5", it is quite clear, as starting from position of '1', MEX value becomes 2 or more. If 1 is on left side of 0, such like "2 1 3 4 0 5", I guess you may ignore the problem asks any interval should have same MEX. Then you can check an interval which covers '0'. Whether '1' is in the interval impact MEX value of position '0'. So '1' cannot be moved either; otherwise at least one interval's MEX is different.

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

      houxiang thanks for the approach, got it now !

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

    my solution for problem c,

    lets pos[a[i]] = i;

    initially let l=r=pos[0], as the only position for the 0 in b is the same as in a, because in a, mex(l=pos[0], r=pos[0])=1, and we have to maintain that in b.

    now to get a new mex value in a, we have to extend our interval [l, r] somehow to get a value greater than 1, to achieve that, we have to at least include the value 1 into our interval, so we have to extend either l or r to include the value 1, so if (pos[1] < l) then we have to extent l, or if (r < pos[1]) we have to extend r, after doing that, we can see how the position of value 1 in b have to be the same in a, but now the mex value can be greater or equal to 1, so we might have values greater than 1 included in our new interval that we don't benefit of, we simply are going to store them for later when they are included in the mex value (because if we position them in the current interval then we didn't consider the possibility that they can be positioned outside the current interval).

    we continue trying to increase the mex value of our interval, for example, after extending the interval to include the value 2, we got the mex value 4, so now we are going to look for the value 5 so we can have a new mex value.

    now about the stored-for-later values, that at some point they were greater than the mex value (actually they were greater than mex+1), now some of them are included in the new mex value, so they have to be positioned somewhere in the current interval and not outside it, so we are going to look at the currently available positions in b that aren't occupied with some values, and we are going to choose some of them to put those values, and then choose their order. after that, we delete those newly positioned values from the stored-for-later set of values and continue our process until the interval covers all of a.

    my implementation
    how to manage mex value with updates

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

can we do B using dfs traversal? for example first fill all the positions of the 2d array with 1 then run dfs from (0,0) so that every cell change exactly two neighbour cells 0. any one help?? if i'm wrong

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

    Possibly, but it's definitely not necessary. A simple matrix traversal is enough for this problem.

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

    what exactly do you mean by DFS traversal? what exactly would you do for each node?

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

      for every node (i,j) goto (i-1,j),(i+1,j),(i,j+1)and(i,j-1) then make exactly two of them to opposite color of (i,j).

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

Can someone prove B? I solved it like this too but I don't know how to prove it exactly

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

Can anyone suggest me similar problems such as today's Div2 B? I found it annoying. I know no problem is a bad problem and instead of complaining we all should try our best but sometimes I feel like I'm getting nowhere. How should I approach such problem ? Should I try out as many test cases as possible until I find a pattern ?

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

How can somebody come up with this solution for problem B 162759681. Can anybody explain the intuition and logic behind its implementation ?

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

The questions mentoined in post scriptum of problem A. How can we solve them can anyone give hints? According to me for 1) mod — if n is even return 0,n/2,n/2 else -1 2) gcd — no idea

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

    For gcd, the intended solution is $$$1$$$ $$$n-2$$$ $$$n-2$$$.

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

      for mod is the logic correct?

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

        Yes. If I recall correctly, $$$a$$$, $$$b$$$ and $$$c$$$ needed to be distinct, which I didn't mention in the blog. My solution was $$$0$$$, $$$1$$$, $$$\frac n2$$$.

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

          thanks got it btw nice editorial

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

            thanks, glad you liked it

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

          Can you please reply to my query as well. How is this solution 162759681 working exactly and what is the intuition behind this implementation

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Base row1..... .... 1001 Base row2... . ... 0110 Again repeated row3 0110 Row4.. .......... 1001 Like this formats its repeated

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

I did not understand this statement from C: "For every other interval, MEX([bl,…,br]) cannot exceed 2". In the above statement, how can the MEX value be 2? Isn't the maximum MEX 1 for all other intervals?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The statement in solution C says "For every interval [l,r] such that (l≤p[0]<p[1]≤r), MEX([bl,…,br]) must be at least 2. For every other interval, MEX([bl,…,br]) cannot exceed 2". The interval L = 0, R = 2 you mentioned satisfies the condition (l≤p[0]<p[1]≤r). But the question is about intervals that don't satisfy this condition.

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

    Yeah I had the same Confusion

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Sadly I had to do some more important things so I couldn't participate :(

But I really enjoyed cadmiumky's problems!

Marinush

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

    And I really enjoyed you not participating!

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

    And I really enjoyed the bried time before this comment where you hadn't assumed I asked!

    cadmiumky

»
5 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

Tbh, problem B was too easy for div2b, thanks to first sample that used pattern, which can be extended to infinite boards. However, problem C was annoying imo.

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

    I found B hardest among A-D, seems skill issue on my part.

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

      Maybe we're just good at different types of tasks, I can't say that I'm really into DP problems ;)

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

      Can you Explain the Solution of Problem D a bit more?So hard for me![cry][cry]~

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

    Can U explain B . I found it to be very tricky and could'nt solve it!

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

      Just look at the pattern in the first sample.

      Split your n * m board into 2 * 2 squares, and paint these squares like chessboard, but instead of black and white use [[0, 1], [1, 0]] and [[1, 0], [0, 1]].

      You can extend this pattern to infinite boards.

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

The problems were great. Thank you!

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

    i see your comment in every blogs.. you are so active..

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

      Is it bad?

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

        i guess no .. if you have enough time... just it was my observation..

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

In the third problem can we like just try to logically make out what the value of all subarrays MEX will be and then the numbers which are constant(mostly 0 & 1 along with some other number in Their MEX) and then fix positions of these numbers or the ranges the number can exist in. After this I am getting a bit lost, can anyone help with this thought process

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

Really liked the name of Problem E, The best band in the world ❤️

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

can someone explain the editorial of B?

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

In problem E, Can anyone give an example of values of the following dp state. I didn't get what is it actually storing.

dp[i][j]= the best possible maximum if we had number i and the minimum value in the product is j, j is a divisor of i.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For a number $$$i$$$ and all ways of writing it as product of some values that are $$$>= j$$$, take the one that has the lowest maximum value. It is easy to see only values that can affect this dp must be divisors of $$$i$$$ so we only need to consider those.

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

Nice contest

»
5 weeks ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it

Gheal Can you update the test cases for D? They seem to be weak enough to pass a following greedy solution: for each value val of the array, just go through the array from left to right; whenever we meet val, if possible, remove the segment since last val we picked. Something like

1
26
1 2 1 2 1 2 1 2 3 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3

would fail this approach. 162829437

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

    This test was added automatically because of a successful hack with it, I'm not sure if the submissions will be rejudged though.

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

the problem a and c were very similar to codechef problems A was very similar to this problem and C was very similar to this problem

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

Very Fast Tutorials!

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

Damn it! I was using LinkedList for D :/

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

Am I the only one who thought D can be done more easily than C?

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

    lol, I just go in order.

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

    Hey harshitbhatt!Can you Explain the Solution of Problem D a bit more?Thank you!

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

Amazing C

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

The problem B is quiet hard to me ;(

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

The Editorial is fantastic and it is easy to understand.Thanks!

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

Actually A is the simplified version of this CodeChef problem.That is why I can solve it at 0 minute. Btw isn’t antontrygubO_o the contest admin of Codechef?

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Why 256MiB in Problem E?

I spent about 1 hour on this...

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

B was quite an annoying one

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

The simplest solution that always works correctly is to find those numbers that gcd(a, b) + gcd(b, c) + gcd(a, c) = n; And if n is even then the possible move will be 0 0 n/2 otherwise there is no solution: int n; cin >> n;

if (n % 2) {
    cout << "-1\n";
    return;
}

cout << "0 0 " << n/2 << "\n";
»
5 weeks ago, # |
Rev. 3   Vote: I like it -24 Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Hey Gheal! I was wondering why the hints to problem D seemed pretty difficult to me, but when I opened the "solution" I realised that probably "subsequence" has been used instead of "subsegment" or the more favourable (in my opinion) "subarray".

Please look into that!

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

    My bad. In romanian, the transliterations of subsequence and subarray have swapped meanings. Thank you for spotting this mistake, it has been corrected.

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

    Hey,naman1601! Can you Explain the Solution of Problem D a bit more?Thank you!

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

Question C how is this kind of question done? I can't deduce. Can you give some methods or suggestions?orz,%%%,thanks.

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

The first part of editorial for E says: This dp can be calculated in $$$O(vmax⋅log^2(vmax))$$$ for all values

Why not in $$$O(vmax⋅log(vmax))$$$?

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

    Usage of maps for finding at what index would divisor x be in number i.

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

Can Anyone Explain the Solution of Problem D a bit more?

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Why these $$$O(m \cdot log(m))$$$ solutions get TLE? 162900411 and 162902446

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

    I'm quite sure there were solutions in $$$O(log^2)$$$ that passed so I can't figure out how these TLE tbh.

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

      And also, both submissions above are the same. But one gets TLE on test 2, and the other gets TLE on test 13. (You can view their diff in codeforces' submissions compare).

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

Can someone please explain me the logic behind problem B?

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

    I observed this 2x2 pattern from the given test-cases:

    $$$ \left(\begin{array}{cc} 1 & 0\\ 0 & 1 \end{array}\right) $$$

    If you place this pattern of [[1, 0], [0, 1]] in the top left 2x2 sub-matrix, then you can alternatively place this pattern and its mirror — [[0, 1], [1, 0]], in the rest of the rows and columns. The design will spread such that all numbers will be guaranteed to have 2 different neighbors.

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

if in ques 1, if we take 0,0 and that number as addition of 3 with xor are equal to n, why is it wrong??

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

struck in D can anyone tell solution of D in simpler way?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to prove a + b = a ⊕ b + 2⋅(a&b) ?

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

    We can think of this in terms of individual bits.

    0+0=0⊕0+2*(0&0)=0

    0+1=0⊕1+2*(0&1)=1

    1+0=1⊕0+2*(1&0)=1

    1+1=1⊕1+2*(1&1)=2

    Just testing out all of these possibilities, it can easily be seen that the equation holds true.

    A more intuitive understanding of the formula would be: the 2*AND operator is there because the XOR operator effectively cancels out a 1 and a 1. Therefore, to account for the case of double 1's, we just need a 2*AND operator. Otherwise if at least a or b is zero, then a+b=a⊕b

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

    a ⊕ b is the sum of individual bits and 2⋅(a&b) is the carry.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

damnnnnn 3rd problem... The implementation is too good, my mind is blown. Awesome!!!!!

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

My solution for D gets AC https://codeforces.cc/contest/1699/submission/162975412

but if fails on this testcase:

1

42

1 2 1 2 1 2 1 2 3 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 3 2 1 2 1 2 1 2 1

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

Hey Gheal, in div2E, why do we update smax only when i <= mn?

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

    smax wouldn't accurately describe the minim balance if i > mn, as that would mean not every element has been taken into consideration (i.e. the minimum)

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

The editorial's way of calculation of the final answer for C was actually pretty nice! I tried using some combination concepts and kept getting runtime errors and a messy code lol.

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

Can we solve D using doubly linked list? By iterating on the target value in final array?

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

can anyone one explain condition put in cout statment. For problum B in editorial

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

good editorial

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

Hi Just Curious ? how can i solve this gcd(a,b)+gcd(b,c)+gcd(a,c)=n. ?

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

For Problem E, in the last loop: for (int i = mx; i >= 1; i--) if we change it to i > 1, then we would got WA on testcase 8. So here are my 2-fold question: 1. why does it matter, i== 1 shouldn't update toggle, and hence ptr — i will only get larger. 2. how can i get the full testcase8 in its entirty? Currently, it is too long and shown as ... at the end. thanks

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

    My code needs to consider i = 1, as that could be the minimum value. It's true, it does not change the value, but it is the first time the code knows that we have conisdered ever decomposition (and put it in toggle), and as such a better value than the originally considered mx - mn might appear (more specifically, it will be the largest prime divizor — 1). Writing i > 1 will affect the code as such to ignore all the possible decompositions made by the code, and it will remain with the default value of mx - mn

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

I wonder is there a solution could make D better than $$$O(n^2)$$$
I guess so but I can't find any.

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

please anyone can describe the line " cout<<((i%4<=1)!=(j%4<=1))<<" \n"[j==m]; " ?