Dominater069's blog

By Dominater069, 4 weeks ago, In English

Sorry for the delay in publishing the editorial. If anything is unclear or missing, please let me know in the comments.

In all the problems, reading the hints is a must as the solution continues from there.

1944A - Destroying Bridges

Idea: Dominater069
Preparation: Dominater069
Editorial: Dominater069

Hint 1
O(n) Solution
Hint 2
Hint 3
O(1) Solution
Code (O(n))
Code (O(1))

1944B - Equal XOR

Idea : satyam343
Preparation : satyam343
Editorial : Dominater069

Hint 1
Hint 2
Hint 3
Solution
Code

1943A - MEX Game 1

Idea : Dominater069
Preparation : Dominater069
Editorial : Dominater069

Hint 1
Big Hint 2
Hint 3
Solution
Code

1943B - Non-Palindromic Substring

Idea : errorgorn, Dominater069
Preparation : Dominater069
Editorial : Dominater069

Hint 1
Hint 2
Solution
Code

1943C - Tree Compass

Idea: Everule
Preparation: Dominater069
Editorial: Dominater069

Hint 1
Hint 2
Hint 3
Solution
Code

1943D1 - Counting Is Fun (Easy Version)

Idea : satyam343
Preparation : satyam343
Editorial : Dominater069

Hint 1
Hint 2
Solution
Code

1943D2 - Counting Is Fun (Hard Version)

Idea : satyam343
Preparation : satyam343
Editorial : Dominater069

Hint 1
Hint 2
Solution
Code

1943E1 - MEX Game 2 (Easy Version)

Idea: Dominater069
Preparation: Dominater069
Editorial: Dominater069

Hint 1
Hint 2
Hint 3
Solution
Code

1943E2 - MEX Game 2 (Hard Version)

Idea: Dominater069
Solution : ffao
Preparation: Dominater069
Editorial: errorgorn

Solution
Code

1943F - Minimum Hamming Distance

Idea: satyam343
Preparation: satyam343
Editorial: satyam343

Hint 1 / Claim 1
Hint 2
Solution
Code
  • Vote: I like it
  • +109
  • Vote: I do not like it

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

no comment ?

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

    The editorial shows as created 31 hours ago but it was only published 1 — 2 hours ago.

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

Quite clear editorial!

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

I solved 1st and 3rd but got stuck in 2nd and 4th , thanks for the editorial guys it was a fun round

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

I have another proof for D1. If there is a 0 at the beginning of the array — remove it, otherwise substract 1 from the longest non-decreasing prefix. It is easy to check that this algorithm is correct.

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

It’s great that this editorial can give me hints first.

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

Why do you do

if (v[l + r] < (r - l + 1))

in solution of C to check if the substring is a palindrome ?

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

    Yes, Look at this.

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

      No, my question was why use l+r ? He has made l and r 0 indexed while he computed the array for manacher considering 1 indexing. So, the center of any substring would get shifted towards left by 2 units. so, why use l+r ? Why not l+r+2 ?

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

        Oh sorry, I thought u'r question was : "Do you .."

        So, Look at the function manacher_odd and manacher return values.

        U'r welcome.

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

          Well, the author has used the code from Link. The return values are that way because of these two lines in them —

          s = "$" + s + "^";
          t += string("#") + c;
          

          It is mentioned there that — "Note that  d[2i]  and  d[2i+1]  are essentially the increased by 1 lengths of the largest odd- and even-length palindromes centered in i  correspondingly." That means the array returned from manacher function is still 1 indexed.

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

            Two modifications has been made: one in manacher_odd and one in manacher.

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

              Yeah,got it. The return value in manacher function makes it zero indexed. Thanks!

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

            "Note that  d[2i]  and  d[2i+1]  are essentially the increased by 1 lengths of the largest odd- and even-length palindromes centered in i  correspondingly." Precisely!

            Note that cp-algorithms (to the best of my knowledge) usually follows 0-indexing convention.

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

              Why didn't you take max(d[l+r],d[l+r+1]) in your code to find the largest length among odd and even length palindromes centered in i ? Why looking for odd length only (d[l+r]) suffices ?

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

                Because the substring [l...r] has a well defined centre ((l + r)/2), why would i use smth else?

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

                  No, what I meant is this — The centre of the substring is (l+r)/2. In your code, you have used array v to denote the manacher array. According to cp algorithms, d[2i]  and  d[2i+1]  are the lengths of the largest odd- and even-length palindromes centered in i  correspondingly.In our case v = d and (l+r)/2 = i. Now,

                  ((l+r)/2)*2 = l+r, which is 2*i
                  ((l+r)/2)*2+1 = l+r+1, which is 2*i+1

                  So, v[l+r] tells us the length of odd length palindrome whose centre is at index (l+r)/2 in the original string.

                  And, v[l+r+1] tells us the length of even length palindrome whose centre is at index (l+r)/2 in the original string.

                  In your code, you are doing

                  if (v[l + r] < (r - l + 1)) ans += len;
                  

                  which means that if the length of odd length palindrome which is centered at index (l+r)/2 in the original string has a length which is lesser than the length of the substring, then the substring will not be a palindrome.

                  But such a case can also exist when v[l+r] < (r — l + 1) but v[l+r+1] >= (r — l + 1), which means the odd length palindrome centered at index (l+r)/2 doesn't have a length which is atleast equal to the length of the substring but the even length palindrome centered at index (l+r)/2 does have a length which is atleast equal to the length of the substring. In that case the substring [l,r] will be a palindrome.So, we should not be doing ans+=len; in that case. Right ?

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

                  According to cp algorithms, d[2i]  and  d[2i+1]  are the lengths of the largest odd- and even-length palindromes centered in i  correspondingly.

                  Odd length palindromes are centered at a character, even length palindromes are centered between two characters. $$$d[2i+1]$$$ refers to the longest even-length palindrome centered between $$$i$$$ and $$$i+1$$$. It makes no sense to check both $$$d[2i]$$$ and $$$d[2i+1]$$$ as they have different centers.

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

