Bitwise Operations for Competitive Programming | Topic Stream 8
Vložit
- čas přidán 3. 06. 2024
- Bitwise operations - binary representation in general, the operations that can be done on binary numbers (both logical and bitwise), and some problemsolving techniques involving them. Feel free to use the timestamps to skip around to what you don't know, I started from a very basic level.
Here's the mashup (the practice problems) codeforces.com/contestInvitat...
and a pastebin with the sources and difficulties of each problem: pastebin.com/HLMw0a9q
The problems are roughly ordered by difficulty.
I currently can't find a problem on bitsets, will update the mashup if I do.
Stream will start Sunday, at the normal Codeforces round time: www.timeanddate.com/worldcloc...
I will take various questions and go over the practice problems.
Playlist of past streams: • Topic Streams
A similar, nice resource from Errichto: codeforces.com/blog/entry/73490
Timestamps:
Intro + what is binary? 00:00
Binary representation in computers 04:49
Bitwise and logical operations (and, xor, etc.) 07:00
Builtin functions (popcount, etc.) 21:15
Some tricks/identities 26:32
Using bitmasks, bitsets, bitmask DP 31:34
Main takeaways for problemsolving 39:46 - Věda a technologie
This is actually amazing! Can you do number theory next? I am really looking forward to it!!!
That did pretty well in the vote for this, so it could definitely win and be next stream's topic.
@@ColinGalenWHere's the voting was done ?
@@336_saranyamaity8 It was done at czcams.com/video/eFlR4ymrKGI/video.html
This is a special case, the voting will normally not be done via comments. That video will detail my weekly plans.
@@ColinGalen thanks , and after commenting in most of your videos you finally replied sensei ✌️
Thanks for starting it out from scratch, I'm a noob but i was actually able to wrap my head and get a fairly decent understanding!
The example problems given in between in the video to think are very helpful,i was able to arrive at the solution myself and that led to getting some confidence in the topic as well! Thank you!
Started following u after those precious topic streams and they are back now 😍😍Thanks alot @Colin
I don't know whether you are still active, but after 2 years it still helped me
Thanks for the mashup and stream!! Also would really appreciate if you could cover topics in the future required for mid range participants. For ex, Grundy games, Xor Basis, probably harder adhoc problems, etc. Just harder problems in general. Really liked the dp optimization video.
xor basis is mid-range? yikes, i'm behind
edit: a serious reply, yes, if it wins a vote
Amazing vid bro!!! one of the best vids on bit manipulation out there! tysm!!
Small correction at 6:11 that will be from -(2^7) to (2^7 - 1 ) for 8 bits signed integer .
Hey bro can you tell me from where you did learnt about bits
unsigned itself is wrong..
its 0 to (2^8-1)
for signed its:
-(2^7) to (2^7-1)
Damn your explanations are godly.
These are just incredible plz keep doing some complex topics like types of dp, segtree
FYI, I've done a dp + segtree stream, can be found at czcams.com/video/KX_-7AqcnEU/video.html
@@ColinGalen yeah i have seen it , i was saying like a completely different video on range queries and like some more things like graphs(advance stream ) , trees and all
Thank you so much bro, very very very useful, I'm very happy, I'm very thankful very much, peace ✌️
I have a question. For finding the k-th bit of a number x, can't we use the formula : x&(1
How many days do we have to solve the mashup ?? To stick with your plan
At the 38:00 minute mark, why is the complexity or number of transitions = 3^n? The transitions mentioned are conditional on the bit in the original number, right? If that bit is 0, then the submask is forced to have 0 - if the bit is 1, then the submask can have either 0 or 1 - but basically there's only 1 OR 2 transitions possible at any state.
Then why do we have 3^n, implying 3 transitions at every state?
Can you shed light on monotonic nature of AND and OR or share some resources regarding this
you're an awesome teacher
Thanks alot this is great 👍
btw what's the time complexity of _popcount , _clz and _ctz
When would you use bit wise operations
Bits are independent....Wow, it made approaching problems easier
thanks mr. colin
here you said 3^n but there are many duplicates so what is the correct answer??????????????????
AWESOME!!!
Graphs next please 😀
Would actually appreciate if we picked couple problems and we implement them...Thank you
Thank you
Thank you :)
range at 6:11 is wrong:
unsigned:
its 0 to (2^8-1)
for signed its:
-(2^7) to (2^7-1)
Binary strings next ෆ╹ .̮ ╹ෆ
Op bro 🤟🤟
🔥🔥
next please Combinatorics 1700+
I'm fine with repeating stuff, but in case you (or anyone reading) didn't know, I've already done a stream on this: czcams.com/video/le2enQgQ7Ws/video.html
orz
colin
Yes dear
Not my point to cpmplain but wathcing this viedo made me watch also 20+ ads wtf
LinkedList please!
that's not cp