Its insane how i almost immediately understand how to solve D and E problem, but I've been reading C for about half an hour. Idk why problem setters always doing poor problem statements nowadays. Maybe these are measures against ChatGPT.
@shayan please sir can you explain this : PROBLEM D: we are using f[] array to make the node dead and lets say we get node z and node y' for operation x then we make node y' as dead .How are we ensuring that down the line for any other x ,node y' will be not be critical node(only node forming pair with some other node divisible by operation number )??? or in simple words please prove choosing any node among two would be fine.
I was waiting for this only. I have a question regarding problem D, i understood that we're processing decreasing order of x but if we take x in increasing order it can create some problems and we might not get our solution, can you explain why is that? I can't understand why we can't take x in increasing order.
As already said by Shayan, if we have to choose the one having difference say `x`, if only we have x+1 vertices left, we can ensure that by pegionhole principle, we are guaranteed to get one's modulo x will be same as another one. If say you take the vertices in increasing order, while you get till n-1, you only have one choice which does not guarantee you to give two numbers having same modulo (n-1)
can we also solve C like, we keep the count of subarrays from l to r such that the value of 'g' becomes zero, and then subtract them from total number of arrays i'e n*(n+1)/2 so we do the DP where dp[l] = 1 + dp[l + r], where dp[l] holds number of subarray starting form l and having the 'g' as zero, so we can find r in log(n) time so time complexity becomes n log n , and in the end we summate the dp's and we can have our answer.
n Problem E, the editorial says that if we have a bit set in sizes of two trees then we can set all other lower bits using that but this case is not possible if we can't always break the tree in desired size. For example for test case 1 2 8 1 1 1 1 1 1 1 8 1 1 1 1 1 1 1 there are two trees with size 8. but by breaking the second tree we can only obtain 1 tree of size 4 and 4 tree of size 1. Thus breaking that tree into tree of size 4 and size 2 simultaneously is not possible. So the answer for this case should be 13 (8 | 4 | 1). Can you please explain
It seems you made this video in hurry. I came to see how Problem D works but couldn't understand anything . Your last video was good but not this one. try to take actual examples and explain with edge cases. Not intuitive video it's like you are explaining from editorial section
![[LIVE] : ONE ลุมพินี 79 | คู่เอก "ก้องชัย vs อาเมียร์"](http://i.ytimg.com/vi/WfPSA1A0NHc/mqdefault.jpg)
Its insane how i almost immediately understand how to solve D and E problem, but I've been reading C for about half an hour. Idk why problem setters always doing poor problem statements nowadays. Maybe these are measures against ChatGPT.
only half an hour???? nah, it's way harder
I solved C faster than A
I went from specialist to pupil 😭😭, Please tell me how many DIV 2 C I need to solve to be comfortable???
Nice job mate! One thing I think the cuts are annoying, that needs to be worked on, or just don't do it.
You are right
was eagerly waiting for this! Thnkyuh @shayan
Thank you, Supriya!
@shayan please sir can you explain this : PROBLEM D: we are using f[] array to make the node dead and lets say we get node z and node y' for operation x then we make node y' as dead .How are we ensuring that down the line for any other x ,node y' will be not be critical node(only node forming pair with some other node divisible by operation number )??? or in simple words please prove choosing any node among two would be fine.
I was waiting for this only. I have a question regarding problem D, i understood that we're processing decreasing order of x but if we take x in increasing order it can create some problems and we might not get our solution, can you explain why is that? I can't understand why we can't take x in increasing order.
is this your username mayank5102002?
As already said by Shayan, if we have to choose the one having difference say `x`, if only we have x+1 vertices left, we can ensure that by pegionhole principle, we are guaranteed to get one's modulo x will be same as another one.
If say you take the vertices in increasing order, while you get till n-1, you only have one choice which does not guarantee you to give two numbers having same modulo (n-1)
icreasing order me you will be having less pigeons and more number of boxes so ye condition ki ek box me do pigeon honge does not hold true
can we also solve C like, we keep the count of subarrays from l to r such that the value of 'g' becomes zero, and then subtract them from total number of arrays i'e n*(n+1)/2 so we do the DP where dp[l] = 1 + dp[l + r], where dp[l] holds number of subarray starting form l and having the 'g' as zero, so we can find r in log(n) time so time complexity becomes n log n , and in the end we summate the dp's and we can have our answer.
nice
Bro, you are true legend.
Thanks man! Means a lot
n Problem E, the editorial says that if we have a bit set in sizes of two trees then we can set all other lower bits using that but this case is not possible if we can't always break the tree in desired size. For example for test case
1
2
8
1 1 1 1 1 1 1
8
1 1 1 1 1 1 1
there are two trees with size 8. but by breaking the second tree we can only obtain 1 tree of size 4 and 4 tree of size 1. Thus breaking that tree into tree of size 4 and size 2 simultaneously is not possible. So the answer for this case should be 13 (8 | 4 | 1). Can you please explain
Thanks for the solutions. 🙏🙏
Sure thing!
Problem D
why is it always better to start with X = N -1 instead of X = 1 ?
why do we decide to kill the node with higher numbre i ?
Thank you!!
Sure thing
It seems you made this video in hurry. I came to see how Problem D works but couldn't understand anything . Your last video was good but not this one. try to take actual examples and explain with edge cases. Not intuitive video it's like you are explaining from editorial section
I'm sorry if that is the case. We'll try to improve the content next time.
buy a mike dude
a Mike or mic?
@@CPwithShayan we already have Mike Mirzayanov so a mic 😂😂
@@ankit21309 Yes 😂 I will do that then. Thanks for feedback. ❤️