C was really cool problem

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

Nice Div2 Round

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

Hey guys, I'm not very familiar with div2-Cs, But isn't this round's div2-C felt like a normal 800-1000 rated problem? It felt very simple!

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

    It was pretty hit-or-miss, evidenced by the fact that a lot of people in Div 1 (including me) failed to solve it.

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

      Other than the editorial solution, an obvious greedy idea also works..... (and i was nice enough to not cut it as div2C)

      Just binary search and take smallest frequency each time, nothing hit or miss about this solution atleast

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

        I think (at least for me) weak samples made it harder. But I also understand that if samples were too strong, then the risk of people guessing the correct answer increases. In summary: just a skill issue.

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

Created a 10 minute video editorial for Div2D : Non-Palindromic Substrings. Experimented with a different format wherein I talk about how to arrive at the solution using 10 steps that logically follow from one another (instead of discussing the entire solution in detail). Let me know your feedback.

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

Nice problem related to Div2A: For graphs with $$$n$$$ vertices what is the minimum number of edges needed to guarantee the graph is connected? ie. find the smallest $$$k$$$ such that any graph with $$$n$$$ vertices and $$$k$$$ edges is connected.

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

I have yet another proof for D1. Let's traverse the histogram from left to right. In other words, imagine that we have a rectangle $$$a_i\times 1$$$ standing vertically on the segment $$$[i-1, i]$$$ of the real line. We are a little ant, we go from $$$(0, 0)$$$ to $$$(n, 0)$$$, but when we encounter a rectangle, we have to go up, and when it ends, we have to go down. Let $$$m$$$ be the total distance we had to go up (which is the same as the total distance down as the total height difference is 0), let $$$i$$$-th step up by $$$1$$$ have happened at position $$$l_i$$$ and the $$$i$$$-th step down have happened at position $$$r_i$$$. Clearly, $$$l_i\leq r_i$$$. If $$$l_1 + 2\leq r_i$$$, then we can use segments $$$[l_i, r_i]$$$ for our problem, and we are good. Otherwise, if $$$l_i + 1 = r_i = j$$$ for some $$$i$$$, then it is not hard to see that $$$a_j > a_{j-1} + a_{j+1}$$$.

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

Could anyone clarify problem C? From my pov, given an array of numbers: 0 1 1 2 2 3 3 3, then the answer should be 2 since Bob could draw every "2" before Alice could pick.

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

    If the game starts as follows

    • Alice: takes 0
    • Bob: removes 2

    Then after this Alice won't take 1 which she still has time to do later, but rather

    • Alice: takes the only remaining 2

    After this Alice can always take 1 and 3 in some order. In particular, if Alice is determined to take all the numbers from $$$0$$$ to $$$k$$$ (and if she can do it), then at each move she can take the one among these numbers that she hasn't got yet and that there are the fewest number of copies of at the moment.

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

      Nice explaination, thanks!

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

      In MEX Game 01, for the test case 2 (08). 9 (1 0 7 7 7 6 1 2 0). the answer should be 2 instead of 3.. Since Bob is trying to minimize the score && there is only one 2 in the array so, he'll wipe out 2 first so that the score could be 2... why he would let Alice to have the score 3???

      in this problem Bob's approach should be finding the smallest integer (x) which occurrence in the array is less than x+1.. and this smallest number should be the answer...

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

        he'll wipe out 2 first

        Wrong, Alice goes first and she will take 2 for herself

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

    You can also think in terms of game symmetry. 0 0 1 1 2 2 3 4 5 If Bob takes 1, Alice can mirror him and take 1. However, if Bob takes 3, Alice cannot mirror Bob and take 3. Thus Alice should take 3 first. However, after she takes 3, Bob will take 4 and Alice will be restricted to a MEX of 4.

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

