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
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
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.
@@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
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 !!
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.
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".
@@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
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 !
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
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.
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.
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 !
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.
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)
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.
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.
4:39 why is there a 64 in the denominator?, Isnt the complexity of builtinpopcount no of set bits, which in the worst case here can be no. Of working days D, so should it be just O(N^2 * D)
@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?
Something does not seem right to me. The second example, 10^7 numbers: visited [x] only means the x-th bit of bitset , you cannot just check the x-th item of bitset to make sure if x is visited or not. I think you should first declare an array of bitset. But then your whole logic here is paradox. The if(! visit [x]){...} part means nothing.
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
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.
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
@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.
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
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
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
@@mogovanjonathan
for(int i=0;ia[i][j];
if(a[i][j]!=0){
b[i]=b[i] | (1
and b[ i ] is the array in which we store the schedule representation of each worker
@@umangagrawal228 Thanks sir!
@@umangagrawal228 Its wrong, You cant use a 2D for 1st question, so much space you've wasted!
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
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.
This should be pinned
same doubt till read your comment ty
took me almost 2 hour trying to understand how the logic works until I realized what you have said
This content is awesome. 😃😀 For anyone preparing for competitive programming or even maybe for ds and algo for interviews.
This video is What i have WAITED to see for YEARS . You are FIRE 🔥
15 min for the video and 30 min for understanding.
it would say 45 min well spent :)
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
@@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
@@AbhishekKumar-im2xd thanks man, i ve been waiting so long for this answer. Thank you!!!
@@mogovanjonathan try to write natural numbers above the each digit starting from 1 ,you will understand. What's this???
The knapsack solution is so cool especially optimising the for statement with the shift. Never thought of that before.
Now, I have a complete understanding of the std::bitset. I always had doubts about its complexity. Thanks!!
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
Thank you Errichto! This is splendid...
Thank you Erichto.
Your tutorials are wonderful and helpful.
I hope you would come up with more such videos.
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 !!
Dear Mr. Kamil! Your content is so useful, getting so much new knowledge from you! Thank you!!!
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.
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".
@@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
Thanks errichto for such underrated yet important concepts :)
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 !
Really knowledgeable content sir
I definitely learnt something. Thanks for introducing C++ functions we don't see too often.
I love these videos. You make so articulate content.
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
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.
This is so concise and easy to code in assembler.
Awesome work ! I struggled a bit to get the Knapsack, but it's so clever ! Thanks a lot for the new knowledge !
Doubt in knapsack problem- Why we are left shifting in the code but in the example you right shifted?
The way we write and the way bitset is represented is different.
Today I got to know how much more I have to learn yet...
This make so much sense and meaning and do hope to understand all this video more and more
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.
Brilliant video, we need more Sir ... Thanks
Amazing! Thanks a lot for this content! Greetings from Brazil!
Kindly make other important videos explaining with examples as can be found from the codeforces blogs. I am eagerly waiting
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.
An amazing explanation. Thank you for making these videos!
Can you please create a series on C++ STL. You're an awersome coder.
Thanks for this informative video. Please keep up the good work. It's helpful and is really making the difference!!
in the example explained ,the bitset is from left to right , while in program it is from right to left
Man this is called simple and elegant, GG Kamil, this was superb!!!!!
highly underrated content!
please add some more commonly used algorithms in your playlist, algo lectures. It would be very helpful for us.
damn bro damn, hell of a video.
Keep going dude.
Thanks Errichto! Very nice content!
Dammnn That explanation is so cool. Thank you @Errichto
Thank you very much. It's very useful in competitive programming
That's really awesome 😍
I was looking for some good tutorials on bit manipulation...
Thanks @Errichto 😃
Thanks
Thanks so much bro
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 !
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.
Codeforces custom test too doesn't allow to create a bitset of size 1e9.🙁
the shifting and oring in knapsack didn't make any sense for me until I realized that bitset[0] is the right most bit
Great content , keep up the good work
Very Nice Content .... Good Work Errichto
Nice video. Thanks for posting.
Thanks for your explanation 👍
Nice video
This video was mind blowing
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)
hey @Errichto can u please provide us link of problems on this topic
Thanks Errichto
knapsack trick very brilliant
U R the Best. U R an Inspiration brother
Nice stuff!! Liked it.
Thanks a lot, this is really helpful...
A bit fast paced, appreciate you slow down a bit, thanks.
very well explained
12:26 aren't we supposed to rotate right >>. ?
thats what i was thinking ......
@@adityaraghav8693 i guess only we both were thinking that.
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.
this so awesome, thanks you so much
Awesome... thanks for for this tutorial..
great work!!!
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.
Great video thanks
Thanks for this
Awesome 👍
Awesome!!! Thanks
Please make more!
4:39 why is there a 64 in the denominator?, Isnt the complexity of builtinpopcount no of set bits, which in the worst case here can be no. Of working days D, so should it be just O(N^2 * D)
Thanks for the content...It helps a lot :))
Hey Errichto ! I was just wondering whether multidimensional bitsets are possible or not ... just like maybe 2d bool array
wow, 700+ likes, 0 dislikes. This video deserves it.
In the second problem, is it okay to do "can
Thanks red!
awesome brother.
Never seen a like dislike ratio as this not a single second wasted
i dont think ive ever seen such a good like dislike ratio
Love you bro
@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?
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
Do you have a video or article that explains knapsack? I saw your DP playlist but couldn't find it
What does the variable 'x' represent in the exact Weight W question ?
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.
can you please explain why you divide by 32 ?
Something does not seem right to me. The second example, 10^7 numbers: visited [x] only means the x-th bit of bitset , you cannot just check the x-th item of bitset to make sure if x is visited or not. I think you should first declare an array of bitset. But then your whole logic here is paradox. The if(! visit [x]){...} part means nothing.
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
Hey Erichto,
At 11:59 you said we have to right shift than in coding part you did left shift, please explain.
bro in bitset index start from right
means
5 4 3 2 1 0
like that so we are doing left shift
@@lovishkumar5520 ohh thanks a lot.
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
Thanks for explaining my doubt
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.
use vector for that,man
@@lanfker Yeah i know that lol, i am talking specifically about arrays and bitsets here.
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
@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.
This content is somewhat difficult for me to comprehend. What problems should I solve to get to the level of these problems?
which is better? _builtin_popcount or bitset::count??
Is bool array[70] faster than bitset in MSVC C++17?
I don't understand K = Max_d/64+1
We can handle D≤64 in a single unsigned long long
very informative and conciese video!
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
i see the problem alr, thanks for the amazing video!
why can't I use duplicates in bitset version of subset_sum??
Thankyou