Editorial of Codeforces Global Round 21

Thanks for participation!

If your solution to D involves any data structures and is not $$$O(n)$$$ -- please read the "solution 1". I believe it is very interesting, but to make the difficulty suitable for D we allowed not $$$O(n)$$$ solutions.

1696A - NIT orz!

1696B - NIT Destroys the Universe

1696C - Fishingprince Plays With Array

1696D - Permutation Graph

This problem has two different solutions. The first one is more beautiful, but less straight-forward.

1696E - Placing Jinas

1696F - Tree Recovery

1696G - Fishingprince Plays With Array Again

1696H - Maximum Product?

• 5 months ago, # ^ | got 4 times wa then realised .

• 5 months ago, # ^ | Lol Same...

• 5 months ago, # ^ | LOL ! I also did not realize it.

• 5 months ago, # ^ | got WA 3 times not realizing answer will be at most 2, one more WA for a mental typo using max(ans,2) instead of min(ans,2).

• 5 months ago, # ^ | Yeah, totally agreed! I love it when editorials have Hints as it allows many of us to solve problems (sometimes we just need that train of thought and a little nudge). Honestly, it's better than looking at the solution and then doing it, as there's still that feeling of 'doing it ourselves'

• 5 months ago, # ^ | Just out of curiosity, could you link that blogpost? I'd like to read it too

• 5 months ago, # ^ | Brother Legends never dies Tourist is Legendary No one takes his place

  • 5 months ago, # ^ | There is nothing called legendary. If you consistently put in the effort for over a decade(He has been into mathematics and programming since age 10), you could become like him(may be better than him).

    • 5 months ago, # ^ | And you're still newbie after 3 years.

      • 5 months ago, # ^ | Because I am not consistent :( I am trying to be consistent.

      • 5 months ago, # ^ | And you are still unrated after 2 years

      • 5 months ago, # ^ | I am saving the link to this comment because i want to comment here when i get a decent level of rating in CF.

        • 5 months ago, # ^ | and what's your definition of "decent"?

          • • 5 months ago, # ^ | lol, okay.

              • 5 months ago, # ^ | I want to give the same reply to u one day

• 5 months ago, # ^ | A Lion takes its one step back before making its bigger attack

• 5 months ago, # ^ | Normal competition when everyone is too good.

• 5 months ago, # ^ | Share the blog . I want to see what happen to our king !!.

• 5 months ago, # ^ | i Dont think its a downfall if you get -56 for global rank 7.

• 5 months ago, # ^ | because you do not need to store entire expanded array. you can simply store counts of repeating factors.

• 5 months ago, # ^ | You shouldn't make the whole array just you can store the occurences

  • 5 months ago, # ^ | can you pls explain how to store the occurrences such that they appear in the correct order as well?

    • 5 months ago, # ^ | I did it just storing a pair of values: the factors and its number of ocurrences. For example, for M = 3 and A = {6 3 4} -> {[2,3] [1,3] [4,1]} Did it for both vectors and compare them

    • 5 months ago, # ^ | 161770389 You can check here. I've just stored it as pair like if A={4,2,6} and M=2 then it will be {{2,3},{3,2}}.

• 5 months ago, # ^ | The maximum size of the array that can be created is of order 1e5, you are pushing more values than the max size, thus giving RTE. Instead of pushing all values, just store it in pair of vectors {value, frequency}.

  • 5 months ago, # ^ | Makes sense, thank you so much!

  • 5 months ago, # ^ | Excuse me, why is it giving RTE and not memory error?

    • 5 months ago, # ^ | As far as I know, segmentation fault = RTE in online judges

      • 5 months ago, # ^ | I meant how it's a segmentation fault? Like the code doesn't set any array size constraints as such

        • 5 months ago, # ^ | Because, after the array is completely filled, he is trying to insert more elements in it...

• 5 months ago, # ^ | Exact same thing happened with me!!! wasted 24 mins on a simple problem.

• 5 months ago, # ^ | lmao came here to comment this

• 5 months ago, # ^ | I cant understand the second approach given in editorial . Need help

• 5 months ago, # ^ | seems integer overflow problem.

• 5 months ago, # ^ | Int overflow

