C++ Bitsets in Competitive Programming

[@Errichto]

Also, you can print a bitset and you can construct it from string or integer. In particular, you can easily print binary representation of number 123 this way (where 15 is arbitrary number of bits): cout

[@mogovanjonathan]

hy Errichto, coutd you please help me with the solution c++ of the first problem(1 month) using popcount, how to make 2 3 5 6 8 in 01101101 --> 109? thank you

[@umangagrawal228]

@@mogovanjonathan for(int i=0;ia[i][j]; if(a[i][j]!=0){ b[i]=b[i] | (1

[@umangagrawal228]

and b[ i ] is the array in which we store the schedule representation of each worker

[@mogovanjonathan]

​@@umangagrawal228 Thanks sir!

[@pratyushbhatt1712]

@@umangagrawal228 Its wrong, You cant use a 2D for 1st question, so much space you've wasted!

[@sahilamin219]

This video is What i have WAITED to see for YEARS . You are FIRE 🔥

[@luccanunes1570]

I hope he knows how important these videos are for people. I really can't imagine my programming life without Errichto's lectures and streams

[@chiefolk]

12:32 i was confused as to why errichto was doing bitwise left instead of bitwise right as he said he would do bitwise right few seconds ago in previous slide, now i understand why because bitset is indexed reverse unlike an array so bitwise left should be done. TL;DR bitset is having opposite endianess.

[@stratonov]

This should be pinned

[@samuelcanochocce2521]

same doubt till read your comment ty

[@mowafkmha4505]

took me almost 2 hour trying to understand how the logic works until I realized what you have said

[@RAJATTHEPAGAL]

This content is awesome. 😃😀 For anyone preparing for competitive programming or even maybe for ds and algo for interviews.

[@incrediblecoder3369]

The knapsack solution is so cool especially optimising the for statement with the shift. Never thought of that before.

[@saurabhsharma7123]

Now, I have a complete understanding of the std::bitset. I always had doubts about its complexity. Thanks!!

[@mogovanjonathan]

hy , could you please help me with the solution c++ of the first problem(1 month) using popcount, how to make 2 3 5 6 8 in 01101101 --> 109? thank you

[@AbhishekSingh-cd6yc]

15 min for the video and 30 min for understanding. it would say 45 min well spent :)

[@mogovanjonathan]

hy , could you please help me with the solution c++ of the first problem(1 month) using popcount, how to make 2 3 5 6 8 in 01101101 --> 109? thank you

[@AbhishekKumar-im2xd]

@@mogovanjonathan you can do it like::) bitset b(0); //if you know that the atmost range is 32 say we have numbers int arr[5]={2,3,5,6,8}; bitset b(0); for(auto i=0;i

[@mogovanjonathan]

@@AbhishekKumar-im2xd thanks man, i ve been waiting so long for this answer. Thank you!!!

[@himanshu7271]

@@mogovanjonathan try to write natural numbers above the each digit starting from 1 ,you will understand. What's this???

[@shubhmishra66]

Thank you Errichto! This is splendid...

[@pythonwork4709]

Thank you Erichto. Your tutorials are wonderful and helpful. I hope you would come up with more such videos.

[@ouyaah]

Amazing, using binary representation is so overpowered, I am glad we invented computers. Great explanations. The knapsack example is awesome. In the examples you show, I think you have this pattern of finding the bitset representation of some kind of "visted set" that helps you reason on bit operations rather than integers. I wonder if it is a pattern you can relate to when searching for algorithms to problems in C++ in general.

[@Errichto]

Every topic has some patterns and tricks and here it's: subset = binary mask. I don't think it's related to "algorithms to problems in C++ in general".

[@hritikbangar4341]

@@Errichto Hey errichto it would be great if you can make some videos specially dedicated to patterns like these like subset=binary, covering almost all the topics of programming

[@dropfiremusic4752]

Dear Mr. Kamil! Your content is so useful, getting so much new knowledge from you! Thank you!!!

[@vikramsaurabh8240]

always fun to watch your videos and learn at the same time. Very systematic and lucid way of teaching stuffs. I just wish your channel keeps on growing Errichto. You are doing a terrific job !!

[@336_saranyamaity8]

why we are not taught about bitset in general , its so good and useful !!! I came across a DP solution using bitsets and that was the moment I knew i must learn bitsets , IT WAS A AWSM VIDEO !

[@mumen_rider4209]

in the boolean example of dp ,we traverse from last to see if we can occupy the previous value .Whereas in bitset we OR the value to the value shifted to x , to check if we can attain the weight W

[@rohakdebnath8985]

I love these videos. You make so articulate content.

[@mdsazidkhan4720]

Thanks errichto for such underrated yet important concepts :)

