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 !!
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 !
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
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
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.
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.
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)
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.
@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?
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.
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
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!
This video is What i have WAITED to see for YEARS . You are FIRE 🔥
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.
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
Dear Mr. Kamil! Your content is so useful, getting so much new knowledge from you! Thank you!!!
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 !!
Thank you Errichto! This is splendid...
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 !
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 :)
This is so concise and easy to code in assembler.
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 love these videos. You make so articulate content.
I definitely learnt something. Thanks for introducing C++ functions we don't see too often.
Really knowledgeable content sir
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.
Awesome work ! I struggled a bit to get the Knapsack, but it's so clever ! Thanks a lot for the new knowledge !
This make so much sense and meaning and do hope to understand all this video more and more
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
Brilliant video, we need more Sir ... Thanks
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.
Can you please create a series on C++ STL. You're an awersome coder.
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.
An amazing explanation. Thank you for making these videos!
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!!!!!
please add some more commonly used algorithms in your playlist, algo lectures. It would be very helpful for us.
That's really awesome 😍
I was looking for some good tutorials on bit manipulation...
Thanks @Errichto 😃
Dammnn That explanation is so cool. Thank you @Errichto
Today I got to know how much more I have to learn yet...
highly underrated content!
A bit fast paced, appreciate you slow down a bit, thanks.
Thank you very much. It's very useful in competitive programming
wow, 700+ likes, 0 dislikes. This video deserves it.
Thanks Errichto! Very nice content!
crazy knapsack implementation
Very Nice Content .... Good Work Errichto
damn bro damn, hell of a video.
Keep going dude.
Great content , keep up the good work
This video was mind blowing
Nice video. Thanks for posting.
Never seen a like dislike ratio as this not a single second wasted
knapsack trick very brilliant
the shifting and oring in knapsack didn't make any sense for me until I realized that bitset[0] is the right most bit
Thanks
Thanks
Errichto
Thanks so much bro
Thanks for your explanation 👍
very well explained
Nice video
U R the Best. U R an Inspiration brother
Nice stuff!! Liked it.
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.🙁
Thanks for this
Thanks a lot, this is really helpful...
this so awesome, thanks you so much
great lecture😇
Please make more!
Awesome 👍
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)
Awesome!!! Thanks
Great video thanks
hey @Errichto can u please provide us link of problems on this topic
Awesome... thanks for for this tutorial..
great work!!!
Thanks red!
Thanks for the content...It helps a lot :))
i dont think ive ever seen such a good like dislike ratio
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.
awesome brother.
Love you bro
very informative and conciese video!
Thankyou
when I use bitset in my computer it show Segmentation fault
so good
Do you have a video or article that explains knapsack? I saw your DP playlist but couldn't find it
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.
C/C++ is the best
@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?
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.
Thanks for explaining my doubt
can you please explain why you divide by 32 ?
In the second problem, is it okay to do "can
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.
which is better? _builtin_popcount or bitset::count??
Is bool array[70] faster than bitset in MSVC C++17?
why can't I use duplicates in bitset version of subset_sum??
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
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
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 Errichto ! I was just wondering whether multidimensional bitsets are possible or not ... just like maybe 2d bool array
Kaha Se Aata Hai Etna Motivation ~ Mohit🙄🙄
can bitsets deal with negative numbers ??