Competitive Programming - Getting Started & Acing It【w/ @PriyanshAgarwal】

Key Takeaways

All right. We're live. I think I'm just going to assume that you know, we're live and it's working. And we see like I see that you know, there are 81 people people watching right now. Um assuming you know, you all can hear us. Thank you for being here and thank you for being here, Priyansh. Thank you so much for inviting. Looking forward to this live stream. Yeah. Uh So let's just you know, get right into it. First of all, did you want to introduce yourself and your background on competitive programming? Um yeah, sure. So hi guys. My name is Priyansh Agarwal. I'm pursuing an undergraduate degree in computer science. Uh right now I'm in third year. So just one more year to go for until college ends. Uh apart from that I've been doing competitive programming for like the past 2.5 years. Uh I do have some remarkable achievements in that as well. For example, I have Google Kickstart you know global rank six and India rank one in the recent Google Kickstart rounds. And yeah, apart from that I've been creating a lot of content as well around competitive programming on my YouTube channel. Uh and yeah, I love teaching competitive programming as well. Cool. Um yeah, I was kind of curious where do you think like you know, that passion for like uh teaching comes from for you? Um okay. So it's not like uh you know, I had this passion for teaching from from a very long time. Uh since I started content creation, I guess I started enjoying it a lot. And I realized that if I can you know, explain some concept that I have in my mind to somebody else uh in a beautiful way, in a way that they can understand it, you know, that gives me a lot of dopamine. So that's something. Hm. Uh do you feel like like is it something that runs in your family? I mean, don't worry like if this is a personal question, but yeah, I'm just curious. Yeah, not exactly. Like I don't have anybody in my family as such teaching. And yeah, I mean, I would be the first person who, you know, has even started content creation. Cool. Yeah, I'm actually the same way. Uh But Harsh says, "This man needs no introduction." And yeah, I guess you need no introduction. You're already known in this like YouTube world. That feels great to hear. Yeah. Uh and someone's asking like, "Please share his channel link as well." I already put it in the description, so you should be able to Yeah, and it's also there in the title as well. So, YK has tagged me as Priyansh Agarwal, so probably you can click on that and you'll, you know, be uh directed to my channel as well. Yeah. Okay, uh that's probably enough for the introduction. So, let's just get started. Um so, I'm just going to, you know, ask you kind of you know, simply, how should people get started with competitive programming? Okay, so first of all, in order to be, you know, able to start competitive programming, you need to first of all start programming. Uh like you have, you know, competitive programming, so obviously it requires programming. Right, so I would suggest learning any programming language. Um one of my favorite language is C++. Some people in competitive programming also code in Java and as well, I mean, also in, you know, uh Python. So, I would suggest, you know, starting your CP journey by learning some programming language. Apart from that, you'll realize with time is one thing that you'll realize with time is that competitive programming requires a lot of, you know, math stuff. So, if you're good with mathematics, you know, you should be good to go. But if you're someone who's, you know, who doesn't have a lot of experience in mathematics, I would suggest spending some time, you know, learning basics of number theory, permutations, combinations, and basic linear algebra. Right, uh once you're done with this, uh when you're attempting a competitive programming problem, you'll be in a very good position to, you know, uh jot down your observations in a mathematical form. Right, uh and apart from that, you should be like having a good typing speed, I would say. Uh it's not something that is required initially when you're starting competitive programming, uh but uh at one stage, you'll realize uh that, you know, having a good typing speed also enables you to code very fast and also enables you to solve problems quickly. Because essentially, when you're doing competitive programming, you're given a bunch of problems that you need to write a code for. Uh and, you know, this code should run fast enough. I mean, it should run uh in a given amount of time. And also, you should be able to come up with a solution in a given amount of time. Right? So, essentially, if you're, you know, coming up with a solution and are able to code it up really very quickly, and, you know, you're able to submit it before somebody else, you're considered better than them uh in terms of competitive programming, you know, uh level. So, yeah, I guess uh these are the three things that you should look for. Uh learn a programming language, uh have some experience with mathematics, not a lot, and again, like, if you have a good typing speed, I would say 30 WPM, 30 words per minute, or something like 40 W words per minute, uh you should be in a good position. So, yeah, I hope that that answers your question, Mikey. Yeah, definitely. Um it's interesting that you mentioned math cuz I was kind of saying the same thing about, you know, coding interviews, like math is like really helpful. Um And yeah, I mean, uh if uh if I were to put it this way, uh math is even more important for competitive programming than it is for interviews and data structures algorithms. Because if you look at data structures and algorithms, you have a certain, you know, type of techniques that you can employ to solve a problem. Right? So, it gets kind of, you know, uh it it is not very mathematics heavy. But when you look at competitive programming problems, they're essentially, you know, uh something like puzzles. Right? So, if you're able if you want to solve puzzles, you cannot be just thinking on an algorithmic level. Right? You need to be able to, you You jot down your observations on a pen and paper, and that's more like, you know, uh jotting down some mathematical expressions. So, it becomes even more important in competitive programming. Yeah, thank you for that. And uh before we started going live, you were mentioning how um coding interviews and, you know, competitive programming are sort of related, right? Uh yeah, they are related. So, essentially, uh if I were to put it this way, uh if you're very good with competitive programming, uh you have a very good chance of, you know, uh nailing all of these uh coding interviews. Uh this is primarily because when you look at competitive programming, uh you're not just solving puzzle-type of problems. You're also solving algorithmic problems, right? And that is what is expected in most coding uh interviews. They expect you to be able to solve algorithmic uh problems that, you know, might be requiring some data structures as as well. So, if you look at competitive programming, uh people are, you know, essentially solving very hard data structures algorithm algorithms uh algorithms problems in competitive programming. Right. So, I mean, they are somewhat related. If you're good with CP, uh you will be very good with uh DSA in interviews as well. Nice. Okay, so I want to, you know, keep our focus on like uh competitive programming in this one. And there's a question that might be a good place to start. Uh how to get to expert from specialist in 2 months on Codeforces? So, I think like the question before this one is like is Codeforces even the right platform? Like what platforms do you recommend to get started? Okay, so Codeforces is definitely not the first platform that you should be starting your competitive programming journey on. Uh I feel that if you have to start uh CP, uh you can start on a platform like, you know, HackerRank or maybe HackerEarth or maybe even GeeksforGeeks and LeetCode. Right. So, you should start with a platform that is, you know, uh more rewarding. Uh for example, if you look at LeetCode, uh you know, people are, you know, people mostly boast about the number of problems they solved on Leadcode. People don't boast about the rating, right? And this is very different when you you know, compare it to Codeforces. Codeforces is like you know, competitive programming website where in everybody is competing to you know, gain the rating. I mean to increase the rating. So what happened in on Codeforces is that you have a rating system. The person having the higher rating is considered to be at a higher level. Right? So if you just start your competitive programming journey right from Codeforces, what will happen is that you will get really demotivated. People who have experience of about two or three years in competitive programming would be you know, very likely performing very you know, I mean would be performing much better than you. Right? So essentially when you're just starting out and if if you see everyone performing much better than you, you might get demotivated. So yeah, Codeforces is not the right platform to start. I would suggest HackerRank, HackerEarth, GeeksforGeeks or even Leadcode if you just have to start right now. Right. Okay, and I thought you know, you might be able to like you might be helpful for you to you know, share your screen and maybe like kind of walk through the whole process of maybe like you know, getting started for the beginners and then like you know, for you to like prepare for like particular competitions, how to get better and you know, all of that might be helpful. Okay, sure. Let's talk about some websites that are there on you know, that are there for competitive programming. Let me share my screen here. Give me a minute. So I hope my screen is visible. If you can confirm that. Yep, I can see it. Hopefully the the viewers should be able to see it too. Cool. Can we have like a plus one in the chat or maybe a yes or a no in the chat that can confirm if my screen is visible? Yeah. And then we can get started. Yeah, I think we can just assume that you know, it's visible and we can continue. Okay, sure. So I'll just show you some websites that are there for you know, getting started. First of all is HackerRank. Right? So this is one website. Um And I'll just you know keep opening some websites here so that you have an idea. Just a minute. Yeah, I think this one it is. Cool, so this is one website that you can get started at for competitive programming. Other one is HackerEarth. Right. And like I suggested GeeksforGeeks. GeeksforGeeks doesn't have a lot of competitions as such. Like it doesn't have a lot of competitive programming contest. But if you open this website you'll find a lot of you know implementations of data structures and algorithms. So whenever you feel like you want to implement something you can you know refer to GeeksforGeeks and you'll have an implementation there. Other is LeetCode. I mean LeetCode is not like a competitive programming website, but this is something that you can you know refer to if you're preparing for coding interviews as well. But this this can be considered like a good website to just start your problem solving journey. Right, these are the four websites which are I would say more rewarding for beginners. Right, they don't focus a lot on competitions, but they focus more on you know getting you started. So these these are the four websites HackerRank, HackerEarth, GeeksforGeeks and you know LeetCode. Now let's talk about websites that you should be referring to when you're already like at a some level at some level in competitive programming or you've solved some problems you know that are like around competitive programming. So the first website that you can refer to is like CodeChef, then there is Codeforces and the last one is AtCoder. Right, and what you'll notice is that all of these websites they have a certain you know rating system. For example, if you look at this website called CodeChef, this is my profile on CodeChef and this is like my rating on CodeChef. Right, the higher this number the more level I mean the better I'm concerned I'm considered you know when when like my profile is shown. Right, so this does provide you with some metrics. for example, at this rating, which is 2201, my global rank is 603 on this platform, and my country rank is 286. Right. So, you might be having two types of, you know, ratings. One of them is your current rating, and the other is your highest rating. For example, it might be visible here. The highest rating is 2225. Right. And mostly, when you're telling your rating to somebody, you essentially want to tell them that tell them your highest rating. Right. So, this is one platform you can, you know, start attempting problems on once you have some hang of problem solving. The next is Codeforces, right? This is my profile on Codeforces. And again, this has a rating system. Like, my current rating is 19112, and my maximum rating is 2089. Right. And this just shows my like rating graph. Like, for example, if I attempt a competitive programming contest, if I perform well, my rating would go up. If I don't perform well, my rating would go down. Right. So, that's where the competition part comes into play. If you're performing better than people who are at a higher level than you, your rating will improve. If you're performing, you know, worse than the people who are at a lower level than you, your rating will go down. Right. So, this does have some metrics again, the number of problems solved, your heat map, and all of that stuff. And then there's this third website called, you know, AtCoder. This again has a rating system. I'll have to log in for that. Let me just see if I can log in. Yeah. So, this does have a rating system. I don't attempt a lot of problems or a lot of contests on AtCoder. But yeah, this These are the three websites that you should be referring to when you have some hang of competitive programming. Right. The first four are Yeah, yeah, yeah, go on. Yeah, so just quickly, you know, sort of I guess going back to more of the beginner side, like if people want to like get into math or, you know, data structures and algorithms, are there like any particular resources you recommend for that? For data structures and algorithms, again, I would suggest going for GeeksforGeeks, the third website that I showed you showed you for beginners. But if you, you know, want to get into mathematics part of this whole domain, I would suggest you know going up to this website called Project Euler. Uh this is one website that has like you know math specific mathematics specific problems. Uh these are not competitive programming problems, but but some somewhat like mathematics puzzles. So, yeah, this is one website that you can refer to if you want to you know get good at mathematics. Cool. And I guess they can people can just like go through those websites and maybe find some problems to work on, something like that. Yeah, sure. And what uh you can do YK is that you can probably add the links of these uh in the description after this live stream. I can provide you with all the links. So, that should be helpful to navigate. Yeah, sounds good. Um Okay, I think I'm going to take a question from the audience. Uh is STL necessary to start in CPP competitive programming? First of all, what's STL? And yeah. Uh yeah, sure. So, uh this question is very particular to you know people coding in C++. So, STL is uh supposed to be standard template library. And this library has a lot of you know standard functions. Uh for example, let's say you have an array and you want to find out the minimum in that array. One way could be to just run a for loop and find the minimum. Another way could be to use some standard function. Right. So, this library does provide a lot of standard uh template functions and you know a lot of data structures as well. So, uh I mean, for beginners when you're just starting out, let's say you haven't done any competitive programming, you haven't uh you know even started your programming journey, it would not be a good idea to go for standard template library at this point. But, once you get a hang of it, like like I said, once you are you know uh once you're a little comfortable with solving problems and when you're going onto these websites like CodeChef, Codeforces, and AtCoder, that would be a good time to you know learn about this. Because whenever you're implementing some logic uh for a problem, uh this this would come in handy. You would require lesser code and lesser, you know, thinking of your own to implement some logics. But, yeah, it is necessary. I mean, uh STL is necessary, but uh not uh for for a, you know, complete beginner. Thank you. Um I think the related question is like, what programming language should people use for competitive programming? Right. So, that's like a, you know, uh hot question in competitive programming. Uh Everyone who's starting competitive programming wants to know what's the best language to start. Right. Uh so, uh I would, you know, answer it in this way that first of all, there is this language called C++. This is considered to be really good for competitive programming. Uh like you would have seen just now. The person who asked this doubt, uh you know, asked this doubt which was very specific to uh C++. Right? So, most of the resources that you'll find uh online and, you know, most of the discussions that you find online would be happening mostly in C++. Right? So, it's uh it's suggested that you start uh your journey of competitive programming with C++. But, for people who have already, you know, some experience in some other languages, for example, some people would be could be totally familiar with Java or Python. Then, for these people, I wouldn't recommend switching to C++ just for competitive programming. You can, you know, achieve almost similar results as in C++. I mean, in C++ in your own language as in C++. So, uh you know, uh if I were to just summarize it, uh go for C++ if you haven't just started if you haven't started anything. But, if you have already started and you are familiar with some language, stick to it. And I mean, if you haven't done it for a very long time, then again, you can go for C++. Uh yeah. Cool. Um Okay. So, we're getting a lot of questions about um data structures and algorithms. And I know we just answered it, but do you think it would make sense for you to like share your screen again and just kind of go through some of those websites and show people like what like where to click and stuff like that. Sure, you mean for data structures algorithms? Yep. Okay, sure. Right, I hope my screen is visible. So again, these are the the websites that I just discussed that I just talked about. These are very CP specific. I'll just keep the websites that are specific for DSA. Right, so one of them is GeeksforGeeks. Like I said, this is one website that you can refer to for any implementation of like any algorithm, I would say. Any algorithm, any data structure that you find online. There's a very high chance that you'll find the implementation of that on GeeksforGeeks. Another website that you can, you know, refer to for just the implementation part is CP algorithms. Right, this is again competitive programming specific. Sorry, this is my laptop, you know, going sideways. Just a minute. Cool. So, just give me a minute. Let's put it aside. Right, I hope that's better. Cool. So, CP algorithms is one website that you can refer to for any implementation of an algorithm. For example, let's go on to something like algebra. Right, and you have binary exponentiation as a topic here. Now you go down and you'll find the implementation of this algorithm here. Right, similarly you can, you know, browse through GeeksforGeeks for any like implementation. For example, this is like a section on GeeksforGeeks. Let's open something like Let's open something like quick sort. Right, quick sort on doubly linked list. Right, so you'll also have the logic of that whole algorithm and you'll also have the implementation here. Right, and they don't just provide you with the best implementation, they provide you with, you know, implementations that are not absolutely optimal. So, you can, you know, go down and, you know, you can understand it along the way. For example, the first implementation could be just order of n squared. The second implementation could be order of n log n. Right, so as you go down, you'll realize that your code is getting optimized and you'll also have more idea about it. Right? So, this is one website that you can refer to for algorithms and data structures. Uh for implementations of, you know, algorithms and data structures that are CP specific, I would recommend CP algorithms. And for practicing, again, I would recommend Leadcode. This is one website I mean, this is one website that everyone uses. So, you can, you know, rely on this website for practicing DSA. Yeah, thank you for that. I think you Oh, yeah. Uh that's that's so good. Yeah, sure. I can share it again like if you have to add something. Sure. Yeah, I think just like sharing the screen just in general is helpful for like adding more visuals. Oh, sure, sure, sure. You want me to share it like uh for the entire duration? I can do that, yeah. Yeah, yeah. That that might actually make sense. Um Okay. All right. We have a new question here. By the way, it's been 20 minutes uh so far. How how are you feeling so far, Prem? I'm feeling great. I mean, uh answering all of these doubts, I feel, you know, privileged to be here on your channel. Uh your channel is like really huge, so yeah. Uh feeling great up until now. Cool. Yeah, I mean, it's it's good to have you here, and it's good to like um like virtually see all the viewers here, too. There There are almost like 300 people here, which is really cool. That's amazing. Yeah. Um Okay, so this question says, "I recently started learning uh DSA. I'm getting how to implement uh like stuff, but facing difficulty while solving problems. How should I approach it?" I think that's a question that everyone who's starting DSA or problem solving would ask. Right? So, let me just tell you that, you know, uh in the beginning, it might seem really overwhelming. You look at a problem, you don't have any idea how to solve it, uh but trust me, with time, it gets better. Uh once you have solved a lot of problems, uh like in my case, if I show you my Codeforces profile, uh and this is just one website that I've solved so many problems on. There are other websites that I've solved a lot of problems on. So, if you look at this, I have solved almost 1,900 problems. Right? So, that's just huge, right? And I've been doing CP for around like I registered 3 years ago on Codeforces. I've been very active ever since. Right? So, if you look at my initial graph, like if you look at these few performances initially, what you'll see is that my graph isn't going up, you know, from the very beginning, right? Uh in this phase, my graph is going down, like my rating graph is going down. Right? And once I have some hang of competitive programming, you'll see that uh my graph is going up now. Right? So, this is something that will happen with almost every one of you. Initially, you'll, you know, be totally overwhelmed by the fact that all of these problems are so difficult. But once you get the hang of it, you'll realize that this is actually enjoyable. Once you start enjoying problem-solving, then, you know, I mean, you would put in a lot of effort to learn things that you don't already know. And that's that's where the growth comes in, right? So, yeah, if I were to answer it, it's just about practice and experience. The more effort you put into it, the better you will be. Yeah, I you know, I I actually feel the same way, like I feel like people should start with like easier ones, like, you know, like you were saying, LeetCode, uh HackerRank, and even like Codewars, I think it's becoming popular recently. It's I if I understand it correctly, like it's more for beginners. Um Codewars? Uh I haven't heard of Codewars as such. Uh Yeah, some something something like that. I'll like I'll put like all that info in the descrip you know, description later. Um But I know like people people struggle with, you know, LeetCode mediums sometimes. So, they they can just start with, you know, LeetCode easy, like you know, one easy problem a day. Yeah. Exactly. So, like if you look at LeetCode, you don't just have very difficult problems, you know, you can browse through and just select the difficulty that you're comfortable with, right? For example, if you're comfortable with you know, hard problems, go for hard problems. If you're comfortable with just easy problems, then start with easy problems. Once you start getting the hang of it, let's say for example, you're solving two easy problems, try including one medium problem into your practice session. Once you get comfortable with solving some medium problems, include more medium problems. So, you keep increasing your level bit by bit. Yeah. Yeah, I really like that approach. Uh okay. So, you know, I'm I'm looking at like questions from time to time from the audience and we're getting a lot of questions about recursion and dynamic programming. Like, do you have any tips on those? Um okay, sure. So, let's begin with recursion first of all. If you have to learn recursion, I would recommend going on to YouTube or you know, uh yeah, I mean, go on to YouTube and look at look for any playlist that is there for recursion. So, like you if you look at a playlist, you know, on recursion, just keep these pointers in mind. The first few videos should just talk about how you develop logic, and then there should be some videos that you know, help you solve some problems on recursion. So, once you do this, you'll realize that you also understood the logic in the first part, and then you you know, solved some problems on it I mean, by taking help of the you know, creator who's creating that video. After that, you can go on and solve some problems on your own. And this way, I mean, this is exactly how you learn any topic, right? Uh if I were to like, you know, should I give some resources for recursion? Like, uh how do you want me to go about it? Yeah, sure. If if you could like, you know, share on your screen that would Sure, let me like open this YouTube stuff and let me just put in recursion here. I mean, that is what I do when I have to learn anything for that matter. Like, you know, you can probably go for this video. This has one video and this just says recursion in one shot. So, you can go for this video. You might have some playlists as well. For example, there's this playlist introduction, I mean, recursion basic to advanced backtracking series. This has like 19 videos, right? So, I think you you can go for this video. Right? For example, if you look at it, first of all, it talks about some logic, then how do you build logic, parameterized recursion. After that, like they have some problems on it, right? A combination sum, combination sum two, and all of that. So, this this could be like a this could be like a great start. I would recommend going for this video if that's in English. I'm not really sure if that's this is in English or is or it is in Hindi. Uh but, yeah. You can choose your language and you know, go for that. Cool. So, uh yeah, I think I I missed about the dynamic programming part. Uh so, once you're done with recursion, you would have a you know, better hand at dynamic programming. Uh because dynamic programming is nothing but, you know, essentially optimizing your recursive codes, right? So, again for dynamic programming, I would recommend this channel that is there on YouTube. Uh Uh this is one by Kartik Arora. This is like one place that I learned dynamic programming from. So, you can, you know, head to this uh channel and, you know, learn about uh dynamic programming. Uh so, if you look at this channel, this has like a lot of stuff on dynamic programming. For for example, this series, uh dynamic programming beginner to advanced. Then there are, uh you know, series on digit DP. Then there is a series on DP with bit masking. Right? So, I think this this could be like a one-stop channel for learning dynamic programming. And yeah, after that, if you want to solve some problems, I would recommend going for this website called CSES problem set. Right? So, you look at this dynamic programming section, this has a lot of amazing problems. Uh so, I would recommend solving the first uh at least 10 or 12 problems from this section. Uh the last few are kind of a little difficult. So, if you're just starting out, I I would recommend trying out the first 10 or 12 problems. Uh but, if you're already comfortable with dynamic programming, I would recommend solving all of these problems. For dynamic programming, yeah. Cool. Thank you. Thanks for sharing all of that. And I just want to quickly mention, you know, I have videos on like recursion, dynamic programming. Uh Oh, sure. You can check out CS Dojo as well. I mean, that's again a great site. Yeah, thank you for that. you would be having some playlists, I guess, right? Yeah, I have some playlists up. But, the best way to do that, I guess, just to define like on YouTube search. People can just search like CS Dojo, dynamic programming, recursion, you know, different things. Let's do that. Bye. Uh I don't want to like talk too much about myself. So, let's Yeah. Let's see if there's Let's Let's close this. Yeah. Uh actually, there there's this interesting question. Okay. Um there are built-in data structures in many high-level programming languages. So, why do we need to learn it? Okay. Uh that's an interesting question. So, uh let's say I give you a problem that requires you to use uh some data structure. Uh for example, which data structure should we take? Uh let's say you want to, you know, uh implement some problem in graphs, right? You might have some inbuilt implementation for graphs available in, let's say, Java or C++. But, now if you want to, you know, do some modifications in the code of the graph, right? Uh you can you can't do that if it's already available as an inbuilt library, right? Uh but, if you want to solve solve some problem, you might have to tweak in a lot of stuff there. For example, if you look at this data structure called segment trees, right? I don't think any language uh or any programming language any high-level programming language has its inbuilt implementation. Uh but, yeah, even if they do have it, uh you would essentially have to write a lot of code to tweak it. Right? Uh so, yeah, I think it is very important to, you know, understand how all of these data structures are implemented because at the end of the day you might have to, you know, re-implement them or re-implement them or, you know, you might have to make some changes in them. And again, like, you know, solving some problems that are data structures or algorithms heavy build up your problem-solving skills as well. So, when you are, you know, working for some, let's say, big tech company and you want to implement some logic and they don't have some inbuilt implementation of that data structure, you know, you could, you know, write it on your own. So, I think that's something that something that, you know, this whole comes into play. Um I'm curious, like, when you're working on a competitive programming problem, are you allowed to use, like, you know, external libraries? Do you write your own libraries? Okay, that's actually a very interesting question and an amazing question because, like, I used to be of this opinion when I was starting competitive programming that I cannot use any external code. I cannot use any external library. I will have to write everything on my own. But, that's not how it works. So, if I if you look at my GitHub, I do have this whole, you know, let me open my GitHub. Sorry, my laptop is like really far, so I have to, you know, reach out for it. Okay. So, this is one website this is one, like, you know, repository that I have of my own for some inbuilt, I means, for some, you know, template codes. For example, if I go on to something like range queries. Right? And if I go on to segment tree. So, this is the code of a segment tree, right? You look at this, this is like huge. So, let's say you have a problem on Codeforces that requires you to use segment tree. Now, you cannot, you know, implement that whole segment tree logic on your own at that very point, right? So, having some, you know, template codes ready readily available for you does help. I mean, if you do if you if you feel lazy and you don't want to implement all of these codes on your own, you can, you know, uh to this uh public repository that I have of my own, CP templates. This does have a lot of implementations uh this does have a have implementations of a lot of algorithms. For example, HLD as well, heavy light decomposition. Now, you look at this code, this is like huge. You wouldn't essentially be, you know, uh coding this on spot. Right? This is this is just insane. This is huge. So, yeah. Uh you can use external codes and uh it is always preferable to use, uh you know, external libraries and external repositories to pick up codes Good stuff. All right. Um yeah, that that actually kind of gives me a lot of uh kind of follow-up questions, but I'm wondering like if if we it would make sense for us to like go through maybe one or two questions. Um I don't know, like I'm I'm thinking like LeetCode easy, medium, or HackerRank, like something on the easier side, so we can go through it quickly. Or or maybe like if um depending on like how comfortable you feel, we could go like for something more challenging, too. Yeah, we could go on for something challenging, but it's just that my laptop is a little, you know, uh little away from me, so it's kind of difficult to code. Uh but yeah, we can go for uh any problem. Let's let's see any problem that we have on LeetCode, maybe. Or let's say we go on Codeforces. Yeah. So, let's go for problems that I can pick up some easy problem because then, uh you know, I don't want to be seen as, you know, somebody spending a lot of just a lot of time on the stream just thinking about some problem. Right? So, let's pick up some easy problem. 800 is supposed to be like the easiest level on Codeforces. So, um let me just, you know, sort them by the number of submissions. Right. So, do you want to pick up this problem? Can we solve this problem? Yeah, let's try it. For sure. Okay. So, let me just read through it and let me increase the font a little so that everyone can see this. Okay, so we have this question. One day three best friends. This is something that I haven't solved already, right? So, let's try to solve it on spot. Uh one day three best friends Petya, Vasya, and Tonya. I don't know how to pronounce that. Uh decide to form a team and take part in programming contest. Participants are usually offered several progra- uh several problems during programming contests. Long before the start, the friends decided that they will implement a problem if at least two of them are sure about the solution. Right? Otherwise, the friends won't write the problem solution. The contest uh this contest offers n problems to the participants. For each problem, we know which friend is sure about the solution. Help the friends find the number of problems for which they will write a solution. Okay, great. So, if you look at this problem, uh what they're telling you is that you have n problems, right? I mean, in this problem itself, let's say you have n questions. Right? And you have these three players. Let's call them A, B, and C. So, if you look at this matrix, uh I mean, these are like, you know, let me just show it to you. Okay. So, I haven't read the input part here. The first line contains n. N is the number of questions that are there in this problem. The number of problems in the contest, then n lines contain three integers each. Right? So, for example, if you look at this uh you know, this sample input. So, this has two problems in it because it's written two here. Right? And for each of these problems, you get a list of three numbers. Uh for example, let's say for the first problem, you have 1 0 0. This just means that A is comfortable solving this problem, B is not, and C is not. Right? Similarly, if you look at the second problem, uh A is not comfortable solving it, B is comfortable solving it, and C is also comfortable solving it. Right? In this problem, what they're asking you is to, you know, tell them the number of problems uh that, you know, they will write a solution to. And there's a condition to this whole thing. The condition is that if you have to write a solution for a problem, at least two of the three people should be comfortable solving it. Right? For example, let's go through this sample input. So, if you look at the first problem, it is, you know, I mean, two people are comfortable solving it. So, that's essentially one potential problem that you can solve. That you can write a solution for. Right? For the second problem, again, all three of them are comfortable solving it. So, we'll write a solution for it. For the third problem, you'll see only one person is comfortable solving it. Right? So, we won't write a solution for it. Fine. So, if I were to implement it using code, let's go about doing that. So, this is some code that I've, you know, written beforehand. Let me erase all of this. Now, again, if you look at this whole entire code that I have here, you know, this is like some template code that I have already available for me. Right? I mean, I will start writing my solution from this point. So, I'm using C++. I mean, this is like a just this is just like a walk-through, you know, on how you submit problems on a on Codeforces. Right? So, let's take the input int n. Int n is what? n is the number of problems that, you know, you will be getting for this whole problem. Right? And then you have this what? You have three integers for every problem, right? So, let's keep an let's keep a variable called answer. Answer is the number of, you know, number of problems that we'll write a solution for. Right? So, we go through n problems and we take in the input. Right? Let me just see. Right? So, these are the three inputs that I've taken for each problem. And what I'll do is I'll just check whether, you know, two people can solve this problem or not. And how can I do that? Like, you know, one tells me if I have one written here, this just means that that person is comfortable, right? So, essentially, I can just add them all up and see if, you know, that number is greater than equal to two or not. So, if a + b + c is greater than equal to two, I just add one to my answer. What does What does this imply? This implies that this problem is solvable by me. This This problem is, you know, something that all of these three people will be writing a solution to. Right? And at the end, you just print this. Right? I hope this Let's see. Okay, let's copy this input here and let's see if our output is coming out to be same. Okay, we have two uh two was the intended output here. Uh we're getting two. Let's copy another sample input. Now, what you would uh you know observe here is that in this problem you're given some sample inputs and some sample outputs. Uh sorry. Here. So, if you look at this problem, there are some sample inputs and some sample outputs. What does this mean? This is not like you know the test cases on which your solution will be tested upon. These are just sample inputs and outputs, right? Uh essentially, your problem will be tested on a lot of other test cases as well. Your your solution will be tested on a lot of other test cases as well. Right. So, let's try to submit this problem. Let's copy this code and let's submit it. And let's see what is the verdict that we get. And I just hope I've read this problem correctly because I don't want to end up, you know, getting a wrong answer or something like that in a very easy problem. Okay. So, now you look at this uh uh you know submission that I made and the verdict is accepted. What does this mean? This just means that I have a correct solution for this problem. Right. And you look at this solution that I submitted on this problem. I have a wrong answer on pretest five. What does this mean? This just means from a list of test cases that this problem has, my solution failed on the fifth test case. Right? Uh let me decrease the font here to you Sorry. Yeah. So, now if you look at the solution, this was I mean this is one huge solution. Obviously, I wouldn't have implemented it on spot. I would have picked up some code from my library uh from my repository that I have. Now, look at this. Uh this was the test case that was there for this problem. The output uh okay, sorry. I'm somehow, you know, pressing uh this whole thing. Yeah. Now, you look at this uh problem. This was the test case that was there in this problem. The output that my code generated was 499. But, the answer for this test case was zero. Right. So, this will give me a wrong answer. My uh solution will be considered accepted if it passes on all the test cases. Right? This was one solution uh wherein I got a wrong answer. Then similarly, we have this verdict called time limit exceeded. Right? If you look at this code uh on this last test case uh this test case, my code, you know, uh returned this verdict. I mean, I got this verdict called time limit exceeded. What does this mean? This just means that while running my code on Codeforces, Codeforces wasn't able to get the answer in a limited amount of time. Right? For example, if you look at this problem, if let's say I run an infinite loop, right? Let's say I run an infinite loop before I do anything. Sorry. Right? This is like an infinite loop, right? So, let's save this and let's submit this solution on Codeforces. Right? Let's have people guessing in the chat what would we get as, you know, an output. I mean, get as a as a verdict. What do you guys think we'll get as a verdict? Will we get wrong answer or will we get time limit exceeded or will we get accept? Or will I get compilation error? If there is if there if somebody can spot some compilation errors in my code. I mean, that that would be interesting. Let's see. What are we getting? So, this is running on the first test case, but but we have an infinite loop, right? So, this gives this gives me this verdict called time limit exceeded on the very first test case. Right? So, I hope YK that was helpful like, you know, going through this problem. Although, this was very easy, I didn't have to think a lot on this. No, that's that's actually really helpful. Um So, like in each of these problems, the input is always like a text file and output is uh just a single uh value. Okay, that's a good question. Again, uh the input is uh the input could be like a text file, but the output could not be just, you know, one uh one output like one character or one number. For example, if you look at this output, this is like a this is like some peculiar stuff, right? So, it's not essentially always a number. It could be some string as well. It could be some entirely I mean it could be just one line as well, right? So, it could be anything. You just have to print the output in the way that they expect you to print it. For example, look at this problem. Let's say instead of printing one let's say I just print something like this. Let's I print two before printing one. Now, what do you expect? Would you expect getting a right answer or a wrong answer? Obviously, you'll get a wrong answer, right? Because Codeforces wants you to print one, but you're printing this two one. This is not intended. Right? So, I mean you just have to follow what you know they tell you to output. Hi. Um by the way, it's it's been 40 minutes so far since the stream started. How are you feeling? I'm feeling great. I mean you know if I can solve some problem on stream, that's like a totally different feeling. So, essentially if you look at my YouTube channel as well, most of them are competitive programming streams. Right? So, essentially I'm just solving some problems on those streams and it feels great. So, yeah. That was great. Nice. Uh yeah, I'm wondering if we can like quickly answer a question and try solving another problem if you're down for it. Yeah, sure. Like probably we can try out some difficult problem because these are like very easy and they don't require any thinking. Yeah, sounds good. Let me just you know stop presenting for a while and let's see if you have some doubts in the chat, right? And then we can get back to presenting. Yeah. Uh so, the question we have here is it would be great for beginners if you tell them about some of the biggest CP contest in the world. Okay. Good question. So, first of all, you have have all of these websites like Codeforces, CodeChef, AtCoder, right? All of these websites you can refer to for solving problems and also for attempting competitive programming contest. But these are not like you know very prestigious uh I mean uh you know contest that are known by everyone. Right? So, there are contests like Google Code Jam, Google uh Hash Code, Google Kick Start. Uh then there are contests like Facebook Hacker Cup, CodeChef SnackDown. Right? So, there are like a lot of contests like these. These are, you know, very well known. Fine. So, probably we can add the links to all of these in the description after this video. Uh it would be very, you know, difficult to like go through all of them because there are just a lot of them. Yeah, sounds good. Um yeah, I mean, if you if you want to solve another problem, I think people would like that, too. Um sure. Just give me a minute. Let me go through the chat and see if we have something interesting. Yeah, um people are uh someone's asking, you know, Python or C++. We are, you know, we already answered it earlier. Basically, C++ if you're just getting started, but if you're already familiar with like Python, Java, or other languages, you know, don't switch right away necessarily. Like start with what you have and then yeah, switch if you want later. Great. Uh okay, so somebody's asking, should we go for a LeetCode problem uh instead of a Codeforces problem? Yeah, I think we can do that because that's like a totally different environment. So, let's go for a LeetCode. And let me pick up some problem. I mean, I don't want to, you know, end up wasting a lot of time just explaining how I'm thinking about the solution. I do want to spend some time explaining how you can, you know, attempt problems on all all of these platforms. Right? Uh so, I hope this is Yeah, this is my account only. And yeah, I mean, for that matter, I haven't done a lot of LeetCode. Uh like if you look at my profile, I haven't solved a lot of problems as such. Like only 33 easy, 66 uh sorry, 56 medium, and just 15 hard problems. So, yeah, mostly I do attempt contests only on LeetCode. I don't uh you know, end up spending a lot of time solving problems. So, let's see. I don't even know how to navigate on this platform so much. Uh let's see. Okay, let's go on to problems only and then Let's pick up some easy problem only for now. We don't want to, you know, just waste time trying to think about solutions. Yeah, I think easier medium would be okay for for you probably. Yeah, I mean for me anything is okay, but I don't want to end up, you know, just making this whole stream like a competitive programming problem solving stream. Let's pick up this problem. Let's see. I think it's okay. People probably enjoy that. Okay, sure, sure, sure. Let's let's go for like something like a medium problem. Yeah, medium sounds good. Cool. Let me just read through this problem if I've already like since I've already opened it. Okay, so I think this this is not interesting. Let's This is like very easy. This is just inbuilt implementation you can use. Right, let's go for something like medium. How do I set the difficulty? Yeah, and if you're in the chat, tell us what problems you want us to solve. Yeah, and in fact, you know, don't just tell us what problems you want to solve, but let's say if if picked up some problem, think about approaches to, you know, solve that problem. Right, so let's see which problem do you want to like solve? Swap nodes in pairs, something like this. Should we go for this one maybe? Uh so the nice thing, you know, to me about LeetCode is like I think it shows like how many people like like, you know, like the question. I don't know if it shows that in this place. Oh, yeah, yeah, it does show that as well. So I think we should pick up some problem that is like, you know, liked by some people. So uh I don't know what is this. Implement a strstr. How about 22, generate parentheses? Or yeah, wh- whatever you want, I guess. Okay, I think this is like a linked list problem. I don't really like, you know, playing up with linked list. So, that's not something Yeah, I was linked list is more like the uh data structures algorithm. It's not even about competitive programming. Yeah. So, uh How about What were you suggesting? Bracket generating bracket sequences? Something like this, right? Uh which one? Uh you said something around bracket sequence, I guess, something like that. go to 22. Yeah, scroll down. 22, okay. Okay, 22. Generate parentheses. All right. Okay. So, this problem is uh given n pair of parentheses, write a function to generate all combinations of well-formed parentheses. Okay, that's interesting. And uh I mean, n is uh you know, n is the number of brackets, I mean, the number of parentheses that you want to use. For example, if n is equal to three, you want to use three opening brackets and three closing brackets. Right. Uh so, I mean, if I were to just implement it in a very brute force manner, what I could do uh do is, you know, just uh have this thing what? Like, I can just, you know, uh pick up any bracket sequence. I can pick up this first one, this this first bracket sequence, and I can just, you know, uh uh check all of its uh you know, I mean, how should I put it? Like, I can just permute it, right? I can just consider all the permutations of this string, and if uh any of them is valid, I just include it in my answer. Right? So, how does that sound? You know, this approach. I mean, just pick up the first sequence and just uh you know, uh do all the permutations on it. Uh that doesn't sound doesn't sound like that uh efficient, right? Yeah, it's not it's it's not definitely it's not efficient. But, if you look at the constraints here, n can go up till eight, right? So, I mean, it won't run, but this is something that I want to just put put up, right? Uh so that people can, you know, look at how we're approaching problems. Right? So, I mean, that's that's one approach, but that wouldn't run. Uh again, we haven't really talked about time and space complexity, uh but the solution that I'm suggesting right now is like, you know, 2n factorial. So, if you have n brackets, I mean, if you have n as the input, you have 2n brackets, right? And if you consider all the permutations of it, that's like 2n factorial. So, here it would be like 16 factorial, right? So, 16 factorial is like really huge and it won't work. Right? So, I mean, I hope that that makes sense, like, you know, in terms of time complexity, it's really difficult to explain right now because I haven't really talked about time complexity. But just assume that the approach that we discussed right now was really inefficient in terms of time. Right? I hope that's that's fine, like, you know, saying it in this way. No, yeah, I think that's pretty clear. Cool. So, how do we go about generating all the valid, you know, parentheses? I mean, that's the approach that we just discussed was definitely, you know, not the most efficient. But another approach could be something like this. Let's say, uh, you know, we have int n as the number. We can, you know, have some opening brackets and we can have some closing brackets, right? So, let's say we have opening equals to n and closing equals to n, right? And initially, how many brackets have we used already? Int used equals to zero. Right? So, this is our initial state. Our initial state is, you know, we have zero brackets that we've used already and we have how many remaining brackets? We have n opening brackets remaining and n closing brackets remaining. Right? So, I can just, you know, write a DP solution, like, you know, DP of used {comma} opening {comma} closing and try out all the possibilities and then the complexity would be what? Complexity would be time would be, like, order of what? Order of n into n into n. And space would be again order of n into n into n. Right? So, how does that sound like? Should we go about implementing the solution? Sorry, could you explain that again? Okay, sure. So, we have this input which is int n, right? What does this mean? This just means that I have n closing brackets and opening brackets. Right? So, essentially I can just have a dynamic programming state. What could What would that state be? It would be just simply the number of brackets that I've used till now. Uh you know, how many brackets uh do I have remaining? I mean, we don't even need this used thing. So, let's just have this way. Right? So, the final uh time complexity would be order of n squared and the space complexity again would be order of n squared. Uh now, let me just explain the solution. It's very difficult for beginners to understand because obviously this is like a medium problem. But, look at it this way. Initially, what do you have? Initially, you have n opening brackets and you have n closing brackets. What would you do now? You would try to place some opening bracket or some closing bracket at the index that you are at. Right? So, if you're at any index, you would want to essentially place some opening bracket or some closing bracket. That's the two possibilities that you have, right? And I mean, it doesn't really matter which opening bracket are you placing placing? Are you placing the first opening bracket or the last opening bracket? Right? So, that's like a simple dynamic programming state. Uh like, does that make sense? Uh yeah, I think so. So, you're What I'm doing is something like this. DP of opening closing. And uh this is, you know, considers all the ways. Uh are you going to try to uh create an array of brackets and then kind of concatenate them into a string later? Yeah. Yeah. Yeah. Yeah. But, uh to be honest, you know, it's it would be really difficult to implement it on spot, you know? I mean, it's not difficult to implement, but that would just take up a lot of time. So, that's primarily why I did not want to choose a problem that requires a lot of implementation. Right. Yeah. I hope that that doesn't sound, you know, something like, you know, me being very incompetent. No, no, no, no. I I totally get that. Like, it's it's hard to like solve something on the spot. Um Did you But, yeah. How about, you You how about, you know, we just implement the first approach that came to our mind? I mean we could show we could show how you know we implement problems on lead code and how we submit them. Yeah. Right. So, let's say if you talk about the first you know uh bracket sequence that you have already is something like this. Let's say if we have string initial. Right? Initial is something like this and we just place n opening brackets first and then n closing brackets. Right. So, this is the first initial string that we have. Let's try to print this and let's see what we're getting. Let's run this code. Okay, I think we'll get some compilation error because just a minute. We haven't returned anything. Okay, let's see what is the error that we're having. We have this Right. So, this is what we're getting initially. This is the first bracket sequence that you have in the line, right? And next what we can do is we can consider all of its permutations. Right? And whichever of them is like a valid permutation, we just include that in our answer. So, let's try to do it that way. So, we have vector string. Sorry, we already have that available. So, let's do something like this. Okay, so let me just explain this function which is like the next permutation. What does what this does is that it takes a permutation of a string or an array or a vector and just it just returns the next permutation if it's available. If it is not available, it just you know exits from this loop. So, this is this this is the function that I'll have to implement which is this valid valid. So, I just have to check here whether this permutation that I'm considering is valid or not. Right, how do you check whether a bracket sequence is valid? A bracket sequence is valid as long as you have more or you know equal number of opening brackets before closing brackets, right? So, we could have in sum equals to zero and we could just iterate on the string. So, if I equals equals to opening I just do sum plus plus. Else I do sum minus minus. And I just take check if sum is greater than equal to zero. Sorry, if sum is less than equal to less than zero, I just return false because that's not a valid uh subsequence, right? A valid sequence. Cool. So, let's try to run this code. And let's see if I'm getting some compilation errors. Okay, I haven't named it correctly. Okay, so do you see that you're getting all of the valid subsequences here when n is three? Uh and we're getting a right answer. So, let's try to submit this although you know we we won't get a right answer because uh this is like you know very heavy in terms of time. So, but let's see. Let's try to submit it and let's see what you're what is the verdict that you're getting. Okay, somehow we're getting success. I mean that uh it shouldn't have happened. Uh some I mean some more reasons why I should hate Leadcode probably. Yeah. if n Yeah. Yeah, with with eight brackets, it's it's probably okay, I guess. No, no, it's it's actually not okay. Like if you look at it, we have something like this. Uh if n is equal to eight, the number of brackets that I have are what? We have n We have two into n, right? So, that's like 16 factorial ways. And I don't think that should work. Uh how many 16? 16 factorial. Okay, let's consider it this way. Uh so, we have six factorial. Uh six factorial is what? Six factorial is 720. Right? So, we have 720 into 7 into 8 into 9 into 10 into 11 into 12 into 13 into 14 into 15 into 16. Okay, this is really huge. I mean, uh if you look at Uh sorry, are you able to see this? This It is this huge. Yeah. And this this one run. But But somehow it's running, I don't know how. But yeah, that's that's not the most efficient way to solve this problem. Uh like I was saying, the DP approach that I was suggesting is much better. Like, you know. Cool. So, yeah, that's that's how you submit solutions on LeetCode, right? Uh so, with with a DP approach I guess. So, like, you know, when you when you call like uh when you call the same function like recursively you would like append uh to what you have, right? Mhm. Right. Right. Right. Like you would start at like index zero and then kind of uh go go go to like index one, two, three, and then just like keep adding stuff just like that. Mhm. Yeah. But we'll also, you know, be storing what is our current state. So, essentially, we won't be repeating everything again and again. Right. Right. Uh Yeah, I guess generating everything is it's not it's not an efficient approach. Uh the dynamic programming approach? Oh, I mean like uh the initial approach that you were just talking about the the dynamic programming is it's the like more efficient approach, right? Yeah, definitely. The The dynamic programming approach, you know, is much more efficient and it will be only considering the valid sequences. Right? So, we won't be even going into the invalid sequences. So, that's That's definitely better than this, yeah. Cool. Um Do you ever use like Python to solve things, by the way? Um I don't know. I haven't really used a lot of Python. Uh what I do is sometimes, you know, if you look at C++, like if you look at this number, let's say I tell you this huge number. Uh let's open Python and we have A equals to something like Let me increase the font. A equals to something like 2 to the power 1,000. Right? If you print uh Okay, sorry. It is A equals to 2 to the power 1,000. Yeah. Now, if you print this number, this is like huge, right? Uh you can't fit this number in C++. So, sometimes when I, you know, uh don't want to get into a lot of precision and all of it all of that stuff, I do end up using Python as well. But for competitive programming, mostly not. Because it's uh it's slower. It's slower than C++. Yeah. Uh yeah, I remember someone was asking earlier like, do you get judged on like time and space complexity or just the run time? No, you only get judged on the run time. It doesn't matter what your space and time complexity is. But it's like very, you know, it's They both are correlated. The better your time complexity, the uh lesser time it will take for your code to run in, right? So, essentially, you're not judged on time complexity, you're you're judged on the run time. Uh but uh in order to be able to code for a particular run time, you'll have to look at the time complexities. Cool. Um Yeah, it's it's been almost an hour, so you know, we can end it if you want. Like Yeah, you know, basically we can end it whenever you want. What time is it over there? Uh it's 10:16 p.m. But yeah, I mean I'm cool like answering some more questions for like 5 to 10 minutes. Uh and then we can end it, yeah. Sure. So, let me just stop presenting my screen. Yeah, let me see if if there are any questions and I think if there's anyone Oh, this one's kind of a good one. Is it necessary to be good at uh data structures and algorithms to get a job? Okay, it it depends on what job you're applying to. So, it kind of totally depends on the type of company you're applying for, right? For example, if you look at all of these fan companies like Facebook, Amazon, Google, Netflix, they do require you to be a very good problem solver and also be very good at data structures and algorithms, right? So, for these companies, uh yeah, you would uh have to be good at DSA uh in order to crack their interviews. But if you look at all of these interviews by these startups, right? Uh so, startups don't really care about a lot uh I mean, they don't really care a lot about your problem-solving skills or your data structures and algorithm knowledge. What they care about is your development skills. For example, if there are two candidates, one of them is a great competitive programmer, is a great uh you know, problem solver. And let's say the other one is very good at, you know, implementing stuff in React or let's say is very good with Python, right? And I mean, that's like a development skill. This is like a problem-solving skill, right? So, startups would prefer the second type of person and uh you know, big tech companies which are established would prefer the first type of person. But again, it's not like, you know, startups are bad or these big tech companies are good. Uh both of them, you know, are paying uh huge amount of money to, you know, their uh employees. So, yeah, both of them are good options. It's not essential uh it's not, you know, totally required that you go go this DSA path and learn all of these DSA and then go for then go apply for a job. You can also be very good at development and then go and apply for a job as well. Yeah, both of them work, but you need to be good at some skill, yeah. Cool. Thank you for that. You know, I I totally agree with that sort of approach. Um anyway, I feel like this is a good probably good time to end the stream. But Yeah, totally. Um Did Did you have any anything like you wanted to add to this conversation we've had so far? Um not exactly like so far it's been great. It was really great coming on this, you know, huge YouTube channel that you have of your own. Right, and talking about competitive programming. Um and thank you so much for like like you know, taking out time for this and you know, scheduling all the meetings and you know, putting out all of this stuff on Twitter so that more people can come and join. And yeah, apart from that like for the people who've like you know, who don't know about me a lot, I also have a YouTube channel on competitive programming. So if this was the conversation that you know, got you some I mean that got you interested, I would definitely recommend you know, checking out that YouTube channel of mine and I hope you know, you find some insightful content there as well. Cool. Um Yeah, I think this like I said this is a probably a good time to end the stream. If anyone's interested in you know, learning more about competitive programming, go check out Priyansh's channel, Twitter account, everything. Everything's in the description and you know, if you're new on this channel, make sure to subscribe if you want and you know, feel free to follow me on Twitter too cuz I've been pretty active on Twitter at Waikiki Dojo. Okay, thank you so much everyone. And have a nice day. Bye.