[@samolisov]

I've tried to solve a task about count triangles in a graph and it looks a solution may be the following (without needing to divide by 3): 1)make sure the graph is directed, so remove opposite edges during/after bitset buildin. 2) when you going through the vector of bitsets the sicond time (in the nested loop), start not from the beginning but from std::next(the first iterator). This prevents the sets from being duplicated during checking, so we will get intersection of sets[0] and sets[1] but never sets[1] and sets[1] again. 3) during testing wheter there is an edge between veryices 1 and 2 also check is there an edge 2->1 because the graph is directed now.

[@RickeyBowers]

This is so concise and easy to code in assembler.

[@nextrie]

I definitely learnt something. Thanks for introducing C++ functions we don't see too often.

[@Kadaj0666]

Awesome work ! I struggled a bit to get the Knapsack, but it's so clever ! Thanks a lot for the new knowledge !

[@sophiesparkle2464]

This make so much sense and meaning and do hope to understand all this video more and more

[@hungquang8527]

Hi, I have a (probably stupid) question... I'm using Dev C++ on Windows, and I can only initialize a 500-million bitset; when I tries to initialize a 1-billion bitset I receive an "out of memory" warning. I've previously learnt how to expand stack size for dfs recursion using -Wl,--stack=(STACK_SIZE) but apparently it doesn't help in this case. Have you heard of this situation before/know how to solve it ? Thank you for reading !

[@Errichto]

I've never heard of something like that :( make sure you create it globally, not locally. And maybe try running your .exe file from command line, not from IDE.

[@BhupendraYadav-li4ts]

Codeforces custom test too doesn't allow to create a bitset of size 1e9.🙁

[@utkarshmaheshwari8717]

Really knowledgeable content sir

[@lovemusic8862]

Amazing! Thanks a lot for this content! Greetings from Brazil!

[@a1988ditya]

Brilliant video, we need more Sir ... Thanks

[@aj-uo3uh]

A break out of that loop in the knapsack problem when can[W] is true would result in a faster answer most of the time.

[@hotwanikunalsunil4675]

damn bro damn, hell of a video. Keep going dude.

[@fardeenrahman3845]

You know, you are so gorgeous. your explanation is so simple and convenient. you explain in detail and never escape a small thing. It's really mind-blowing. Plz, keep it up.

[@ranitbandyopadhyay]

Kindly make other important videos explaining with examples as can be found from the codeforces blogs. I am eagerly waiting

[@wagnerrodrigues6440]

Thanks Errichto! Very nice content!

[@mohammedshoaib1635]

An amazing explanation. Thank you for making these videos!

[@maruftuhin6030]

Thanks for this informative video. Please keep up the good work. It's helpful and is really making the difference!!

[@AmitKumar-pl4po]

Dammnn That explanation is so cool. Thank you @Errichto

[@ashwaniponia3817]

Very Nice Content .... Good Work Errichto

[@suhailakhtar1707]

please add some more commonly used algorithms in your playlist, algo lectures. It would be very helpful for us.

[@srijansankrit2340]

highly underrated content!

[@introvertsinger710]

Can you please create a series on C++ STL. You're an awersome coder.

[@zuesextra5957]

in knapsak problem can we do bitseta and then for each weight we mark it found , then in the last we make "the bitset"a & "the target weight"w and if the result = "target weight"w we print yes otherwise print no , it easier in implementation and faster in complexity which myabe equal to O(max_w/32 + n)

[@evergreen7781]

That's really awesome 😍 I was looking for some good tutorials on bit manipulation... Thanks @Errichto 😃

[@saiprasadduduka2155]

Thanks Errichto

[@asishpanda7142]

Great content , keep up the good work

[@tanduclam2742]

Thank you very much. It's very useful in competitive programming

[@mumen_rider4209]

in the example explained ,the bitset is from left to right , while in program it is from right to left

[@jimmyshenmusic]

Nice video. Thanks for posting.

[@ArunKumar-th9ph]

@Errichto @12:55 Consider the binary substring of "can" bitset from the rightmost 1 which would be at index 0 up to the most significant set bit i.e., the leftmost 1 in the "can" bitset. Is the statement "This string must be a palindrome." true?

[@kbhanuprakash9530]

Thanks for your explanation 👍

[@coder389]

knapsack trick very brilliant

