### Dominater069's blog

By Dominater069, 2 months ago,

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
• +109

 » 2 months ago, # |   0 no comment ?
•  » » 2 months ago, # ^ |   0 The editorial shows as created 31 hours ago but it was only published 1 — 2 hours ago.
 » 2 months ago, # |   -8 Quite clear editorial!
•  » » 2 months ago, # ^ |   0 Blah
 » 2 months ago, # |   0 I solved 1st and 3rd but got stuck in 2nd and 4th , thanks for the editorial guys it was a fun round
 » 2 months ago, # |   +37 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.
•  » » 2 months ago, # ^ |   0 Can you explain your solution?
•  » » 2 months ago, # ^ |   0 Nice
 » 2 months ago, # | ← Rev. 2 →   0 It’s great that this editorial can give me hints first.
 » 2 months ago, # |   0 Why do you do if (v[l + r] < (r - l + 1)) in solution of C to check if the substring is a palindrome ?
•  » » 2 months ago, # ^ |   0 Yes, Look at this.
•  » » » 2 months ago, # ^ |   0 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 ?
•  » » » » 2 months ago, # ^ |   0 Oh sorry, I thought u'r question was : "Do you .."So, Look at the function manacher_odd and manacher return values.U'r welcome.
•  » » » » » 2 months ago, # ^ |   0 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.
•  » » » » » » 2 months ago, # ^ |   0 Two modifications has been made: one in manacher_odd and one in manacher.
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Yeah,got it. The return value in manacher function makes it zero indexed. Thanks!
•  » » » » » » 2 months ago, # ^ |   0 "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.
•  » » » » » » » 2 months ago, # ^ |   0 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 ?
•  » » » » » » » » 2 months ago, # ^ |   +10 Because the substring [l...r] has a well defined centre ((l + r)/2), why would i use smth else?
•  » » » » » » » » » 2 months ago, # ^ |   0 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 ?
•  » » » » » » » » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 C was really cool problem
 » 2 months ago, # |   0 Nice Div2 Round
 » 2 months ago, # |   0 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!
•  » » 2 months ago, # ^ |   0 It was pretty hit-or-miss, evidenced by the fact that a lot of people in Div 1 (including me) failed to solve it.
•  » » » 2 months ago, # ^ |   0 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
•  » » » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   +11 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.
 » 2 months ago, # |   0 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.
 » 2 months ago, # | ← Rev. 2 →   +8 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}$.
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ |   +13 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.
•  » » » 2 months ago, # ^ |   0 Nice explaination, thanks!
•  » » » 2 months ago, # ^ |   0 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...
•  » » » » 2 months ago, # ^ |   0 he'll wipe out 2 first Wrong, Alice goes first and she will take 2 for herself
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # | ← Rev. 2 →   0 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.
•  » » 2 months ago, # ^ |   +8 Why not? It doesnt allow simpler solutions (plus helps troll people who assume complexity) and im quite lazy to write O(nlogn) checkers
•  » » » 2 months ago, # ^ |   0 OkTrolling people who assume complexity. Genious strategy =)
 » 2 months ago, # |   0 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?
 » 2 months ago, # | ← Rev. 4 →   0 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.
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 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.
•  » » » 2 months ago, # ^ |   0 Of course, that makes sense I was blinded by Alice picking 0 for some reason. Thank you for the clear explanation.
 » 2 months ago, # |   +16 But why are the constraints for Div1C $2 \cdot 10^3$? Because of the checker? Or is there an $O(N^2)$ solution?
•  » » 2 months ago, # ^ |   +24 Because of the checker.
•  » » » 7 weeks ago, # ^ |   0 what's a checker?
•  » » » » 7 weeks ago, # ^ |   0 the program that checks your answer
 » 2 months ago, # | ← Rev. 2 →   0 Dominater069 thanks for such good quality editorial.
 » 2 months ago, # | ← Rev. 2 →   0 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?
 » 2 months ago, # |   +11 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 hereThanks
•  » » 2 months ago, # ^ |   +3 im sorry, ill try to rewrite it, and indeed complexity is nk, but k <= n anyways
•  » » » 2 months ago, # ^ |   +3 Thanks
•  » » » » 2 months ago, # ^ |   +3 i tried to make it clearer, if its still not clear please comment the part, ill try to fix it
 » 2 months ago, # |   +8 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?
•  » » 2 months ago, # ^ |   0 K = 4 so 4 subtractions, [2, 2, 3, 3] would need 5 subtractions
•  » » » 2 months ago, # ^ |   +8 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)
•  » » » » 2 months ago, # ^ |   0 You are absolutely correct, sorry for the error.
 » 2 months ago, # |   0 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...
•  » » 2 months ago, # ^ |   0 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.
 » 7 weeks ago, # | ← Rev. 2 →   0 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?
•  » » 3 weeks ago, # ^ |   0 Alice pick 0 then Bob will pick 2 and then Alice will pick 1.
 » 7 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 4 weeks ago, # ^ |   +6 I mostly understand PIE intuitively and it is clear to me when and how it is applicable in a problem (when a thing is a subset of another thing we do something with $(-1)^k$ or $(-1)^{k + 1}$). I've actually only once formally (mathematically) proved a solution involving non-trivial PIE. Here is how I would do it in this case (tho it definitely isn't the simplest method).Recall the Wikipedia definition of the formula: $|A_1 \cup A_2 \cup \dots \cup A_n| = \sum_\limits{i} |A_i| - \sum_\limits{i < j} |A_i \cap A_j| + \sum_\limits{i < j < k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|$So we need to use sets somehow. Let $A_i$ be the set of arrays where position $i$ is bad. Note that $|A_i| = f([i])$ from the editorial. Notice that $|A_1 \cup A_2 \cup \dots \cup A_n|$ is precisely the number of bad arrays. So the answer is $(k + 1)^n - |A_1 \cup A_2 \cup \dots \cup A_n|$. Now let's use the formula. Consider $|A_{x_1} \cap A_{x_2} \cdots \cap A_{x_k}|$. This is the number of arrays where all of the elements on positions $x_1, x_2, \cdots, x_k$ are bad. It is $f([x_1, x_2, \cdots, x_k])$ from the editorial. So we get that $ans = (k + 1)^n - |A_1 \cup A_2 \cup \dots \cup A_n|$ $ans = (k + 1)^n - \sum_\limits{i} |A_i| + \sum_\limits{i < j} |A_i \cap A_j| - \sum_\limits{i < j < k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n} |A_1 \cap A_2 \cap \cdots \cap A_n|$ $ans = f([]) - \sum_\limits{i} f([i]) + \sum_\limits{i < j} f([i, j]) - \sum_\limits{i < j < k} f([i, j, k]) - \cdots + (-1)^{n} f([1, 2, \cdots, n])$Which is what is claimed in the editorial. You absolutely shouldn't ever do this in a real contest, however, it might be useful for understanding the approach.