Transcript
ARC 201 A-D | algorithms problem-solving
From Errichto Hard Algorithms · Episode page · Watch on YouTube
· 2 h 20 min · 13,224 words · 125 timestamped sections
This is the full, timestamped transcript of "ARC 201 A-D | algorithms problem-solving", an episode of Errichto Hard Algorithms published July 11, 2025 (2 h 20 min, about 13,224 words). It mentions 4 people, works and ideas, including AtCoder, Codeforces, C++, Olympiads.
What is discussed, and when
Notable quotes from "ARC 201 A-D | algorithms problem-solving"
After solving, I will maybe say how I think it compares to code versus problems.
about Codeforces · atI will try to do some code forces division one but at coder grand contest I don't I think I never had much fun in those. It's really too hard. It's a waste of problems.
about AtCoder · atC++ 20. I think that's what I want to use.
about C++ · atFreelancing and mainly teaching algorithms, preparing people for Olympiads, for interviews.
about Olympiads · at
Who and what is mentioned in this episode?
Companies & orgs
- AtCoder — Company · Platform discussed · 3 mentions · first at
Primary platform for competitive programming contests discussed in the podcast. - Codeforces — Company · Platform compared · 1 mention · first at
Another competitive programming platform compared to AtCoder in terms of problem difficulty.
Concepts & topics
Full transcript with timestamps
Sound sound. There is sound. Um, welcome everybody. Uh, we're doing at coder today. Maybe starting from from what the regular contest. I think this one also I wonder if one day I should try again heristic contest here. I used to like those. Okay, there's got a regular contest 201. But which problems I want to solve? I don't remember much about the difficulty on that coder. So, let's just try something. Uh, hi MacArthur. Hi everybody. Also, is everything okay? So, are we live on Twitch and with a proper title as well?
and YouTube. Yep. Also, another thing is a great thumbnail. Another thing is there chat. Oh, there is chat. Okay, so I can scroll through. Okay, that's good. Uh, hi Prism. Well, let's see how difficult those problems are. This is rated 500. After solving, I will maybe say how I think it compares to code versus problems. Uh, upload your video with caption. I I'm not sure it's possible for live streams. Yes, I am from Poland. uh bank table out of frustration. Not sure. I'm sure I cursed before but uh when not being able to solve a problem in the year 200 something uh blah blah blah and writers three types by difficulty hard medium easy and every writer has some number proposals for each slot hard medium easy.
Uh for division one we need hard and medium. division to medium and easy. Okay. So for a contest, we want hard plus medium from one outer. Medium plus easy from one outer. Maybe the same one. Maybe not. Is the font size. Okay, by the way, thanks for good educational content on YouTube. Hope you'll never delete those videos. You're welcome. Actually, I don't think I will delete uh a bit larger would be nice. I wonder how it will behave. I think that's fine though. So, I wish that they Can I do this? Oh, yeah. That's great. I can hide the top stuff now. That's good. Also, here's the link
at cutter grand contest. I don't think I'm participating. I will try to do some code forces division one but at coder grand contest I don't I think I never had much fun in those. It's really too hard. It's a waste of problems. Unless of course you appolve. No, I'm not using a Mac. I'm a Windows plus Linux guy. Uh okay. The number of outsour 200,000.
Just want to restart the layout. Nope. Go here. You go here. Oh, if it's not Oh, I see. So, when I we see an outer with some number of problems, let's say seven hard, 10 medium, eight easy, then we can use him in at most seven contests of this type. eight contests of this type, at most 10 in total. In particular, can I say that he will for sure be used for something? Well, it doesn't hurt, I think, to get this number down a little bit. So even if we prioritize let's say hard plus medium let's say we want this outer to provide a lot of hard plus medium uh pairs then still that will be at most seven.
So at least three pairs of this type will be used three pairs medium plus easy because it doesn't hurt at all. After that we we what remains is uh let's say let's see this 75. Now using similar logic if we want to prioritize medium plus easy anyway we can use two of those. So use two pairs of hard plus medium. It doesn't hurt because it doesn't decrease your possibility of how many medium plus easys you can do. And after that we have this which means use I can now provide five pairs of any type hard plus medium or medium plus easy.
So use five any pairs. Is it always possible or was it just a coincidence? Let's let's try more random data. 290. What can we say here? Uh well, oh, if the number of mediums is more than the sum of those, then we can as well limit it. And here for sure we will use two pairs easy plus medium and sorry hard plus medium and 90 pairs easy plus medium and that's it. There will be no of those pairs. And what if medium is small? What if for example we have 2710? Then this we can decrease down to seven. I guess we can have five pairs of this type.
So two and two and then two pairs of any type. Okay, I think that's good. We just need to turn this into code. Uh bigger font size please. I will not increase it over this annoying problems on code forces nowadays to combat traers. I don't see any alternative that organizers can apply. Uh where would you put yourself at math? I mean taco to in your question let's say math master I participated in math competitions I don't have much university level math knowledge but earlier I could participate in national and almost international contests and win some of them okay so let's see if I If I can I'll turn this into ifs.
We end times do something and we have the easy pairs or division one pairs, division two pairs and any we read how many hard medium hard, medium, and easy there are from this outer. And I want to know how many for sure I can make pairs hard plus medium because the easy will be wasted anyway. I can do it as long as medium doesn't drop below easy. I think for example if medium is if medium is 10 and easy is eight then I can create two pairs of hard plus medium and also change font can do this uh so it's medium minus easy.
Uh that's medium minus easy. But of course, I cannot make more pairs than what I'm doing. I am pairing this up with hard. So minimum of hard comma this and maximize with zero I guess because you don't want to say that we make negative number of pairs. hearts decrease by that m decrease by that division one pairs increase by that. Now same logic we will use uh for making those pairs. So if we have 10 medium and eight hard then two mediums we can spare for sure. easy minus equal m minus equal division 2 plus equal and finally so if m is greater than something we use that and finally we have arbitrary pairs so I almost want to say this n plus equal m but I don't think that's entirely correct is it maybe there is some strange case where those other values were zero. Like if if medium is 100, this is zero. This this is and this is zero. Then uh then that stuff did nothing.
Let's see. This is I guess maybe first we can do this. We will not use more. And now is it true that everything is equal? I'm not sure about that. But if so, then this does make sense. Well, H and E can be bigger right from the very beginning. But if I did this because I will not use more then maybe it's true. And if stuff so far is correct which I can check by copying. I can run for the sample test. Well, the assert did not fail. So this is indeed true. Now that I computed number of pairs of every kind, the every contest is made of one division one and one division two. And then any I want to distribute evenly between those two.
Uh so what do I need to say? I think This is for sure. If I'm already have seven contests of this type, 10 of that, then I have seven full contests. And then remains is equal I know diff one plus def 2 minus answer. One of those values was greater than the minimum. So this is what remains. uh out of those this is certain and now with this I need to fill stuff. I need to uh decide what else I can do. So minimum of remains comma any if I have for example seven contests of the one type and 100 to fill as an extra then it's seven full contests then any decrease by that and this is how many you have left of any type. So pairs of hard plus medium or medium plus easy that's flexible.
And the answer finally should be increased by this over two because we have we need one pair of hard medium and one medium easy. So two pairs will increase the answer by one and print the answer. I must say I did not enjoy this problem. Oh and it's incorrect. After getting accepted, I'm going to look at the editorial. Maybe there is something interesting there. Something better than what I did. It seems that my answer is too big, which is a good news. I would not be happy with achieving or obtaining values smaller than the optimal one because I would not know what is wrong and how I could improve it versus here this is almost for sure like a simple mistake doing something illegal creating pairs that do not make any sense that many should not be possible don't look at the tutorial I was going to do it after so after getting accepted Okay. So, I'm doing something bad.
Let's see. By minimizing, I for sure do not create the answer that is too big. Then uh let's also just to make sure assert that everything is positive and not negative. So I take something from heart and medium and I make a division one out of it. I take something from easy and medium, I make a division two out of it. What remains? If I have five easy, five medium, five hearts, it's any pair I can create out of that. uh division one and division two I pair up. I can maybe rewrite this as something easier to understand. It's max minus min.
Uh so if I had seven pairs of one type and five of the other then there are two remaining of one type. Oh now it works. So wait what what was wrong a moment ago? Does that overflow? How can that matter?
Isn't it the same thing? Max minus min. Isn't it equal to Oh, it would need to be twice the answer if I want to do it that way, right? Because here minimum is counted twice. Okay, got it. So, this should work as well. Yep. But maybe I will leave it in this longer form. You see, I wasn't 100% sure about the formula. I just rewrote it to something else that I thought is equivalent and apparently it's not. Uh well, I was lucky that I tried to change it this way. I could as well not see the mistake for another five minutes or more.
Submit. What do we want to use? C++ 20. I think that's what I want to use. Okay, so I did not like the problem. Next time I see something like this, once I realize that it's a bunch of ifs and formulas like that, I will skip it the full problem. And I'm sure that this can be done shorter, but I want to see a way that is actually safer. Like you you cannot make a mistake that easily accepted. So editorial
What? That's some I think this is some very nice explanation for a code that will be five lengths long, but I wouldn't expect anybody to come up with this way of thinking. It's something about achievable number of division one and division two contests creating a regular shape where you if you compute some border points you can compute what is there in between and what intersects y equals x line uh I mean I think just by looking at it I get the idea of which way it goes. It's nice that this interpretation exists but It's obvious for me as also a problem setter in the past that people will not solve it this way.
So what they are doing is there is a simple formula for sure if we only want to maximize division one contests. So just from every outer collect division one contests also separately maximize the number of division two contests and theoretically then you can combine both and then hence minimum of x and y. Oh there is white two y is something else. Oh x and y. So x is the maximum number of division one. Y2 is maximum number of division two. Hence we have minimum of those two counts. Uh and then turns out that additionally you check one more value and that works.
Okay. Magic I'm sure I could understand it in five minutes but I want to move on. Editorials are always like this in cutter. I look at other people's solutions mostly. You know, I often did use the atcoder editorial, though it happened to me that if I wanted to actually understand it, it would take me an hour to solve a hard problem and fully understand what's going on. It's often some kind of magic. Okay. Uh, next. So, similar difficulty and I wonder then what it would be for code forces. So this would be like division 1 a.
I guess it was easy to solve to come up with a solution but tricky to implement and I think most people will produce code that is not far away from mine and items with exponential weights. And there is some value and you run napsac values are big. So nothing can be simple dimension of dp. Uh okay. So we need to be able to do napsac where the pairs weight comma value the first value is always a power of two. So one maybe 100 150 277 4 200 16 something and then I'm sure we will go either from smallest weight to biggest or the other way around.
It's hard for me to imagine something else. Now among values among values like this how many can I choose well what matters is how many full twos I will take right it doesn't matter if I take uh well that there is the given weight let's say the given weight the full capacity is24 this is the naps size if so it doesn't matter if I take one or two of those values because they sum up to the same multiple of two. If you need in the future to pack it with even values then first it doesn't matter if you pack it with one or two ones.
uh and I think what we will do is the P of how many of those we used where size of that is linear then we will move here and we will cut some stuff we want to get amortized time complex amortized linear time complexity or is it easier to go downwards
I know I think increasingly we'll be fine. So after this I will have DP of zero, DP of one, DP of two, DP of three. This is possible weight that is used so far. Before I move on to the weight two and then following powers of two, I don't care which of those two values is taken as long as the total weight is even. So I can compress it to DP of two sorry DP of zero two and four. The three can as well pretend to be a four. Possibly I should also divide it by two. This way I will have a vector. So divide by two while rounding up.
Then this will be DP of 0 012 but also the weight was divided by two. Now what should happen if weight is odd? For example, weight is 15. If I have something like this uh we have after considering that we have DP of 01 23 uh that gets collapsed into DP of both of those collapse to let's say zero and those collapse to one. But what does weight become? Weight becomes let's think seven. the one we used for free this got divided by two. Yeah, I think this is how it goes. So always the total weight when we move from considering items of weight one to considering items of weight two, the total weight we should just divide by two. So now pretend that those new items are of weight one and the the parity of the total weight will affect how we round things. If it's even then we round up. If it's odd, then we round down.
uh the number of total states to consider will be small that that thing is easy uh but now for transitions we can have linear number of uh ones and then linear number of twos I don't want to get quadratic time complexity
we can sort items terms of the same weight. We prioritize those with big value. If this problem was harder, I would believe some that some complicated logic would be needed here. Like we need to think about some convex function stuff like that.
Okay, let's try to solve a problem of just weights one and two. So what should I do? If n is up to 200,000, the weight is from one to two integer only. value of I is big up to 10 to the^ 9. The naps size is big up to well infinity. Hi Ashot. Yeah, welcome. Welcome. How do we solve this?
If the weights are only one then this is trivial. After sorting it will be some kind of prefix sums. Should I do the same for weight two? just kind of sort it but it then it will not apply correctly to this.
Again, if this problem was uh harder in terms of the score, I would think about some convex properties, but this is it shouldn't be 500 problem. If we look at the previous one that I've just solved, it shouldn't be that difficult.
should I know the the solution by now? Also, do you think it's a good idea for me during streams like this one to switch between problems? When practicing on my own, I would do it sometimes because if you're stuck on a problem, I will write this down. Uh during practice, it is okay to well try multiple problems and and switch sometimes, right? in particular, you don't want to quickly go to the editorial and sometimes taking a step back and doing something else, it helps you later get fresh ideas for this problem. That being said, during a stream, I don't think it's that good of an idea to switch context that much.
I wonder an average viewer of my stream how much focus that they have on what is happening here and how often they will open the stream and close. I imagine for some of you it's like have background stuff and then switching problems is a very bad idea.
Because I recall the next problem also is 500. No 600. I don't like it as a problem that I would think about in the background. So, no, let's stick to B. Um, I noticed that today when doing SIMC CP, I couldn't do the second problem, but when I went back to it at the end, I could do it. Here you go. Yeah, it of course happens. No, the pro the CP problems are often some kind of puzzles and you need to come up with an idea. Sometimes it doesn't just happen because you spend enough time. It happens because you're lucky. your brain well it got into that particular idea and approaching it freshly approaching it again might help with that let's try how do I solve this other than separately sorting those with weight one and those with weight two also if I sort well then I would sort together and do some kind of two pointers
or do I need to analyze what is convex here? I didn't I I'm not that stuck yet. Didn't spend that much time here. Well, if weight one has values, let's say three, five, six, six, 10, 7, sorry, 11. And then weight two, it has values. Maybe I should sort this decreasingly. But uh the weight equal to two has different values like this. 21 I don't know 11 9 on purpose I'm using uh I'm using odd values here to avoid ties because I will mostly compare the value of what is value divided by the weight and if there are ties it's harder to think about it usually so to come up with a solution I assume that there are no ties the values are distinct the the fact that here those two values are the same actually doesn't matter too much. If this was three and this was six, then this would matter because they have the same efficiency of using your weight. We weight two value six is equally good as weight one value three.
So I prefer to keep it separate. Okay. Uh so generally you will prefer this unless the total weight is odd. If the weight is let's say that then you can afford one of those for sure take 11 forget about it. Now weight is,024 this is eaten and you can take some number of those pairs and some pairs from here. When you take a pair you will first eat this thing as a 16. Then you will take this thing as a something and then this pair as a free. Then you have all of this available to you and you sort all of this 25 21 16 11 and 11 uh 9 9 five and three.
Those are values you can obtain by getting new and new pairs. And just in this order you apply prefix sums to know the total value you can collect depending on your weight depending on the W allowed. Okay, but instead of doing DP actually let's not do those prefix minima. I'm going to modify it and just say that the values now are 25 21 16 11 and so on. This is those are values that you can take by or obtain by getting new pairs getting new stuff with weight two. Also the answer for sure is equal to 11. This is that single value and we took that because of the parity of W.
And then we move on to weight equal to four. This is weight equal to two. Right? So then we say weight equal to four has some values. Now if the remaining value of uppercase w the weight is uh is odd then I for sure take one of those otherwise I group those into pairs. I sort them together with those decreasingly and I move on to the next bit in W. That seems correct. Okay, then this is what I will code and then I would say that this is significantly more difficult than the previous problem. In the previous problem, it was obvious how to start and it was obvious that you will eventually get a work working solution. Here it's not.
What do we read? is upper case. What do we have? X and Y. X is the weight. Y is the um is the other thing the value. This is up to 60. I will say values of this way to push back value for every level from 0 to 60. or to 59 I will save the values from the input. Eventually I need to sort them and now for every bit I will look at the current bit inside of uppercase W. I'll also have some answer to which I keep adding always the values that I had before. I need to pair up. Let's call those old sort decreasingly.
Oh, and the biggest one you need to take. So if W mod 2 is equal one, then answer plus equal out of zero. Unless it's empty. Unless it is empty, the first element. So it doesn't hurt to eat this guy. Uh anyway we will divide then this by two because we will look at the next bit. Now we need to update by collecting those into pairs and then those well without pairs
push back out of I plus of I + one and for that to work I will append a single zero. Okay. So that's possibly the last element now sees the next one which is a zero. Okay. We have this also tmp obtains everything from values of this weight. Now sort we sort here and maybe that's it. There is high chance that I should do something extra but maybe we don't need to vector. Let's use long.
That's perfect. Not perfect at all. What if I modify W to be a one? Then immediately something will happen. But still we have a zero. We have here four items. Wait. This one. So this guy should be available. Why is he not values of zero push back this big value the three I think we need to first do this. No
Maybe yes. Uh do this old equals temp. Oh, a moment ago I didn't even have that assignment. That's bad. Okay. 70 something 70 something indeed. Then let's submit. I will now summarize the solution if I get accepted.
So at the end we didn't really have any DP here. Interesting. An upsac problem without DP. Half of the tests accepted. Okay. solution summary for that I want to draw maybe I do maybe not let's say that my explanation will be mainly an example because still I think that explains it quite a Imagine that I want to pack the total weight of three and I have some items with weight equal to one and some items with equal to two. Uh among those sorted decreasingly we have a 17 we have 15 uh 10 8 3 2 1 and among weight too also I have some stuff maybe I have a 24 and the others will not matter now if there is weight three uh maybe I will take something of weight two but anyway at least one item of weight one I can afford easily. It doesn't hurt me. So I take it. This 17 I take for sure and I don't care about those values even if this was infinity.
Still taking that would leave me one unit of space in my backpack or napse. So this I take and answer becomes 17. Generally the W value is odd. So it allows me to take one item of weight one. Then I forget about this item. Uh from now on what will remain is basically this. Uh and for that I can take either an item of weight two or two items of weight one. What's optimal first take in terms of combining two items of weight one? Well, I can take 15 + 10. So I have an opportunity to take 25. If I take it then I also have opportunity to take 16. If I take it then five if I take it. Well I can take this element and then one unit of space will be wasted. Still I have dust. And now this becomes available for me each of weight two.
Those are also of weight two. So I can take it together and sort decreasingly 25 24 23 16 10 5 1 one one. This this is sequence of new stuff of weight two. Some of this originally was weight two. Some of this is combined pair of two items of weight one. Now if uh if this instead of three was it was something else. Let's say this was 17. In order to make my code easy, what I'm doing now is I'm saying okay, I took one unit of space already. I took that uh element for free, the 17. So from now on, W is let's say 16. And now to continue doing the same thing, I'm pretending that those are items of weight one and this uppercase W is an eight.
And I will continue the process. The eight next items originally four but now I pretend it's two they had some values possible and I combine that depending on the parity of W possibly I take the first item eventually the uppercase W will become a one after dividing by two a few times and then I just take the first item which possibly by now means what is the best possible eight values that I can take in total the values with that sum up to It's something like this. That was binary napsack task. I don't know why they don't show it in green here. Also, there is a tool right for atodor checklist.
What's the website when you can input somebody's username and it will tell you it will tell it will show you the table with problems solved. Stop stuck. I think I meant something else. I I can What's the guy's name? Canoru
anybody remembers? No. Sidecode.com can can cool with that He thank you chat in particular. Thank you Nasan. Okay, that's exactly what I wanted. Oh, this is so sad. Well I solved some ABCs. Let's see it for atcoder grand contest. Well, I I solved quite a few problems around at color grand contest 25 40. Actually, I solved everything here because this is my round at K Grand Contest 47. So, I could just submit my codes. I once had a goal of solving everything. Now, if somebody paid me a lot of money, I would do it. But otherwise, it's so much work, especially if you want to understand your solutions.
Uh, so I think I'm not doing at grand contest, but what about regular contests? I guess this will take some time to load because I'm doing the 200 one. Yeah. So, this what should my goal be? Your sound is so low. Well, the simplest thing I can do is just increase the gain in OBS. Done. Now it's up a little bit because on my mic this is this is maximized. I mean, also in OBS, the microphone is maximized, but I can add a special filter. I could also talk like this, but I don't think that's very convenient.
What should my goal be? Also, do I prefer ad cutter or code forces for those streams? Oh, in particular, how many people participate in that coders nowadays? Standings, but I'm not sure what I should compare it to. The regular contest is like division one, right? I see here how many people with positive score. Well, there are 60 pages of what? 20 people. with submissions. So, 1,000 people got scores and another few hundred attempted. What about code versus numbers? I want Do we have division one rounds anymore? We do, unless it was unrated or something like that.
It's downvoted, but I think it's not. So, is it fair to say that here 2,00 people participated with a positive score? No, less than 1,000. Okay. And what about nationalities? See, an average person is around here in the leaderboard. We have a lot of people from Japan and they will generally I don't think they will often watch my stream also. What time is it in Japan? 11 p.m. and there is Vietnam. I think there are people from Vietnam who watch me in particular. I'm guessing by the second name that Nathan is from Vietnam.
Uh so it it seems in terms of people who participate in contests doing code forces will be better for my streams than doing ad coder which does not mean that I should not do at colors at all just maybe from time to time any thoughts about it anybody? Akash says, "What about going backwards from highest bit greedily pinging the highest value based on power of two?" Well, you don't know if maybe using smaller powers of two will give you a bigger sum of values. What if you're seeing something with weight, 124 and value 77, but later later you will see that with weight 128 there are val there there is stuff with value 40 a lot of them. And actually you can combine eight of them to create this right. So what does it mean that going from big values of big weights we would greedily do something?
You can remember that you have that opportunity but then also you have those opportunities and you can combine them into eight or into four and so on. This seems more complicated but still possible. When solving this problem, I also thought about this trick. When you have knapsack, a knapsack with repetitions. For example, some there is item with this weight this value and it appears some number of times. It has some number of copies. Let's say I don't know five. There is a trick that if you have multiple copies of the same object, then you can take two of them and say that it's a combined new object. So weight equals 100, value= 34, copies equals one. And you took two of those to combine into that guy. You can take another two and combine into this. And actually, you should stop here. The logic is as long as you have at least three copies of something, combine two of them into the bigger value.
So it's like if you have coins, if you have coins of $5, $5 or not, whatever, $5, you can as well instead have coins of $5 and $10 and you will be able to make the same items out of it. You can pay five, 10 or $15. Same logic here. Same logic here. But if you had five and $5, you cannot say that you just have $10 because well actually you can also pay a single five. So in short uh I'm just saying that at the back of my head I kept in mind similarity to uh of what I'm doing to this trick of napsack with repetitions.
Okay. Uh let's continue. But from now on, if I after a few minutes I'm not liking a problem, I will skip. For the easiest problems, I assume that it will not take me that much time anyway. So, doesn't hurt to do it. But now, it is possible that I will spend an hour to actually solve a problem.
Okay, we have string with A's and B's. uh we have set of those strings and it's a good set if every AB string of length of infinite length has some element of X as a prefix. So you you want to saturate the prefixes. For example, if you have strings ab a a and b, they will make up all possible prefixes and you can have more. If you also have this uh then this is still good thing or if if you make try out of it. If you make try out of this, well, there is some property like you have some nodes that are terminal nodes and they cover all possible paths down.
You're given distinct AB strings for each K. Find the number of subsets that are good sets. Okay, it it's almost for sure a 3D DP problem where you need to think about this as a tree and do a bottom up 3dp. Maybe not almost for sure, but this is my first idea. It's how we should think about it. In particular, either we use A and then everything starting from A is covered or you need to cover A and A and you read from their DP. I think that's fine. Okay. And for every K find the number of good sets that seems tricky because this would be an extra dimension that will make the whole thing quadratic.
Oh wait, I misunderstood. I thought that we need to count subsets of every size, but actually we need to count subsets of every prefix of the input. So it's more like if you know the answer for the for this, then you now add one more string and you need to know the new answer. So you need to insert this as well. Then I would say that it's still 3dp where what this means is that we update some path from the root to this guy. actually from that guy up memorized one or bottom up for beginners. I in if you are doing competitive programming, you want to do iterative DP uh for multiple reasons. I have a video for that. Even if you're doing interviews and you only care about solving easy and medium DP problems and you don't have infinite amount of time to practice, then go for recursion and memorization.
But if you have enough time to practice, you want to go for the iterative. So for beginners, if you just have very little time to practice and you want to be good in one week, I think use the recursive one with memorization. Okay. Uh so here's the plan and for this I want to do it wrong.
Now generally you don't want to build trees dynamically if you don't need to. What uh they are saying basically that when there is new string in the input we need to use it and then print a new answer. Instead, I want to read first all the trees in order to make the try out of it. The the full tree I want to build first because it's easier to make it as a static tree. This for example would mean let's say there is a a b and so on. This is called try. If you don't know what this is then you will not understand the solution to this problem sadly.
and so on. So first I build the full thing. Then I activate strings one by one. For example, there might be new string AB in the input. I mean new I go through the input again. I see the AB. I see the path made out of this in particular. This is its terminal note. The the last character here and I want to update its DP. Now what is the DP? Uh well do can I have repetitions? No distinct number of subsets DP of any note is what? If note is terminal then what I can have is this node and everything below. The number of ways to achieve that is to add power the number of things below plus there is also number of things on the left child times number of things on the right child and else if the note is not terminal then I just have this okay so DP of node is always DP of left times DP of right number of ways to make your left child good and right child good so it would cover everything out there
plus uh it's to add power below but only if note is terminal. So if this note is the end of one of the strings then you can take this guy and then below you do anything you want which means that I also need below which is another DP like sub tree resize. This is sub tree size of this guy or number of terminal nodes below. So I also need to update that and always dp of the root will be the answer. Seems good.
Uh what was the previous task again? Binary then I think if you have the knowledge then this task the prefix covering is easier. You need the knowledge of tries but coming up with a solution here is in my opinion trivial. a an experienced competitor will not miss it will not miss such a solution. It's uh straightforward in terms of you immediately go into that idea though you need to have the knowledge of that try stuff. No test cases, right?
There is so there is input and always when I read S, I want to make it into or wait, do I need to actually I think I can do it as I go because in try it's extremely easy to it's extremely easy to add new notes to add new string. Yep. I don't see a reason why I would do it offline. So no, I just say repeat n times or even while n minus minus. So just repeat. Well, why do I want to do it? Let's leave n as it is. Repeat n times. And here we read the string. Well, n is unfortunate because I can later mistaken it with the num the length of the string. Maybe let's call it uh count or something like that.
uppercase n what denotes number of strings but doesn't denote length of a single one let's say ns just to make sure that no this is length of a string even more count strings Linux I use Linux yubuntu Now I start in the in the root for every character in S it's either A or B I don't know type if C is equal B it's is it upper upper case yes this is B then this will be Otherwise it will be a zero. This is type of the come on type of the child and I will now go into I don't know child of note of this type unless it doesn't exist. So if doesn't exist then it becomes like next++ no connection.
Internet is fine. I got a warning that the stream is dying. Is it fine? I think it's fine. I'm using rest stream to stream to both YouTube and Twitch. Okay, seems fine. So just in particular, I couldn't see the chat on my second monitor. It's fine now. But was it not fine even for a few seconds? Was there any lag, any freeze
total length is this? So this is the try thing you have notes and let's remember the path in particular it includes the root I guess. Okay now I need to go it go through it backwards and update this stuff. So reverse Can I do this or does it not compile? Notice existing variable. No. Let's then I'm not sure how bad of a coding style this is, but it's like I'm pretending that this is a function. It will be its own internal scope. I make a note here but then here it's a separate thing. Okay, going backwards I need to do the DP thing. DP of note is equal DP of uh one child in particular this might be zero and if it's zero then this should be treated as a zero.
I think it will help me if the root is actually one not zero. Zero will be something where DP value is always zero. I think that will be better. There is model right. It's been it has been working well for me. No disruptions. Uh where okay thank you. What is this
as for you need you don't need to start from scratch and the advice for you will be I guess the same as for everybody solve problems try different difficulties you will see what is proper for you and just go from there topics to learn to attempt division two problems you need to know how to code then you and attempt division two problems hard problems in lead code. I think my median thinking time for elite code heart problem is less than one minute. uh because many of those are just standard don't know about the average
if this is terminal note also here we need to say is terminal of terminal means that it's at the end of some string terminal of note also if this is the root then next is true for now I'm not using modulo I will add it in a moment uh below should mean what is number of things below I think it's easier to compute number of things including this guy so we'll no um yes minus one because you're terminal here we want to say below of node++ this is sub resize including yourself maybe let's just then call it sub resize
And also sub tree size of this node is the sum of two children. Let's make variables for the children. plus. Okay. And always what we want to do is print DP of one, right? The root. Okay. Terminal. What else? DP. DP is something I want to maintain
a lot of zeros. That's not good. Should I never make mark something as terminal? What about this? Can you tell me what is DP of zero, DP of one, DP of two, DP of three? Is everything zero always? No, it's not. Which which makes sense? So when I go to A, immediately its DP value is one. This guys also is a one. And then we should have this do we have children computed correctly? What is child of the root of zero and what is child of the root of one? So left and right children two and three. That's correct. and learn DP values are non zero. What is DP of node? It's number of ways to choose the terminal nodes. So the strings in this sub tree so that it everything would be covered.
For example, if inside of some sub tree we have this note here and in particular this is one of the terminal nodes. So it's end of some string and also this guy this one or maybe this one this one this one. What options do you have? You can choose this one and this one and then everything is covered. But also instead of this guy you can choose this, this and that. And then also everything is covered. What does it mean? Everything is covered. If you go from the root to anything here, you will go through one of the chosen nodes.
So what is the number of ways to choose some of the nodes, some of the terminal nodes so that there wouldn't be any gap. You couldn't go from the root to somewhere infinitely below without going for one of the chosen guys. Are Oh, thank you, Xenox. Yes, you're right. This should be one. What I should have done after my change is this. I should have went with this route than this route. It's always better not to require a comment. And then what you want here is DP of root. Mhm. Now I guess that we want model operations
including the power of two. Two of Z is one. I here computed an array with powers of two. Alternative would be logarithmic methods to uh to compute that I mean to avoid premp computation. Okay, problem solved. Now I will take a guess by error not a human. I will take a guess that if we look at the standings then this problem for the top participants this problem maybe was easier meaning they spent less time than the previous one. Wrong answer. I wonder if it will be for just few tests. Oh, it's good that I'm using my power of two uh two of this.
Okay. Uh yeah, yeah, this is also wrong. I didn't even after doing this fix, applying this, I thought it's such a trivial fix that I don't need to run again locally. Turns out that this way I don't even check if I computed the array correctly. So here goes like what? Third attempt. Fourth. Should I try add cutter contests? Yes, I think so. I don't think it's good to focus on any one platform as platforms have their own taste or flavor of problems and you don't want to only be good at this type in particular for beginners. I think that adoder beginner contests are actually strictly better than code forces contests.
Okay, problem solved. So now uh let's take a look at the standings. And my guess is for the top people, they didn't really spend more time on C than on B. This person solved in order it seems. And we see 20 minutes and then six. uh this person oh started from F but still this is 5 minutes and this a lot of minutes okay so my theory doesn't work 16 and seven theory works uh the order is all over the place but let's say it's similar unless they tried A first then B would be faster okay here C took more time C took more no after that 14 minutes five B was faster Faster. It was faster. Okay. My theory is not correct.
Also, here do we see the difficulty? Not yet. I think this circle represents the difficulty. But the problems from this round have not loaded yet for the difficulty. It's not computed. Okay. So, let's continue.
Can you explain the transitions again? Uh, assuming that you understand the try thing, then here we go. Not this. What was that? I forgot the shortcut. Ctrl D. No. Okay. Ctrl LD. I I will actually talk about it more generally. Let's say it's a general tree. If you have a tree and you want to achieve something like this, count the number of ways to choose some nodes so that um every path let's say from root to a leaf goes through at least one chosen note. This is not exactly the statement from today from this at color problem but it's very similar. So let's say similar actually we deal with binary tree actually only there are some terminal nodes that we can choose and it's not just to a leaf but also to nodes that do not exist still it's similar enough then how do we solve this? Well, if you decide to choose the root, then the condition is already satisfied. Every path from root to a leaf goes through at
least one chosen note. So what is the number of ways to choose nodes among the remaining ones? It's just two at power the num number of those nodes. Two at power size. It's two at power sub tree of the root minus one because this one is already chosen. Like here it would be 1 2 3 4 5 6 7 8 9 10. two power 10 plus there it's also possible that we do not go with the root so the root is now not chosen then I need to choose something here choose something here choose something here so that each of those sub trees would be covered if this is child A this is child B and this is child C then DP of A tells me how many ways there are to choose some nodes in this sub tree so that the condition would be satisfied that every path from the root to something here is covered by at least one chosen.
So DP of A tells me that times DP of B tells me the number of ways to choose that inside of the second and DP of C inside of the third sub tree and that's it. This is the formula. uh in my code I always had this and this I added to the answer only if I could choose the root because actually the statement basically provided uh the nodes that we can actually choose. So this I would apply only if the root is something that is allowed to be chosen. Also this was not exactly sub precise. It was number of nodes below that we can choose.
Why isn't dp of a called a of dp? Uh dp of a. Well I I would guess that it's because we read stuff from left to right. So this is easy. friends on. I I guess I understand why you're asking that, but I'm not going to spend more time thinking about it. Okay. Uh that was prefix covering much mod minimize. And now I need to keep in mind that I am allowed to skip problems if they are not cool. Is it worth grinding code forces? Uh, I mean, before the AI, why would you grind code forces? I would argue that if it's only for the rating, then it doesn't matter.
Then then always the answer was you shouldn't do it. No, you you're I think most people at least should practice algorithms to be good at algorithms, not to have a certificate of of on code forces. I'm good at algorithms. In particular, if you want a job, you will go through algorithmic problems that you need to be able to solve. The code forces rating will not help you with that. your skills will given two sequences A and B and an integer M uh elements of A can be rearranged find the minimum possible value of that.
So we want to avoid big value of this. Always when they say find minimum value of maximum, I rearrange the order of words a little bit in my head. So we want to avoid big value of this. In particular, we can binary search the answer. So the question is uh after binary searching some value k we permute elements so that a plus b of i module m was smaller than k for every i. That's that's the statement. Hi cool dude. This is what we need to solve. And I'm not saying that binary search will be needed. Maybe it's some kind of sort and two pointers kind of thing.
We'll see. Too many platforms for programming. Please suggest some atcoder.jp. JP. If I came up with this problem by the way as a problem outer I wouldn't be sure that if uh if it appeared before it seems standard. I don't see a solution but I'm just saying feel standard. Uh yes I do use Genie. I keep using Genie because it's very convenient. I have two buttons to compile F9 F8 which do it with different flags and so far I didn't see a software I can where I can achieve that so easily. to compile with debug mode and without it.
That being said, genie is not good for big projects. Not good at all. Yeah, it's minimal. I agree. Okay. Uh let's say I miss 10 because or maybe 100. It's easy to think about round values like this. And now if AI, if values A and values B. If values A include let's say A 10, then in B you want something that is not 80 something. This would be very bad because 10 + 85 model m is uh very close to 100. Instead you want something else maybe 40. If you have here some values let's go with m equals 10. If you have here some values 1 2 3 4 5 6 7 8 9 10 for now.
Let's see. Then it seems reasonable to match it backwards like this. So those will sum up to six at most. And here match this with a zero. This with a nine or less eight seven. This guarantees that every sum two values it doesn't exceed six. So maybe after sorting a what will happen with B is that we reverse some prefix and reverse the remaining thing.
So that this would be below M and this would overflow M. I'm not 100% sure that just this style is optimal. Thanks for solving that detox and removing save question. Oh, I still didn't take timestamps to post about it on code forces, but yeah, you're welcome. I still think that my explanation was so much better than the code forces editorial. Well, if we look at a z in b, we can find the biggest value that added to a of zero does not over does not exceed k or maybe smaller than k. We can then keep doing it and eventually we will fail. Eventually we cannot find something like this.
Then I'm guessing that from now on we should find something that overflows M. But can we do it in this order? I have no idea. So my current idea for every AI using binary search or something like that set lower bound find largest value in B such that A of I plus B of J smaller than K. If it exists then use it. Put it here. If doesn't exist then what you do instead is find largest value in B such that A of I plus B of J is smaller than K plus M hoping that it overflows and the value modulo is smaller than K. Now I hope that doing this either in this order or maybe backwards is enough.
Uh maybe also we should prioritize this first. I don't know. But I think that coding this is simple enough that I should try it. If this was an ICPC contest where you have three people but only one computer, I would now think more about it. I don't want to waste computer time. But in an individual competition, you have a lot of computer time. And I really think that solving this or implementing it is simple. Do we have test cases? Yes, we do.
I wonder how much time it will take. Can I do it in five minutes? Let's say so overflows. No. already half a minute passed. I'm not done reading the input A read B sort let's say both no sort A I think B we want to have in a multis set so that we could use lower bound now do binary search
uh keep values smaller equal k. Let's say in the end we will print the result of binary search and we'll see if we succeed here. Now create a multi- set out of B for every element in A. What you do is try to find something such that X + Y doesn't exceed K. So Y doesn't exceed K minus X s lower bound. No upper bound K minus X and now you do minus minus. If this is not begin then this is something that is smaller equal and now erase it. Else you didn't manage to find it. So now you do the same thing. Copy paste usually means that I could use a function.
Well, uh mod plus that and here else this is a fail break. No fail by default is false. If fail then you couldn't achieve this thing. So we couldn't keep it below that. So low is k + one as this. Mhm. And additionally you should here check that indeed x plus this mod is smaller equal k. else fail. Okay. Uh well, took 3 minutes and a half. Uh so I think we're good. So given such time to code, it's not a stupid sorry, it's not a stupid strategy to implement. And here we go. First sample test failed. So I'm not optimal here. That's sad.
We have the m= 6 and the values are digits of pi 1 34 versus 012 mod is six. So for this if we try try to keep it below let's say three then one will be matched with two this will be matched with zero and here we fail. No let's also try reversing a maybe it will help. So now sort decreasingly just why not try maybe it will work. Uh, well, it doesn't work for the last test
and I know I've read the two comments by Rohit and I wonder if he generally asks a question of how to improve or he is just trying to insult me. The first, let me make a screenshot of the comments. So if you just read the second comment of who is he a grandmaster, I by the way first read how is he a grandmaster like commenting on how stupid my code is or something. But from this I'm guessing you're asking how to become a grandmaster.
Uh well if it's who am I then well you can check my profiles online. Uh coding like a muscle memory. Do you have idea full algorithm type while you think or you think and type? There is some thinking while I code. Implementing doesn't take that much effort. Let's compare it to speaking. Okay, saying things out loud. So for me, coding, if it's not extremely complicated, is similar enough to speaking. And while you speak, you can think about what you're speaking. It helps a little bit to think in advance. Maybe sometimes you need to stop for a moment and think about what are optimal next few sentences.
But it's not that coding itself is will occupy 100% of my brain. Does that make sense? Do I not like these questions? I rates, if you're asking about that grandmaster thing, I just didn't understand it. It's not that I don't like it. I type what I think, not what I want. Actually, well, then the question is, are you making typos or not? Okay, one more thing that I can try. This seems stupid is to first do the model thing. Uh well also let's analyze this. Oops. Also it took me now eight minutes in total. Well we we did some speaking with the chat. So let's say five minutes I spent possibly wasted.
Uh if I go decreasingly like this then four cannot be matched with anything to keep below that. So you try to keep bit below 10. So hence four matches with two then this remains. You have three and one. Three will match with zero. One will match with one. But is there a reason for this to be optimal? Also new idea is we can maybe turn a research on the length of the prefix that we reverse.
Oh, sorry I didn't see your previous comment. I only saw the one about not liking. Do you mind if I ask if you can recommend a resource to learn Java Go languages? Uh I mean you as well you can type a comment as can you recommend a resource on that. Uh so and my answer is I don't know resources for that. So by the way the meaning of this question doesn't change if you just do this right. Can you recommend uh actually even for C++ which I know I don't have resources to recommend because I learned C++ and Pascal from some Polish websites a long time ago. Those websites don't even exist nowadays.
Oh, I don't even know where I learned Python. I maybe I Python Python I learned through the years just knowing few extra comments every here and then well I know Java but how did I learn also it was googling stuff when necessary. Um okay well I'm tempted to now code this turnary research thing but maybe it's better idea to think okay let's visualize the problem there is the sequence A sorted increasingly there is a sequence B sorted increasingly everything from A It can be matched to some prefix of B and then it will be small enough. And it can be matched with some suffix.
My dog is making noises. Not really suffix. Some kind of range here so that it overflows the modulo. Remember the condition is that we want a of i so a of i plus b of j mod to be smaller equal k that's the condition then for given i and for fixed model and fixed k uh I think this is how it looks like what we can match i with
I wonder if maybe we should for first few elements we should just try to combine it. Oh wait I I think I see a possible issue. If number if the first element I combined with something here the second element I combined with something here as well but let's say the third element is so big that it doesn't work with those guys then instead those two the we I should have matched them here and it would be better because from now on apparently I want to overflow everything and it will be easier for me if it will be easier for me with big values, not with small values. Oh, but there is still that condition. So, I'm not sure if bigger or smaller value is better.
No. After. So is it true that those guys should be merged like that or is it possible that instead of something here I want a smaller value also is it true that I will merge things like this maybe it's not true
let's say that this is not optimal small for some reason. So let's say that some connection is too small. If it's too small, then this one should be combined with something bigger. But it will leave something from here to be combined with something smaller. So it's even worse. And I guess similar logic will be the other way around.
So, can I possibly match those with something bigger? How does it help? It helps because maybe maybe even this is too much. Maybe it exceeds K mod. Let's think about uh actual values. 10 uh this is I don't know seven. If this is a nine and this is eight nine as well then maybe you don't want to combine it like that because 9 + 9 18 modulo 10 is eight and that's too much. Instead, you would prefer this guy to be combined here. But in my example, nine then combined with something here. Well, unless it's a zero. Zero. No. No. It cannot be combined with nine.
Can we discuss and recommend possible solutions? No. When I think about a solution, I want I don't want any spoilers unless I ask for them explicitly. Able to solve lead code, easy, medium, but cannot do hard. There is no you can grab mediums sort by difficulty or the percentage of salt or something like that and try to solve the hardest mediums or the easiest hearts because the cut off between medium and heart is arbitrary and it's not really that all the mediums are easier than all the hearts. Please come live every day.
If I was paid for it, I could do it maybe not full-time because the I would need to have stronger voice. But I will come live every day. I will do streams every day. If it gave me money, if I do it for free, it will be not that frequent.
I I see a lot of possibilities of what we can do. What about this? I maybe turnary search was too big of a word. Maybe we need to search for how long prefix there is such that I can match things like this and they will not exceed K without applying model. That's very simple binary search also leading to log square total because I already binary searched K those maybe we can turnary search the this length and actually think about the answer. So we want longest prefix here and then we hope that this is good one when we let's say for this suffix longer suffix means smallest smaller sums in particular the sum can drop below m those are longer suffix if have longer this values will be paired with stuff more to the left.
Shorter suffix means bigger sums and stuff can grow above n plus k. For this part there is some range of range of available prefixes. Well, I can here search for it will be more complicated or maybe more than one binary search. But I can check first binary search how long the suffix needs to be at least so that the sums would be small enough and then also binary search how long it can be at most so that the sums would be well opposite of what I just said. So I'm thinking now about three separate binary searches.
Binary search longest prefix such that a of i plus b of j smaller equal k. binary search longest suffix such that uh longest what is wrong with me taking everything the sums will be very small so I want them to be at least mod and binary shortest suffix such that I plus b of j what is wrong about taking just very short suffix the sum will be huge I want this to not exceed mod plus Okay. And now this is range of available suffixes. I want to check if it's compatible with this. Well, range of available prefixes. I want to check if they have an intersection.
I'm sure that one of those binary searches can be avoided, right? because you're later checking if let's say this range intersects with say this range after you find this is easier to handle the more to the left you are. So what we can do is just find this and check if it satisfies everything. I don't need to check separately for this because it's not needed and this just check if this is valid. What is that? That this longest suffix. So I think we only need to do this binary search. You find the longest suffix such that this is true. It will find me position saying now this suffix needs to be combined like this. This the remaining prefix also combined combine it internally and just easily check if it satisfies all the properties the prefix and suffix. It will automatically check for those conditions. So I think this is what we do.
Can we sub to the channel? I don't think so. When I researched that few years ago, I didn't want to be a Twitch partner. So you wouldn't be so you're not able to subscribe. Uh in particular because of the ads. I would be forced to have ads on the Twitch stream. And it seems terrible during an educational stream to for you to be disturbed by a few minutes or even one minute of ad. That seems very bad. If I can click it from time to time, it's also an annoyance for me. And it's it's hard for me to imagine a scenario where I cover stuff that is not easy. So it it's actually hard condeming stuff where people pay me enough in like subscriptions or stuff like that uh for public streams where it's worth it compared to a job more than two sections.
uh you well it's guaranteed or you can make it happen by applying modulo ai and bi are up to m so the sum of two values does not exceed 2 m so either it's in range from zero to k or just above that only single time you will overflow m okay let's do this which is I'm I'm copying Also this I will copy a wrong CPP the binary search was fine. Uh, do I need to sort? Well, I sort both
here. No. Binary search. So it's internal second binary search. Also it's possible that this suffix is empty. I will binary search the first element of that suffix. Saf low is zero. Saf high is n. So now from here to the end uh we reverse and the remaining prefix we reverse. Here
I combine a of i uh let's say check of a of i plus b of this a of i with b of n - one - i kind of stuff right this is distance from the beginning so this distance I want from the end uh oak is true check function apply the model oh and he want if sumo mod is greater than Okay, then fail is false. Okay. No, I don't want to do such full check because that's not monotonic. What I wanted to do is just find this. So I'm not doing that. I'm only doing this and I'm just checking if this is true. So if a of i plus this is smaller than mod that's bad doesn't overflow is false and optional break if this is okay then this suffix is good and I want to find the longest so try suffixes more to the left else shorter suffix
Okay, I think this binary search is done. And now what I have is I found the best available suffix and I shouldn't have erased that code. But now I want to verify for this suffix. Let me control Z few times. Copy this. Paste it here. Sure. Let's go with fail. By default, fail is false. And here fail is true. Here I verify for this particular suffix. Uh the suffix being saf possibly n itself. Does it work now? It works now, which does not mean much. Do you do any job? Uh, not a full-time engineer job. Freelancing and mainly teaching algorithms, preparing people for Olympiads, for interviews.
accept. Well, then here from the be very beginning I should have thought more about it and I think the visualization helps because without this slide it would be very hard for me to solve the problem. This analysis with a drawing was helpful in particular. For a moment I thought that we need three binary searches. But if you visualize with ranges what they actually represent that you will know like if again what they meant is I was going to binary search the end of some range starting at zero. I wanted to binary search this. Then I wanted to binary search the beginning of some other range the end of this other range. And I wanted to check if this if those two ranges that we see have an intersection.
If they have an intersection though, this is in particular a point of intersection. It doesn't matter where this ends. It doesn't matter if this white range looks like this or maybe like that. Does it does not change the fact of a boolean value of do they have a common point or not. And that common point what it represented is what is the possible cutff between reversed prefix and reversed suffix. So to simplify the code we only binary search this point without knowing this without knowing this only binary search that once we have it there is a trivial of check if this is indeed a good point that satisfies all the conditions.
It's in some way checking if we are inside this range and if we are on the left from this range. Uh but it's an easy linear check. Uh other than that I will not summarize the solution because it would take a lot of time. Uh well that that was I'm not happy about my speed in this problem. It seems that I could have solved that in 10 minutes and it took me well half an hour. Oh, the stream is already 2 hours 15 minutes.
I want to solve more problems, but I think I have other things to do. Sadly, my aim is generally that the division two streams will be 90 minutes and division one streams like today where I actually hard whether when I actually think need to think about problems is two hours. This is enough for me for today. Uh yes, Solaris prefix is up to K and suffix is supposed to be from M to M plus K. But I only binary search how long this suffix can be so that it would be greater or equal m. And then I separately easily check if it indeed happens to be smaller than n plus k. If not, it means that in my first binary search, the one for k. I need to go to k that is easier to achieve.
I wonder if there is something nice in the editorial. Yeah, they are describing single logarithm. Can we also can we turn a research that's cut off? We can do something with two pointers technique. Sure.
I'm not I cannot in one minute understand how to achieve logarithm this way. Seems still similar to what I'm doing. Uh how are we sure doing this is the optimal way to match them? For just like two minutes I analyzed what happens otherwise. It was that analysis where I thought can it possibly help that those two will be matched with stuff here and then somebody here wants to be with smaller. So I did some analysis there and it was enough for me to convince myself that that I think those guys as well can be matched here instead of with something more to the right. No, I agree this is not trivial and it's part of a guess guessing game in solving problems if you want to do it fast that you don't need to understand everything 100%.
Also in uh during streams I can tell you that I guess a little bit more because I'm also occupied with handling the stream. So speaking with the chat sometimes checking if the stream is alive and I need to talk I need to talk out loud. So while during the contest I have a little bit of more brain power to actually think about a problem solution and then I will more often really analyze something and convince myself before coding. Used to watch a few years back now I'm already in the university. Nice. Okay. Uh, thank you everybody for watching. Uh, today we solved ABCD from the regular contest 2001.
I think it would be nice to do everything, but I don't have time now. Maybe next time I will start from this task. Not sure. Oh, division one, two, three. If this is harder version of the first task then I'm guessing it will be out of case work and so if so it's ugly this one maybe bounding okay I I want to read the geometry problem bounding boxes can still be geometric end points find the sum of areas it's okay it's not geometry but it's summation and I also like those kind of problems.
areas of bounding books. Oh, I cannot solve it in one minute. Okay, I need to go. Thank you everybody again for watching. I want to solve this problem eventually. So I think in the next ad coder stream I will solve this. Not sure if it will be from uh something that I start with because it's not trivial but I want to solve it. Okay. Have a good day everybody or a night. See you around tomorrow. Yes I think so. Let's say C.
Questions about this episode
What is discussed in "ARC 201 A-D | algorithms problem-solving"?
In order: 0:00 Codeforces; 15:00 AtCoder, C++; 45:00 AtCoder; 1:30:00 AtCoder; 2:00:00 Olympiads.
What is mentioned in this Errichto Hard Algorithms episode?
4 people, works and ideas are mentioned, including AtCoder, Codeforces, C++, Olympiads. Each one on this page links to its own page with every episode that mentions it.
How long is "ARC 201 A-D | algorithms problem-solving"?
The episode runs 2 h 20 min; the transcript is about 13,224 words in 125 timestamped sections.
More from Errichto Hard Algorithms
About this transcript: the episode's spoken words as captioned on YouTube, split into timestamped sections. Reclip.Me locates every person, work and idea in the text, keeps the time it is first named, and quotes the words around it verbatim. Last updated January 24, 2026.