[@indrajitbanerjee5131]

Nice stuff!! Liked it.

[@anonymoussloth6687]

Do you have a video or article that explains knapsack? I saw your DP playlist but couldn't find it

[@pratyushbhatt1712]

Man this is called simple and elegant, GG Kamil, this was superb!!!!!

[@val5_]

This video was mind blowing

[@jamjam3448]

Thanks so much bro

[@НикитаШуляк-б6в]

In the second problem, is it okay to do "can

[@yashjain6945]

Thanks

[@vijayKumar-xq1wu]

hey @Errichto can u please provide us link of problems on this topic

[@shoaibsiddiquie5389]

U R the Best. U R an Inspiration brother

[@AmazingWorld-fw9oc]

Hey Erichto, At 11:59 you said we have to right shift than in coding part you did left shift, please explain.

[@lovishkumar5520]

bro in bitset index start from right means 5 4 3 2 1 0 like that so we are doing left shift

[@AmazingWorld-fw9oc]

@@lovishkumar5520 ohh thanks a lot.

[@sachinprasad2220]

very well explained

[@tejasbagal8068]

great work!!!

[@hoangucmanh299]

hey i have a homework problem, given n, imagine we have 2 plates, put n on the 1st plate. We can pick multiple weights of 3^k, k = 0,1,2.... (k >=0) and put on the two plates, (plate 1 has n already, and plate 2 is empty), so that the 2 plates are balanced. the constraint is that we cannot use weight of any kind more than once, and n is

[@gentleman7060]

I'm confused in the first part N^2.D Why d? N^2 is not enough? Or maybe i didn’t get the question. Can you explain

[@bhavukgarg3619]

Today I got to know how much more I have to learn yet...

[@MS-gt9yu]

Awesome... thanks for for this tutorial..

[@chuongnguyenphuc4803]

this so awesome, thanks you so much

[@SupGhostly]

Thanks for this

[@louisfghbvc]

Awesome!!! Thanks

[@antonfernando8409]

A bit fast paced, appreciate you slow down a bit, thanks.

[@DanielOliveira-ex6fj]

wow, 700+ likes, 0 dislikes. This video deserves it.

[@mowafkmha4505]

the shifting and oring in knapsack didn't make any sense for me until I realized that bitset[0] is the right most bit

[@arya6175]

Thanks a lot, this is really helpful...

[@rembautimes8808]

Great video thanks

[@savarkars1403]

What does the variable 'x' represent in the exact Weight W question ?

[@amankapoor7665]

I think it represents the actual elements of the set. So in the above example x would be 2 and in the next iteration it would be 3.

[@samiere]

Please make more!

[@incrediblecoder3369]

awesome brother.

[@TuanNguyen-su5ty]

Nice video

[@binu44464]

Awesome 👍

[@vikasbaghel6999]

Doubt in knapsack problem- Why we are left shifting in the code but in the example you right shifted?

[@code-marshal]

The way we write and the way bitset is represented is different.

[@djBC10000]

too smart lol. I learned nice tricks about bitsets, thank u. How come the C++ compiler doesnt allow for arrays or bitsets to be initialized with a variable size, e.g. the size has to be constant at compile time? This is a bit restricting because more often than not, the input size is variable.

[@lanfker]

use vector for that,man

[@djBC10000]

@@lanfker Yeah i know that lol, i am talking specifically about arrays and bitsets here.

[@skilz8098]