• 5 months ago, # ^ | if you take entire array, it will return 4. return value of mex doesn't have to appear in array.

• 5 months ago, # ^ | it will give 4. so the array will be 4 4 4 4 4 4 4. then do mex again for the entire array, it will give 0 this time. hence all 0.

• 5 months ago, # ^ | It's just hockey stick identity. Nothing more, nothing less. I don't think one has to prove a well-known, simple identity in combinatorics in their editorial

• 5 months ago, # ^ | I'll leave a link to the solution of last problem from last Starters since it also uses this identity and gives a 'proof' based on another (maybe more well-known) identity.

• 5 months ago, # ^ | ← Rev. 2 →   +12 For row i : the summation is iCi + (i+1)Ci + (i+2)Ci ... + (i+v[i]-1)Ci. Now if we know iCi = 1 = (i+1)C(i+1) Replacing this in the above formula we get the summation for row i as : (i+1)C(i+1) + (i+1)Ci + (i+2)Ci ... + (i+v[i]-1)Ci. Combine the first 2 terms : (i+1)C(i+1) + (i+1)Ci = (i+2)C(i+1) [ Using the simple property nCr = (n-1)C(r-1) + (n-1)Cr ] Replacing this in the equation we get : (i+2)C(i+1) + (i+2)Ci ... + (i+v[i]-1)Ci Again now, we can combine the next 2 terms and so on. So finally we get (i+v[i])C(i+1)

  • 5 months ago, # ^ | ← Rev. 4 →   +22 Thinking on how to come up with a visual approach, I have found the following one. It does nothing different than what 123thunderbuddie did, but supports the idea visually. We want to find the sum of the number of ways to reach every cell in the $$$i^{th}$$$ row. Assuming there are $$$c$$$ cells, the sum is equal to the following (just what 123thunderbuddie wrote): $$$\displaystyle \binom{i}{i} + \binom{i+1}{i} + \cdots + \binom{i+c-1}{i}$$$ Suppose there is a row below that has the same number of cells $$$c$$$ (not the $$$(i+1)^{th}$$$ row but a temporary one). This sum is actually equal to number of ways to reach the last cell in that row, which is $$$\binom{i+c}{i+1}$$$ (number of ways to reach cell $$$(i+1, c-1)$$$ from $$$(0, 0)$$$). Here is a visualization:

• 5 months ago, # ^ | The variable is z_cnt is not initialized in both of them resulting in UB. You got lucky with the second solution.

  • 5 months ago, # ^ | Thanks :) me rn

• 5 months ago, # ^ | thanks for the code

  • 5 months ago, # ^ | ← Rev. 2 →   0 you're welcome. Some lines are redundant you can remove them.

• 5 months ago, # ^ | Doesn't this code will add multiple edges between two nodes? Though it won't affect our result.

  • 5 months ago, # ^ | Yup it will i thought of making vector<set> but i ran out of time. see my submission during contest. I clutched this question after being brutally harrassed by Problem C(nice problem) in last 3 min.

• 5 months ago, # ^ | ← Rev. 2 →   +2 Just maintain vector of pairs where pairs.first = actual value and pair.second = frequency . Make vector of both a and b . And check at last a == b or not. Since we can divide every no m times even in the worst case it's log(n), which means atmost 30times for each element. which is still O(N). Code-- Spoiler

  • 5 months ago, # ^ | Nice username name, totally relatable ;)

• 5 months ago, # ^ | Notice that u with minimal number of elements in S(u) is a leaf. Do you know how to prove this? It does make sense intuitively.

• 5 months ago, # ^ | order matters, in map is ordered by key in increasing order so.

  • 5 months ago, # ^ | Okk Thanks for this

• 5 months ago, # ^ | In this Optimal Move would be to take whole subarray and calculate its MEX and replace it with all elements in the array then second move would be converting all array value zero In your Example 0 2 3 0 4 0 5 0 We first find out the mex of whole array which is 1 so array will be 1 1 1 1 1 1 1 1 then in second operation we will convert the above array to 0 0 0 0 0 0 0 0 so no more than two ways are possible

  • 5 months ago, # ^ | Thanks now I get it

  • 5 months ago, # ^ | For 0 2 3 0 4 0 5 0 ans is 1 how ?

    • 5 months ago, # ^ | No ans is not one in this case beacause we will take min(2,count of total continuous non zero element) we need maximum two operation only min(2,3) will be 2