Why did you make too small $$$n$$$ limit in div.1 C? I think Div. 1 participants can find tree diameter in $$$O(n)$$$ time.

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

    Why not? It doesnt allow simpler solutions (plus helps troll people who assume complexity) and im quite lazy to write O(nlogn) checkers

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

      Ok

      Trolling people who assume complexity. Genious strategy =)

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

How can one prove that given a string S isn't alternating or the same repeated character, we can always obtain a k-length substring that is not a palindrome for all k from 2 to |S| — 1 inclusive?

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

For 1943A — MEX Game 1, What about the test case:
1
6
0 0 1 2 2 3

Shouldn't the output be 1 instead of 3? I'm sure I've gone wrong but I've checked multiple times and can't see where I am wrong.

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

    Optimally Alice will pick 1 first, not 0 because she can always follow Bob if he chooses to pick a number that is present more than once within the array. For instance, if Alice picks 1 first, she is never worried about not being able to pick a 0 because if Bob picks 0 on the next turn, she can follow suit afterward. So given Alice picks a 1 on the first turn she will always be able to pick up a 0 and 2 no matter what Bob does, resulting in the answer being 3.

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

      Of course, that makes sense I was blinded by Alice picking 0 for some reason. Thank you for the clear explanation.

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

But why are the constraints for Div1C $$$2 \cdot 10^3$$$? Because of the checker? Or is there an $$$O(N^2)$$$ solution?

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

Dominater069 thanks for such good quality editorial.

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

Can someone explain in detail the transitions for Div1 D2? I am unable to understand the editorial. What do u mean by ‘don’t need to worry about creating extra bad indices because of PIE?

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

Some comments on editorial of F2 (as I am having hard time understandig it)

If f(x) is the number of arrays with atleast x bad elements then the answer should simply be f(0) — f(1). The claim that answer will be sum of (-1)^i f(i) is incorrect.Or I am wrong?

Seems like the editorial is in bad shape here. I can see some review comments (“I am not satisfied with the definition”) which have not been removed.

Also, the complexity should be 0(nk) right? At least by reading the code it seems 0(nk) and not 0(n^2)

Is the editorial partial? I can see a line saying “let b denote the number bad elements in the array” but b is not used anytime. Has the full editorial not been published?

Also, you have defined dp(i, last element, x) and in the definition you have not mentioned about what last element is? Hopefully it is a[i]?

I feel transitions have also not bern explained.

As someone who is doing PIE for first time I am struggling here

Thanks

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

    im sorry, ill try to rewrite it, and indeed complexity is nk, but k <= n anyways

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

      Thanks

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

        i tried to make it clearer, if its still not clear please comment the part, ill try to fix it

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

Shouldn't in E2 example be: 1, 2, 3, 5, 5 -> !!!2, 3, 3, 3!!! -> 1, 2, 2 and, if not, can someone explain why?

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

    K = 4 so 4 subtractions, [2, 2, 3, 3] would need 5 subtractions

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

      I typed 2,3,3,3. Not 2,2,3,3. Shouldn't by same logic, with example given, not be possible to go from 2,2,3,4 to 1,2,2(we need 3 operations to make 3 and 4 equal to 2, and then the one operation we make to reduce some number to 1 will Alice just take)

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

In MEX Game 01, for the test case 2 (08).
9
(1 0 7 7 7 6 1 2 0).
the answer should be 2 instead of 3.. Since Bob is trying to minimize the score && there is only one 2 in the array so, he'll wipe out 2 first so that the score could be 2... why he would let Alice to have the score 3???

in this problem Bob's approach should be finding the smallest integer (x) which occurrence in the array is less than x+1.. and this smallest number should be the answer...

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

    I don't think it should be 3, since Alice on her first turn will choose 2 first since that is the only 2 that exits. After that Bob will play 6. After these two turns are done it doesn't really matter what they choose, however, Alice will never get 3. Thus that is the answer.

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

In 1943A,I got confused in the test case [ 0 0 1 1 2 ] Alice is going to pick 0 then Bob will pick 1 and then Alice will pick 1 and Bob will pick 2.

So the output should be 2 but Expected Answer is 3.

Isn't this the most optimal way they both will be playing?

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

What do you mean by "We might accidentally create more bad elements, but remember that PIE allows us to not worry about that." in solution of Div. 1 D2?

I am not familiar very much to PIE, so if it is very basic rule sorry for that but.