You need to think as the compiler does or what it will do with the intended meaning of your code. When you create an integer it will reserve a section of memory that is the width of the integer on your platform so if you are working on a 64-bit machine and your target project is set to 64bits and you declare "int x = 0;" x will be 64 bits wide or 8 bytes wide. Since the machine has internal registers and a bus width of 64 bits, yet each addressable byte is 8 bits or 1 byte, it will reserve either 8 bytes in ram or a single 64bit register within the system cache. There are other factors at work behind the scenes such as the OS, and the hardware itself on its internal design and how they construct the stack and stack pointer and other things, but most of that is automatically handled and you should have to worry about it. This is just how a computer fetches a section of memory and reserves it for you. The C++ compilers are "strongly typed languages" so it has to know the type and the size of the type at compile time in order to create an object file or a binary before it passes it to the linker. Since int is a builtin type within the language the compiler automatically knows this and doesn't have to resolve its type and because it is built in the size is given too, except that the size of the integer is dependent on the architecture and the compiler's settings for the target platform. So when you make the declaration "int x = 0;" The type is already known at compile-time and it is already known to be 64bits for this type. Now, let's say you want an array of these ints. There are two ways you can declare an array, the first is an empty array such as "int x[];" It will create an empty array with a single element, so this will end up giving you 1 int of that type except that it is still an array of the integer type. Array's will decay to pointers so to speak because the starting point of the array is addressable by the pointer address of the very first element or at the 0th-index into that array. The other way is to state how many elements you want for that array, it's size. If you need 10 objects of a type, then you would make the statement and declare "int x[10];". Here, the compiler has to know how large the array is as the value has to be constant. If you tried something like this: "int x = 4; int y[x];" this will generate an error because "x" is not constant. On the other hand, if you did this: "const int x = 4; int y[x];" this would be fine because "x" is "const". The reason the compiler needs to know the size of the array at compile time is that this evaluation I believe happens during either the syntax analysis or during the tokenization stages. In C++ the array's size needs to be known for other reasons as well, as you have to take into consideration: the stackframe and stack pointers, storage type, and scope. In C this is different, you can have a variable-length array... C++ needs to know how much storage to allocate for any given data type structure before it can generate a translation unit to send to the linker. Here is a Stack Q/A that gives a real clear illustration: stackoverflow.com/questions/4341570/why-does-a-c-c-compiler-need-know-the-size-of-an-array-at-compile-time

[@skilz8098]

@Peterolen True, but it comes down to the architecture of the machine. There is hardware that has 32-bit registers and there are some that are 64 bit and their bus sizes can vary... these are usually defined in the ISA, then it's up to the compiler and OS to know how to use it.

[@shreyashachoudhary480]

Thanks red!

[@literallynull]

Is bool array[70] faster than bitset in MSVC C++17?

[@parthatara1044]

Thanks for the content...It helps a lot :))

[@termodox]

in the last problem the bruteforce complexity was N*N*N but the solution is also in N*N*N is it not? we compute each node with all the others

[@luismiguelmoralesnavarro1490]

Love you bro

[@Jquee999]

can you please explain why you divide by 32 ?

[@toshitkale1174]

Never seen a like dislike ratio as this not a single second wasted

[@prabhpreetsingh5341]

Hey Errichto ! I was just wondering whether multidimensional bitsets are possible or not ... just like maybe 2d bool array

[@saurabhsharma7123]

why can't I use duplicates in bitset version of subset_sum??

[@subhampan]

very informative and conciese video!

[@zhiweilin3603]

for the dp solution shown at 11:29, shouldnt the embedded loop go from x to W instead of W to x? Because if we start at i = W, then can[W-x] is always gonna be false at the begining since only can[0] is true and rest is all false

[@zhiweilin3603]

i see the problem alr, thanks for the amazing video!

[@navneethingankar6486]

wouldn't size of unordered_map be more efficient for second question or is bitset faster??

[@code-marshal]

Unordered_map also uses some technique to resolve collisions. We cant always guarantee O(1) access time.

[@rhutshab]

which is better? _builtin_popcount or bitset::count??

[@Norhther]

Popcount is not a cpp function, but a builtin function of gcc. So not portable as a cpp code. Also, if you want the best performance, you should use -march flag to specify the cpu aechitecture.

[@syeda.k.2934]

12:26 aren't we supposed to rotate right >>. ?

[@adityaraghav8693]

thats what i was thinking ......

[@syeda.k.2934]

@@adityaraghav8693 i guess only we both were thinking that.

[@bharathrajs7318]

The least indexed bit is at the right. For eg, for a 4 bit bitset after setting index 1, it looks like 0010 and not 0100. So shifting left is the correct way.

[@williambillemeyling5647]

Does it take O(n) to allocate a n sized boolean array or is it constant time?

[@CarrotCakeMake]

The OS has to zero out the array or you have to do it manually, so low factor linear time.

[@williambillemeyling5647]

@@CarrotCakeMake if i did a c style array I assume it would not have to zero it out, which would make it constant time. But of cause you would basically always need to zero it out.

[@nikhilgautam2857]

can bitsets deal with negative numbers ??

[@harrychen3523]

is there a data structure equivalent to bitset in python ?

[@s.m.miloyrahman4352]

when I use bitset in my computer it show Segmentation fault

[@SamareshMaity231]

Thankyou

[@ChandraShekhar-by3cd]

Could someone please explain the Statement : can = can | (can

[@manavkushwaha8477]

actually if you print the bitset, you'll get to know that the bitset[i] starts from the right. That is when you set bitset[0], the rightmost bit gets set to 1. So we right shift the bitset.