Code, Slides, Practice Problems cfstep.com/codeforces/contests/contest-1946/problem-d/
@thedivineaurora9336
5 ай бұрын
extraordinary work !!
@mmmnmmmmmmmm
5 ай бұрын
Good videos
@arjungannu
5 ай бұрын
Because we are checking if final pref at each bit iteration is a SubMask of the Mask or not before updating the ans.
@cfstepofficial
5 ай бұрын
Correct, because submasks arer always less than or equal to the mask, so even if the exact bitwise or doesn't match, we can be certain that it'd be smaller.
@irohwin4336
5 ай бұрын
I have a doubt. We may split an array to 10 parts and end up with pref not being a submask. How do we gaurantee that there may not exist a split of array with 9 or less parts where every part may remain a submask? i tried to go through it but couldnt figure it out
@irohwin4336
5 ай бұрын
cleared, got it!
@cfstepofficial
5 ай бұрын
Replying for others stumbling on this thread. Notice that you tried your best to make each part a submask. So if you have 10 parts and the resulting mask is still not a submask, there is no use merging parts to get 9 parts, because then you would simply be merging submasks which is still a submask, so it doesn't improve your chances of finding a final submask.
@irohwin4336
5 ай бұрын
why is the [[ have==mask ]] condition even considered? it's obvious that 'have' is 'or result' of submasks so, 'have' would definitly be a submask of mask. Indeed why do we obtain correct result after placing that condition. Consider the example. a: 001, 001, 010. x=5. [101] for any bit [0 to 30], 'have' would never be equal to mask.
@cfstepofficial
5 ай бұрын
Perfect. If you're thinking about this question, then it means you were paying attention to the video. 1) Why is the "have == mask" needed? Remember that we were solving bit by bit, and we assumed that the first point of difference in the final OR would be at bit position 'b'. So, we in fact assumed the answer to be equal to mask, hence we were just validating if our assumptions did not lead to a contradiction. 2) The bigger question, if we were so lenient while distributing parts, how could we be sure that we will eventually hit "have == mask"? The answer is we won't. But whatever "have" we do create, focus on the first most significant bit that is set in mask but unset in "have". Call this bit position 'x'. Now, think about what would have happened when you were solving for bit position 'x'? You will get at least as many parts as the current one, because a set of suffix bits are removed, so restrictions are minimized. Hence, we have already captured a larger answer in a higher order bit. In fact, no matter how lenient you are, the highest part count will always lead to "have == mask". If you really understood these 2 points, here's a followup question : What would happen if we iterate over bits in descending order and break as soon as we find a valid split? Is it correct? Why or why not?
@cfstepofficial
5 ай бұрын
And in the example you shared, have can definitely be equal to mask. Look again. What are the possible values of mask? They are [101] or [0xx] or [000]. Here, xx means we don't care about the bit. If you recall, in the video, we talked about the fact that if a number is less than num, then, it's possible values are equal to a common prefix followed by an unset bit followed by a suffix whose value we don't care about (that's why we cut out the suffix using the right shift operator). Hence, while solving for bit position [2], the mask would be just [0xx], so we will cut off the last 2 bits from all numbers, the mask and all numbers (I also reiterated this fact in the video). So the number are 0 and [0xx, 0xx, 0xx] and the mask is [0xx]. Clearly there's a match.
@shashanktiwari4442
5 ай бұрын
I have one doubt.. inside the loop why are we not taking pref^=a[i] but taking pref^=(a[i]>>bit)
@cfstepofficial
5 ай бұрын
Because they would be the red bits we talked about earlier, their values do not matter. For example, if arr = [01] and mask = [10], then 01 is not a submask of 10, but it is still valid. Why? Because as soon as turn off the 1st set bit in mask (10 ==> 00), all numbers to the right of this set bit doesn't matter, so we should instead be asking if [0] is a submask of [0], and not whether [01] is a submask of [10].
@Rahul-sn6sl
5 ай бұрын
I also have doubt in this part, we are we doing a[i]/2^bit (a[i]>>bit) doesnt that alter the actual value of input?
@cfstepofficial
5 ай бұрын
@@Rahul-sn6sl We do need to alter the array values, since we altered the x on the RHS by trimming the red bits in the video. Please refer to the example that I posted above.
Пікірлер: 15