• 5 months ago, # ^ | There r quite a lot of typos .

• 5 months ago, # ^ | As is literally every codeforces round including div 3, div.2, educational, div1+div2 combined, div1, olympiad-based rounds? (yes I know that div.4 exists but I don't have a very fond experience in div.4)

• 5 months ago, # ^ | why so many downvotes

• 5 months ago, # ^ | Take a look at Ticket 14387 from CF Stress for a counter example.

  • 5 months ago, # ^ | Ohh yes Got it Thanks!!

const double INF = 1.0 / 0.0;

const double INF = 1e18;

• 5 months ago, # ^ | ← Rev. 3 →   0 An explanation for the first (but not very informative) is that diving by zero (even with floating numbers) is undefined behavior, (according to [expr.mul.4], or discussions in StackOverflow), and anything can happen with undefined behavior.

• 5 months ago, # ^ | ← Rev. 2 →   0 a better suggestion might be using std::numeric_limits<double>::infinity() as the value for inf. this is not undefined behaviour and still compares bigger than the maximum value representable with double.

• 5 months ago, # ^ | in first operation,you can take l=1 and r=6(basically the entire array),so the new array will be 1,1,1,1,1,1. In second operation,again select l=1 and r=6,the array will now be 0,0,0,0,0,0.

  • 5 months ago, # ^ | For a collection of integers S, define mex(S) as the smallest non-negative integer that does not appear in S.... Then it means I can take any smallest non negative integer? it's not necessary that it should be less than all the elements of the array right?

    • 5 months ago, # ^ | No it's not necessary.But you cannot just take "any" smallest non negative integer. for example-Mex(5,2,0,3,0,5) will be 1 because 1 is the smallest non negative integer which does not appear in this array.

      • 5 months ago, # ^ | thank you so much... <3

      • 5 months ago, # ^ | But how number of operation for (5,2,0,3,0,5) is 1.

• 5 months ago, # ^ | Try expanding $$$a$$$ and $$$b$$$ into $$$a^\prime$$$ and $$$b^\prime$$$ in the example test cases.

  • 5 months ago, # ^ | i have expanded both the arrays upto maximum extent as possible but im not getting proof/intution.

    • 5 months ago, # ^ | Now notice that it is possible to obtain $$$a^\prime$$$ from $$$a$$$ after some operations, and it is possible to obtain $$$b$$$ from $$$b^\prime$$$ after some operations, so if $$$a^\prime = b^\prime$$$, we can obtain $$$b$$$ from $$$a$$$. We still need to prove that if $$$a^\prime \ne b^\prime$$$, it is impossible to obtain $$$b$$$ from $$$a$$$ after any number of operations. To do so, note that the fully expanded form of $$$a$$$ does not change when you perform one of the operations on it.

• 5 months ago, # ^ | Basically, $$$z$$$ will only lose bits. So $$$(a_i\mathrm{\ or\ } z^\prime) \le (a_i\mathrm{\ or\ } z)$$$, where $$$z^\prime$$$ is $$$z$$$ after some operations.

  • 5 months ago, # ^ | Okay, but what is the meaning of submask here specifically. Is it like changing the set bits of z after any number of operations so the resulting bit representation i.e. bit mask obtained is called submask?

    • 5 months ago, # ^ | $$$z^\prime$$$ is a submask of the bitmask $$$z$$$, since every bit that is set in $$$z^\prime$$$ is also set in $$$z$$$, but not necessarily vice versa.

      • 5 months ago, # ^ | It means new bitmask obtained after changing only the set bits of a bitmask is known as submask of that bitmask. Am I right?

        • 5 months ago, # ^ | ← Rev. 2 →   0 Sounds right

• 5 months ago, # ^ | You are doing: x = (a[i] | z) y = x & z z = y Every bit in z that is 1 is also 1 in x, so (x & z) equals z. In other words, you aren't changing the value of z and the second operation is doing nothing.