CF EDU 179 (Div. 2) A-E | algorithms problem-solving

What is discussed, and when

1. 0:00 – 15:00: II camp, Donut Master, DP classes, Red Outs
2. 15:00 – 30:00: Fibonacci cubes, CodeChef
3. 1:00:00 – 1:15:00: II camp
4. 1:15:00 – 1:30:00: Donut Master
5. 2:15:00 – 2:16:09: DP classes, II camp

Notable quotes from "CF EDU 179 (Div. 2) A-E | algorithms problem-solving"

• Let's make sure that this time my microphone doesn't suddenly drop with in voice. Yeah, it seems good. Hi, Donut Master. I see you are the first here. can I start by…

  about Donut Master · at 5:04

• Solve let's say I don't know in math maybe those five problems but don't expect what I did for intro problems where I could actually solve 12 in hours with explanation top…

  about top coder · at 9:59

• What was special about the 10,00 round? I'm tempted to do this unless somebody convinces me otherwise. So most likely we will do ado 179 and couple of updates before we start.…

  about II camp · at 11:31

• Will we also do topic wise problems too in the future like problems on segment three? Yes, I will on weekends. On the weekdays, I'm going to just solve recent problems…

  about Fibonacci cubes · at 19:16

• Do I participate in code Jeff? No. Do they still have high quality division one rounds? Well, I don't even participate in code forces really. And I would obviously prioritize…

  about CodeChef · at 27:04

Who and what is mentioned in this episode?

People

• Donut Master — Person · 2 mentions · first at 5:13

Companies & orgs

• Codeforces — Company · 4 mentions
• top coder — Company · 1 mention · first at 10:13
• Red Outs — Company · 1 mention · first at 10:39
  Mhm. Okay. so today, let's choose the contest for today. I'm tempted to do this one because it was by Red Outs, which there is some correlation of the quality. So let's see.
• CodeChef — Company · 1 mention · first at 27:19

Products & tech

• OBS — Product · 2 mentions

Concepts & topics

• II camp — Concept · 4 mentions · first at 11:53
• DP classes — Concept · 2 mentions · first at 12:15
  I camp starts tomorrow. This today is basically your last chance to register. You will find it on code forces. if you're participant of IYI or some other regional international…
• Fibonacci cubes — Concept · 2 mentions · first at 19:29
• CSS — Concept · 1 mention
• ICPC — Concept · 1 mention

Full transcript with timestamps

5:01 Sounds test. Let's make sure that this time my microphone doesn't suddenly drop with in voice. Yeah, it seems good. Hi, Donut Master. I see you are the first here. Uh can I start by complaining about the software again? So recently I complained a lot about the microphone settings this time. So today I connected my TV to the computer. I need to do something and then later the I the displaying to TV was turned off. I started OBS to start streaming and OBS couldn't capture my main monitor. It kept switching to my side monitor and it already happened once. I remember like a couple of months ago and it seems that when the TV is connected via HDMI then I cannot in OBS choose the everything else other than one let's say main or side monitor connected via display port. So if I use HDMI cable for anything then only one of many display ports entries works. Uh stupid software.

6:31 Okay. Uh I hope that the sound is fine. Uh okay. Okay, so we're live Twitch, YouTube, Code Forces. We have a choice between few contests. Was this one downvoted because one heart problem turned out to be uh existing and that they needed to drop division one? Do I remember correctly? We have a choice between doing division two or maybe division three. though I feel like first division three problems are usually like not very beneficial even for the stream right so maybe it's better to do division two generally or division three and really rush through the first problem uh okay so we have this h what should I do what this one. If it's by red outers, then maybe it's generally good.

7:46 Is in division two hard? Division two is easier than division one. 1033. Possibly the setters were cheaters and maybe you shared beforehand. Okay. Oh yeah, I I remember that something about the Telegram group, but also a tester could leak it, right? If the problems leak before the contest, then it doesn't mean necessarily that it's the outerss. Could be the testers. Yeah, Java programmers will struggle in code forces. I'm not going to do CS CES problems every day. My plan is that for weekend streams I will try to make them more well generally better everyday streams just some more random stuff maybe CSS problems as well but it's more like it will be here solving a couple of problems here solving a couple of problems in particular it's not really viable to do what I did with introductory problems with all the categories why is my internet so

9:11 H maybe maybe just the website uh issue. Let me log in. So previous to streams I did introductory problems in two streams but you cannot do something similar for other topics because they are harder and more time consuming right so maybe I will do geometry those remaining problems in two streams or so uh but normally you will need many many uh streams or maybe sliding window it might be easy not Uh so I think I can do CSCS problems but it will be maybe one stream is enough to solve let's say I don't know in math maybe those five problems but don't expect what I did for intro problems where I could actually solve 12 in hours with explanation top coder doesn't exist anymore So, uh, code versus versus at coder for practice. Mix them.

10:29 Mhm. Okay. Uh, so today, let's choose the contest for today. I'm tempted to do this one because it was by Red Outs, which there is some correlation of the quality. So let's see. I already solved this just fine. Maybe. Oh, but then only those two is what we can solve. This one might be too hard. So maybe not. Educational round 179. What about this one? Uh is the nothing down voted plus 150 plus something. Should we do this? Thousand division 2. Was thousand division 2 special or it was a normal round? What was special about the 10,00 round? I'm tempted to do this unless somebody convinces me otherwise. So most likely we will do ado 179 and couple of updates before we start. Yes, the II camp starts tomorrow. 179 is good. Great. Then uh I camp starts tomorrow. This today is basically your last chance to register. You will find it on code forces. Uh if you're participant of IYI or some other regional international olympiat,

12:15 you can join and it's free. Uh the DP uh uh the DP classes there is still registration uh going on again on code forces you will find it. Basically when I say that you will find it most likely you want to just go through my blogs so that you there you will find it and I'm thinking about this issue that during the first few minutes of the stream people are showing up so maybe I should always for the first 10 to 15 minutes just talk with the chat so always this will be our Q&A Okay. Yeah. And it's what is happening right now. But more well like with a timer imagine that let's say yeah just just for a moment here there is timer.

13:22 So I think starting maybe from the next stream there will be time somewhere and I will make the chat bigger because it will mainly be about talking with the chat. So half the screen will be the timer me and the chat. We'll for like 10 minutes usually just talk without starting problem solving and then we will start the stream. I think that's the plan.

14:00 No ICPC participants not allowed for the II camp. II camp is for high schoolers and below. Oh yeah, the timer that was too big. I will not cover half of the camera with the timer. I think we can start. So it will be educational round 179. Uh I pasted the link to the full contest. We start with energy crystals. So this there are three crystals numbered one two three. Uh the energy level of I crystal is AI. Initially all discharged energy zero. They need to be charged to exactly X in one a. So there are three values starting at zero. Each of them needs to become X in one action. You can increase the energy level of any crystal by any positive amount. However, they are synchronized and there is some condition needed for each pair of crystals. It must hold this one is at least half of the other. It reminds me a little bit about conditions in monopoly. In monopoly when you need to build houses or hotels also it needs to be in some

15:21 way balanced. So I think I would maybe make this statement about monopoly. What is the min number factions required to charge all the crystals. Okay. So we start from 0000. Let's say I want to reach target is 10. then I cannot immediately jump to 10. AI is greater equal than half. So I cannot do this immediately because then zero is not greater or equal half of that. I need to start from this then another zero changing to one. Now this zero needs to increase to at most what? Uh three right because half of three is one. So this is okay.

16:15 Yeah. Then the one still will limit us. So it's 33 free. Then uh this will change into seven 33 and so on. Okay. Uh so there are two operations changing from 0 to one. Then two operation operations changing into three, two operations changing into seven and so on. Uh always I can say that I change the smallest number and do I want to do it automatically? I think I wonder if we should simulate this at all, but I think that's easiest. I I'm going to just simulate it. alternative would be to compute something like the logarithm of this because it's clear that if you want to get all sevens or lower then you need this one more operation here and one more operation. So 1 2 3 4 5 6 7 with seven operations you can get all sevens. Uh then with two more operations you can get all 15s. Okay, that sounds better. So three operations to get one one then I think that many. So five operations to get 333 seven operations to get 777 and so on.

17:53 Let us read x. Now I need to find such a power of two. Uh can be is equal to one operations equals three. So this is what I can get in three operations. While what I can get is smaller than the target. I multiply by two and add one and operations increases by two.

18:30 Okay. So I don't actually simulate this one by one though I could we could just implement the logic of always find the smallest element. Uh 379 23 31. Yeah it's I think that this sample test is weak on purpose. All the outputs are odd. Oh no, sorry. I'm stupid. Uh I'm stupid because the answer starts as three and we always increase by two. So obviously it needs to be odd. Apparently never the answer is even. Will we also do topic wise problems uh too in the future like problems on segment three? Yes, I will on weekends. On the weekdays, I'm going to just solve recent problems uh Fibonacci cubes. Also on weekdays, maybe sometimes I will grab a couple of consecutive problems from SCSS, but it will not be just a full section like I did recently for intro problems.

19:49 There are Fibonacci cubes. There is visualization where the site of I cube is f of i. So fibonacci number we define like this 1 2 3 5 8 and so on. Also m empty boxes uh each with some width, length and height. For each box you need to determine whether all the cubes can fit inside the box. So boxes are like queries. Sides of cubes are parallel to sides of the box. So you cannot rotate. Otherwise it would be crazy hard geometry problem in 3D. Every cube must be placed either on the bottom of the box or on top of other cubes. Uh okay. And they need to be sorted. But I can place two cubes next to each other. Yeah. Yeah. Okay. It must be important that those are Fibonacci numbers.

20:59 So it seems that if the biggest uh if the biggest can fit and the next smaller can fit on the top of it, I'm guessing that everything else can fit as well. It's It might be hard to represent in 3D, but I think we can draw that in 2D. So, my guess is that we will only always care about two biggest boxes. Should a complete beginner do this stuff start at division two? I'm guessing that if you're a complete beginner then division two problems will be too hard for you but you will realize that right if you try something and it seems too difficult you cannot do it then you can drop down to like division three try other problems you said to mix at coder and code forces can you give example I mean solve some problems from one and some from the other uh let's Think about it in two dimensions for a moment. So it will be like view from the side. If you have 13 by3 box or square on the top of it you have 8

22:17 by 8. 8 by 8 then the next which is 5x5 will fit here automatically. It cannot not fit. Then the 3x3 can fit here. Not a square but still you get the point. 3x3 then 2x two will fit here and one by one automatically fits here. So into the the if you're given such a container where you want to place the stuff that the biggest box and the second biggest box fit then automatically everything else will fit because it will fit in that remaining part just next to the second biggest box. So the conditions are that that the biggest box need to fit in terms of width and the other dimension the depth and then for height the sum of two biggest needs to be okay that's the condition I actually like this problem among the division 2B problems I think this one is quite nice because there is some analysis that seems simple well you can guess it that's maybe a bad But then there is still some implementation. It's not just few ifs because you need to

23:34 find the fibo values and is small. So no over no overflows possible. I expected that n can be huge and if those values weren't Fibonacci numbers then even for n up to 10 it would be a hard problem because I think it would be some kind of backtracking. I instead of M I prefer to use Q for the queries. Uh for each test case we have this and then there are queries like that. So for every query this is a short way of typing repeat Q times for every query read width length height. First I'm going to find those two biggest boxes.

24:33 N is at least two. So always there are two biggest boxes. I need first 10 Fibonacci values. Fibo of one is one. Fibo of two is two like they defined in the statement. Well, let's go with flexible code. it will go up to n. Fibbo of i is sum of the previous two and then for every query what do we do? Uh we check if two biggest boxes will fit by height. And I want to check that the biggest box fits by width and depth. If so, then output yes. Else output no. At the end of a test case, new line. Oops, that's not correct. Maybe it's because of the rotations. I assume that the we will stack vertically while we can also put the the other box next to it. So I think I want this height to be the biggest of the values. I will put here maximum of this. So maximum will be the height. I think that right because if it's horizontal it will be just next to it.

26:29 I think the logic will still hold. And uh this biggest box it needs to fit in every direction. So or every dimension. So I will just say that it cannot exceed the minimum. The sum of the two fits in maximum in the biggest dimension. And the biggest buck itself fits in the minimum because it needs to fit in every dimension. Okay. Now the sample test works. Do do I participate in code Jeff? No. Do they still have high quality division one rounds? Well, I don't even participate in code forces really. And I would obviously prioritize code forces over codechef because in code forces I know that there are multiple experienced strong people who coordinate this and if there is somebody who is experienced and has nice problems by default they will go to code forces. So on code forces I expect high quality problems. Of course the at coder is even different. Uh so this is by the way two seconds and my runtime is 700 millconds which is quite high for such a task. Usually there is

27:52 bigger uh leeway in easy tasks and I wonder if it's because of the way I print because I output many characters one at a time. So maybe it would be faster to create a string and output once. I just want to see here add a one here add a zero and then output string. That should be a bottleneck. Oh, and I also read maybe maybe reading is the bottleneck. If so, one more thing I will do is type those two magical lines that speed up scen out. It's got faster. What about this? I remember that one of those two lines is unnecessary, but don't remember which one. This is what you need to type if you use scene and see out in C++ and there is big input or big output. Okay, it was about that. Now I wonder if I moved back to printing characters one at a time.

29:12 Now do note that I not I didn't need those optimizations. The code was good enough and you don't get more points for being faster as long as you fit in time limit. The time limit was 2 seconds and my first submission worked. I I'm just experimenting. Why not? Why not using fast IO? Uh because it's unnecessary. See out zero is not useful. But what about syntizer? Okay, so there's no difference once this is uh applied. Then there is here no difference between outputting characters one by one versus collecting a string and outputting all at the same time.

30:08 Uh what's the difference? Uh can we not consider both to be one operation? Oh no, the reading and printing is way slower than normal operations. When you let's say when you type something like this, this is just an operation that CPU needs to perform and also usually it has low constant factor. It's good for memory stuff like that. But when you need to output something, let's say you need to output X, especially if it's a long string or number, but even if it's something small, then this either is displayed to a screen or well usually really it's saved to some kind of buffer and then to a file which are way heavier operations. Uh printing is I think multiple times slower than a standard operation like adding two numbers. So see out it is constant time but it's significantly slower and what is way way slower is actually this I think here because we read a lot of numbers and you can argue that reading number x is of log of x.

31:23 Usually we don't treat it like that but number x is of length logarithm of x right? If number is 10 to 9th power, it has nine digits or 10. Uh so decimal logarithm is the length of a number. So this is closer to time complexity of reading not constant. uh regarding this question, can you give a hint to yesterday's operations problems? uh so for those of you who know that I'm going to uh discuss that problem eventually it's a hard problem. The hint is so don't listen to the next minute if you don't want a hint. The hint is that those are graph related operations. Think in what graph algorithm you're doing such an operation. It's something like uh the value at J you assigned to minimum or maximum of itself comma something else plus some some kind of extra value related to this operation and this is I think I think in what graph algorithms this happens and yeah this is a graph

32:52 Okay. Hint over uh cob def also said your string also allocates on the other solution you did. You know size of string is Q. You could allocate only once. Uh sure but I think outputting push backing to a string wasn't that much of a bottleneck compared to printing at the end anyway. So I I but you're right of course though vector of characters is not as heavy as vector of ints. So I think that adding single character to a string doing that multiple times is not that much different from creating one long string first and then filling. Okay. Equal values. Third problem.

33:56 You're given you're given an array with n numbers in one operation. You can do one of the following actions. I wonder if nowadays if you ask chatgptt generate a new problem for code forces it will most of the time do something with operations. What is time complexity of sin after optimization just okay you should assume that it's constant it's for it's okay to assume that it's constant you will not get time limit existence because of that being said another thing is the optimization is good because it improves the constant factor it becomes the operations become faster a little bit choose a position I and make uh all elements to the left of it equal to ai.

34:54 The cost of such operation is this. So you can change pre you can change prefix into values ai and you pay ai for every element you change. Okay, I will write this down. You can choose prefix of length L and change all elements to AI. Oh, but it's important. Okay. Uh, two elements. Well, maybe let's say this for the cost L * L times this. If five elements you're changing into value 100, you will pay 500. And same you can choose suffix of length L and change all elements to A of N minus L. Yeah. For the cost L * A of this. That's another way to phrase this. The elements affected by an operation may already be equal to that, but still you pay the cost. You're allowed to perform any number of operations. What is the minimum total cost to make all elements of the array equal?

36:14 Will we usually choose the smallest value? When do we not just choose one value and say that I'm modifying this and modifying that? Yeah. is I I need to analyze samples. So you see this is actually a problem where I would uh usually look at the sample test because after reading I'm thinking it should be optimal to just find the minimum and change all the remaining elements to it. Maybe if there is a block of consecutive minima then you don't need to work with all of them. So let's see. So my theory is that here you choose a one and you pay the cost of changing those into one. Here it's a block of ones. Here you choose four and you pay the cost of changing that and changing that. But now this is not divisible by four. So I think what we do instead we we choose this block of fives I'm guessing and we change one element and those six elements. So seven in total. Okay that's good. Now you see you I didn't come up with that but the sample test showed me not necessarily

37:33 the minimum is optimal. Sometimes there is another value that appears a lot of times in a row. Not in a row is useless because if there is five here and then another fives there. I still need to modify those middle elements into five. And when choosing some five and changing this suffix into fives, I pay for changing those fives into fives. So it was useless that those are here. The solution is that for every block of equal elements, we consider changing everything else to this element. Uh the most basic problem by the way that where you can practice this finding blocks is this one. We did it a few days ago in CSS. It's given a string. Find the longest block of equal values. This is the same just with some extra steps.

38:37 Read the input. And then what? Block equals zero. While I + 1 exists and two consecutive elements are equal. I ++ block ++ block initially one. I found some consecutive values that are equal. Now the remaining values I need to change into AI with this cost. Answer should be minimized with u initially answer is infinity and I think we need to use long lungs 305. I very much like the solution here. I'm not a fan of the problem statement, but the niceness of the solution is like for this slot in a contest, it's I think nine out of 10. I very much like this and I would recommend it to everybody to practice using problems like this one where there is some analysis you might have incorrect idea which is great actually. Maybe even this problem for practice would be greater without that sample test because when you practice it's very good to fail because of some wrong solutions. I mean you can get annoyed by that but you train this way.

40:19 So nice problem. I also like the previous problem. So nice uh to the author who created this maybe here. This is 179 Felix Arc. Kudos to him. 1 L* X looks better than long long. I mean, this gets colored so it's easier for me to see. This doesn't get colored so it's harder to see. But whatever. You can type one ll times. It's fine. Creating a schedule, a long statement. Long statement, some big values in the examples. Okay, so far I don't like it. Let's see. Creating a schedule. Was able to solve CD at my first try in this contest. I don't know your level normally but then congrats though often uh doing something at first try is correlated with strength of the samples so maybe it was choice of the problem setter that those who solve a problem solve it first try no I'm not a software engineer new semester that's a hard word semester semester Seaster semester semester it's about to begin and

41:53 it is necessary to create a schedule for the first day n groups and m classrooms uh six classes on the first day and the cave class uh so it's synchronized so it just means that first class it's let's say from 8 to 9:00 a.m. then from 9 to 10:00 a.m. and so on. though the sentence is a little bit confusing. Each class must be held in a classroom that cannot be classes for more than one group in the same classroom. Uh each classroom has an index at least three digits and all digits of this index except for the last two indicate the floor where it's located. For example, this is on fourth floor.

42:35 This is on that floor. Okay, now I understand why the example used so big values. Uh yes, I will sometimes participate in contests and AI will keep getting better at replacing programmers between floors. Wild can move by stairs. Floor 10 to 7th is the top floor. create the schedule to so that students would move as much as possible. Okay. But what is given in the input? Number of groups and classrooms. Indices of available classrooms. This was top floor. Okay. Uh numbers of classrooms per distinct sum of them small number of groups number of classrooms and six classes per day. Okay. I hate the statement and the idea for this problem. Uh too long to maybe hate is a big word. I don't like it.

43:59 Uh, I'm guessing that it will be greedy. When I was saying the sentence, I'm guessing that it will be greedy. My eyes went directly here to the problem tags. Maybe I should I don't know if I want to turn them off for the streams. I normally need them because I often choose problems for students and uh I'm looking at tags. When I see a problem, I want to look at the tags. I'm not sure. Uh but when I started saying that it should be greedy, I didn't see it yet. Okay. So I think that we can take any group and we can just say start from the bottom floor, then move to the top floor, bottom, top, and so on.

44:44 And it seems easiest that there will be another group that will alternate the other way around. Otherwise it would be tricky to make sure everything is correct. But if I another group say top bottom then two group two two groups will just exchange the classrooms. Let's look at an example. If if those classrooms are available then maybe this example is better. Then I see for example 290 I think is the minimum. So I will say that first group will move from 290 to the maximum which is uh 479 then 290 479 290 479 and so on. Second group will move the opposite. This is how easily I can handle uh two groups and two classrooms and I can forget about them. Third and fourth group will get the next two available classrooms. There might be a case that there will be the last group that takes just the middle uh classroom and they do not move at all. But I don't think we can do anything better. Right? I the proof of correctness will be that if you mark floors

46:11 there can be collisions. Multiple classrooms can have the same classroom. What I'm doing is I'm having like those distances that I need to maximize this and then that and so on. And eventually the middle element can be paired up with itself. But I don't think we can do better. If you do things more at random, then still if you look at every space between two consecutive floors, I don't think it can be crossed more times. There is a way to prove it. I will not go into detail. It relates to length of prefix versus length of suffix. And this is also how you can prove uh the correctness of algorithm that chooses median for the meeting point. there is this well-known problem that says um for end points.

47:07 So there are n people I've at position x i choose such meeting point for them that we minimize the total distance traveled the total distance traveled. This is a well-known problem where solution is to choose the median and the proof of correctness for that that median is optimal is also that if we shift it then it worsens and we can analyze maybe it's no it's a different proof but we can analyze for every two consecutive spots how many times it's covered. It's not a good analogy. Anyway, I'm going to go with my greedy solution. Luckily, during a contest, you don't need to fully prove. It's not a math olympiad. What do we output the indices? We don't even need to compute the sum. I think I would prefer to as a problem author, I would prefer to require the sum.

48:28 and groups. M classrooms for every group. I want to take I want to alternate between first and last. I'll use two pointers for that. Let's say so I will output repeat three times. print first and last. Then if i + 1 is still smaller than n, then uh three times we repeat the other way around. Last and first with a new line. Now I see that I should have created a function because now there is four lines of copy pasted code and I += 2 first ++ last minus minus it will be hard to know if it works for the sample test. I mean no no something is very wrong. I need to go A of first, A of last.

50:12 Again, if I created a function, it would be easier to correct. Now, there is something here. Whether it's correct, there is more than one possible output. Uh whether it's correct we will see by submitting. Not good. Maybe I need to look a little bit more. We have this first last first last. Then we swap, but one group can use the same cluster multiple times or not. Yes, it's clear from here. 610.

51:25 Wait, that's I didn't sort. I see. Also, it's uh I think it's it's too much of a hint that in the last test case they are doing my strategy. So, minimum maximum here. As a problem outer, I would change this output. It's too much of a hint if somebody analyzes that. Okay. I missed the sword. Something is wrong. This is not the maximum. Last is m minus one. So many mistakes. When I was typing nm, I considered that maybe I want to change names because usually size of something of the data structure is n not m. Let's see now.

52:42 Still wrong answer. Okay. Why am I outputting fewer lines than they do? Because I'm doing I++ here, even though I'm doing I plus equals to here. Whoa, I don't remember when I did so many bugs in code last time in such an easy problem. Yeah, I ++ in the for loop and I plus equals to here in total that jumped by three. So actually and I should have seen that my output is shorter than their output. I didn't print enough lines. Good thing would be that in a contest accepted grid. In a contest, you're not penalized for wrong answers on one. God forces should have subtasks like iOS per 5 hours. So, uh lot of time to read uh and to consider multiple subtasks.

54:09 And in code forces it's what like six seven problems per two hours three hours. So for every problem you have 15 minutes just reading subtasks and considering them. Uh you would spend half of the contest and for problem outers it's a lot of work. II is Olympia problems are difficult to prepare especially with good subtasks because just using smaller N is usually lazy and it boils down to implemented brute force. How are you so nonchalant? That's a bad thing, right? Am I uh Which field best aligns with CP? Back end. I mean, okay. Low level is also related, but generally back end.

55:13 Okay. Uh changing the string and I think then we'll look at puzzle but not necessarily solve it. We'll see. Quant engineering. Yeah, some kind of HFT. Quant trading. It's related to algorithms. Changing the string. Problem E. I actually don't like string problems. I'm bad at them. But that applies only to hard problems. If the last problem of a contest is about strings, then usually it means I will be worse than others solving it. For something in the middle of a contest, it doesn't matter too much. Even a string s that consists of only three letters of the alphabet ABC.

56:11 Uh I don't like the grammar here. given a string that has something you are given a string given a string is start of a sentence if then they say your task is to do stuff uh I think I'm not native speaker also given our Q operations that need to be performed on the string in each operation two letters XY from the set of ABC are provided and each operation what one of the following actions must be taken change any one occurrence of uh x to y do nothing. So you can change when you have operation xy you can change one x into a y. The goal is to perform all operations in the given order in such a way that the string s becomes lexographically minimal. So we minimize first characters like minimal means that for example uh I don't know zebra is very late in the dictionary because it starts with z. Dog is before that. Cat is before that. Doggo is after dog because it's longer. We sort by first character then by second and so on. If there is a tie then shorter wins.

57:37 So you start with S and you have then Q possibilities. You can change B into A, B into C and so on. But you need to keep in mind that there are operations later on. I feel like maybe we will need to go through the operations backwards or maybe we will need to take care of special we will need to do something special for the first two characters. But backwards is my first feel. uh because it's more important it overrides what happened earlier and depending on that you will do operations here C into A this is always a good thing A into B also it's important that there are three operations it seems that do we all see CA we will do always if you can do C into a then you should always do it. Is that correct?

58:47 Maybe it will hurt. Maybe after that you have a into C and you will be forced to do it because of that instead. No, we are not forced to do it, right? I keep thinking that we need to do it. So it we might be hurt by A at the beginning because if there is operation AC it will force force us to change A into C. But no. So let's see. We have a string and perfectly we want to change its prefix into values A. Then some next few characters into values B. Some right? Why would we change something into B? Because it starts as C. So maybe there was a C here. If before that there is A then it belongs here.

59:56 If before that there is B then we can expand. So this is always C. And then where do we apply the C? Nowhere. there isn't any character that is on the is in the input and we want to make it into C at the end. So this is what we will achieve and this is what we did with characters that were initially like this because if there was a then we leave it there. Here there could be like B C A B C. There is some prefix that we will change into A's. Then some prefix of remaining part that we change into B's and this remaining part we do not change. First question is how long of a prefix we can change into values A.

1:00:58 Oh I see one more thing because of the okay this is not true. It's not that only we are doing those operations. It might happen that we have a lot of operations that change for example C into A or maybe better B into A. Then if in the input you have something like this then you will change those into A's but this will remain unchanged. So this will still be C. So it's not true that I will change some prefix into a can I can I go from left to right and for the first character first decide if it can become a because if it's a from the beginning I do not touch it then can it become a either there needs to be at least one operation that changes its original value into A or I will change it using two operations B into C and then C into A. Either one will work.

1:02:17 Then you're looking at something else and so on. As you keep going, you know how many B's and C's you already changed and you wonder, can I still continue with this prefix of A's? This C will never change because there isn't any operation that changes it. There can be operation C change into B. Uh tricky tricky. Uh please only speak English in the chat. I don't want to have no idea what you're typing without using translator. Um, could observing the thought process of someone really good solving problems have good influence on the person observing? Yeah, sure. Though still solving problems on your own is better practice than watching somebody do it though. Watching somebody do it is easier to do and it has some entertainment value. Not much though. Can't you for every character check what letters they can be? Yeah, but it's not independent.

1:03:42 Want to begin competitive programming? Go to code forces problem set. Sort by difficulty solve from easiest. Yes, looking for patterns is good. I love the H. Not good. I'm registering people for the Huawei II camp. And once again, the link for registration stopped working. I will finish the stream in around half an hour and then fix it. Uh, okay. Again, we go from left to right. Almost always when it's about lexographically minimizing something, you need to prioritize first characters. You look at B and you want to say I want to change it into A. So you have information. There is one change like that that you want to achieve. Then you look into at C and you say that I want to achieve the same A don't touch uh B C and so on. So always what we have is for example twice I want to achieve this and three times I want to achieve this.

1:05:25 You can achieve those with the input operations of changing B into A and C into A. But also you can do it by using the for example B into C operation and then C into A. Okay, what about if I don't go from left to right for the string and instead I go through the operations? If I see if I have this string and I get B into A, then I apply it to this character. It's optimal. If I see though C into A then again leftmost C I can change into A. No hurt in that. What if I see something else like B into C or C into B? That's stupid. That's that's non stupid.

1:06:33 Should I apply this to? So this only makes sense if I want to later change this C into A. So it seems that this you should just remember remember about this possibility if there is C into A later than something C into B you cannot do it greedily. You want to do it only if you will have too many B into A's later or if you will do nothing with this character anymore. Oh, and you don't know which C to change because some prefix of C's you will change into A's. This into A, this into A because this is so much better. Then only the next C you want to change into B.

1:07:32 H. Okay. Uh, Shiam, time out. No need to repeat the question multiple times. Of course, timeout is not a bun. It's just like a pause of a few minutes. It It seems that I should have solved the problem by now.

1:08:36 But this is hard because there are multiple possible approaches and you need need to investigate uh each one. This joint set I don't see how that's useful. This joint set makes sense if you know what operations to do and you need to maintain something fast. Basically, here's the trick. Uh, as we simulate this process one by one, it's not clear how to achieve the solution in any time complexity. Can't you greedily apply operations by the distinction I said earlier? So I usually when solving problems I prefer not to look for hints in the chat. Uh but okay I will read your your suggestion.

1:09:30 CBA and BCA are noticed together. So maybe use case distinction. Good idea indeed. I hope it's a good idea. So those complicated paths BCA versus CBA, you're doing it in so complicated way if there is more or there are just too many of C into A or B into A. This is why you're going around. It doesn't make sense to use this and use this both. If you would use both such triples, then instead you would directly jump from B into A and from C into A. Indeed, we can have two cases, two pieces of code or just some code running twice depending on the case where for example we can say we can do this but we never we will never do this.

1:10:32 What it gives us is that well still we can do C into B but if we can do this we do okay let's say that we can do this uh we can also do B into A directly I think that will lead to a solution though I'm not happy that I didn't come up with this idea myself. Whenever we see B into A in this case, we just use it. Okay. Then then this is the only chain that can stack the only thing that where operations interact with each other. For anything else, their positions do not matter. So we can look at all occurrences of this operations and use them just the left most B changing to A. This we do by iterating once through the operations.

1:11:48 What about C into B? Should you ever do C change into B? Maybe at the end. Brain hurts from being used. No, this problem is not considered easy. I started an easy contest, some old easy contest. I went through a couple of easy problems and now we have a hard problem. Would you like one hint? No, not yet. I think that this still will lead to codes that is slightly over complicated. Uh so up enough not only the number of operations matters the order of them. So there is Q in the input and what is the order of those operations that are allowed matters.

1:13:07 So when I see the next character here, I have some statistics about this like oh actually that was that. So this is what I typed first that maybe if I know that five times I need to change it like that. Seven times I want to change C into A, two times I want to change C into B, stuff like that. If I have this then I wonder if my Q operations allow me to do it. But that I need to fast check it. I need to fast check if something like this is possible.

1:13:54 This this happens directly for both for both of those directly we use as much as possible and then it's about first few occurrences. Okay, I think this this first idea I had will lead to a solution. We're going through the string from left to right. For every character, I wonder there to how small character I can change it. And with that I update just those three counts. This is what I want to achieve. And always I wonder if this is possible just yes or no. Is it possible or not? Now how do I check it? First of all uh in the input uh among the Q operations I keep the count of operations of every type and I directly use those if I have multiple possibilities of when to use I will do it in some order but let's leave that aside for a moment what else can I do I can do if after I do directly those operations I might be left with some more of those required Uh I think so maybe I need two more times. I need this. I can do it by doing B into C

1:15:22 and C into A which increases where operations of this type B into C I can keep sorted of where they when they are. So B into C operations I can have vector of int indices of occurrences and it's like two three 10 and so on indices among the operations then C into a operations I can also have something like that uh where I have where where where those

1:16:08 And I want to pair those up with some suffix here because this will be easiest. So the operations that I do directly that will be taken from prefix. Now we wonder if that many can be matched. If those two can be matched with those I think I can as let's say pre-processing check how long prefix of this can be matched with suffix of that so that always those events would be uh before those this is in pre-processing and then when I have this query about how many operations of every type I want to achieve I will be able in constant time to check if that many from prefix are good against that many of suffix because if you take too many from prefix versus suffix then inequalities will not hold anymore if someone's rating is x what's the best problem rating range x to x plus 500 you should solve problems of such difficulty that sometimes you can solve them and sometimes Not let's say 50%.

1:17:33 Uh okay that's so I think this is correct solution though I don't like how complicated it is and I don't know if there is simpler solution. Okay. So for example, donut master maybe you can tell me is the solution intended solution very different from what I said. So my solution is to collect indices of various operations among the Q operations do some prep-processing with binary search. So n login time complexity or q q to remember for example those versus those how many can interact and then always as I go from left to right through the string I decide the destination what the every character will eventually be and I keep such free counts and I in complicated way in constant time check if that's possible the solution doesn't seem very different Okay.

1:19:01 No, I'm doing code forces problems today. Okay. I think before implementation, I want to take a look at the editorial. I actually use this type of solution. Got time limit exceeded on 26, but afterwards use the same solution. Doesn't seem too different from yours. Okay. I mean 200.

1:19:29 I would be surprised if I got time limit exceeded here cuz I think I have just 200,000 times log. Uh is there a hint? No, there is not. I want to see some prefix of the tutorial. Okay, let's scroll through to see the time complexity. Is there logarithm lower bound isol? Okay, log and the tutorial is long. But if this is the case, then why is it problem E? Shouldn't be later. Uh top people solved it in 10 minutes, but many people struggled more. Okay. So, it's just a hard problem. I think this problem is too hard for its slot. So, then another thing there should be big drop of souls. Oh, still that's a lot. Maybe I should look at uh the during the contest. But I thought that this will be like 5,000 and then 500. Very very big drop.

1:20:40 Okay. Now, another thing is do I want to implement it or do I want to switch contests? I I have some time left to continue the stream. I think I don't want to implement it. The funish part was coming up with a solution. I think that I have a correct solution. But now implementation will not be very nice. So maybe I want to see the editorial in a little bit more detail. Why lower bound? No, it's okay. The solution is not the same. They don't do binary search in advance. As they go, they take earliest of first type and use lower bound to find earliest of the second type that is afterwards.

1:21:54 I think I'm happy just skipping the problem now. I don't like it. Looking at the chat for a moment. Solving along with the stream today, but only managed to submit first problem. You are on P3 by the time I finish P1. Let me I like the question. Let me try to answer that. And I think now we will switch to another contest. Let me think. Okay, here's the thing. I don't think it's a good idea during my stream to try to implement solutions on your own because I see you use the word submit. If you are doing it along the stream, you shouldn't code. uh unless you are very strong if you're let's say not that much weaker than I am in problem solving because by coding at the same time you will do worse understanding the solutions. I assume that majority of people watching the stream are not able to solve problems at the speed I do it. So what you should do is certainly not code it while you listen to.

1:23:25 Instead just focus on trying to understand the solution as much as possible and code if you want after the stream. And what will usually happen is that for some prefix of problems you will be able to keep up. If not, if for some problem you really feel lost, then try to at least focus on some small techniques that I use because sometimes I do talk about like smaller sub problems or stuff like here we can avoid logarithm maybe you don't need to understand the full solution and still you will get something but certainly I it's not a good idea to try to keep up at and implement what if you don't understand the editorial. This one I also want to yeah absolve after the stream. Correct. I also want to answer that uh if someone doesn't understand the editorial mainly there are two explanations. One is that you're trying to solve a problem that is too hard for you. Then the answer is don't do it.

1:24:36 Skip it. Maybe move back to it in few weeks or months. Second possibility is that the editorial is badly written. If so, look at the comments and look at codes also submissions from others and maybe you will be able to understand some gaps in the solution from the uh from the code. Okay, I'm switching the contest. A quick look here also anybody has a way to mark problems as I'm not interested in it anymore because for let's say that puzzles and divisible subarrays were nice problems and I wanted to absolve them afterwards. Is there something I can do to mark this problem so that I wouldn't open it in the future or I wouldn't try to absolve it in the future?

1:25:37 What's the way to do it? Like let's say if I open contest and say that I actually solve a lot of problems which is not the case for me anymore. Let's say that here there is division two uh round and I maybe decided that I'm not interested in this problem anymore which is uh which oh yeah that's the case actually uh it's we talked about the solution and I don't want to solve it what can I do other than maybe taking the intended solution and copy pasting just to mark this problem as solved It's cheating in terms of number of accepted but I want to mark the problem. Snipping tool available on Ubuntu. No, I I don't know how to do it. Uh what you saw me doing is I used snipping tool on Windows because this here is a virtual machine.

1:26:42 Start. You can start it so you can remember it later. like this. Star is for nice problems. Ego, your review, please. Is there a mirror already? I mean, when is the mirror of that? Still not announced. Make a mashup and exclude this problem. Okay, so I can do that. But from the contest and from problem set, what do I see here? I still see this. So I might be tempted to solve this last problem. Snipping tools available on Ubuntu. Ah, I I believe you. I'm just saying that what I used. Oh, and there was a question. Is there snipping tool? So yeah then apparently the answer as knowledge says is yes there are I don't like this star what I can do is also I can submit incorrect solution okay I think I I will leave with the fact that problems like that will remain because I don't want to implement volcanic eruptions. I don't want to implement changing the string either. And as I sometimes say during streams, if you actually are practicing for important contest like IY,

1:28:27 ICPC, stuff like that, you care a lot. You want to be the best, then you shouldn't skip ugly problems. Also, how long is the solution? And when I practiced for ICPC, I also did not skip. Okay, it's reason. Now, let's skip the problem and let's move on. Uh, do I read messages I get from code forces? Yes, but I don't always reply unbalanced binary tree. How to serialize? I think there are many ways, but like if you go down, put negative one. If you go up, put positive one. between puts the value from the note. Okay, what else can we do today? Maybe from this contest. I remember that there was a contest with a single problem remaining. That was an easy problem. I think uh here yeah shrinking array. We can always either do shrinking array which is division to B or we can from here do the first two.

1:29:37 How many times this was submitted? So something easy to finish the stream and then I will talk maybe more about plans for future streams because this stream today might be the last in the next week because of the IO camp. Uh this problem is harder. Maybe we'll do all of them, all three. Well, let's see. during deletions. Also, I welcome any recommendations for how I avoid uh repeated questions of how to reach specialist and how to reach expert and stuff like that. maybe a comment on Twitch exclamation mark expert and all the comments will redirect to the same link of how to practice colon uh add arrangement if the following property holds copy B into C sort in nondereasing order ta sort increasingly A if B is not CI then this okay this definition says if you sort the array every element will be on a new different position then we call B the arrangement it's something that is completely not sorted not the minimum is not on the first slot second minimum is not on the

1:31:20 second slot and so on you're given an array in one operation you can delete an element uh output where it's possible to perform some operations such that remaining elements form an arrangement. You just check if there are two elements that are not sorted. So greater element than smaller. If so, I hate this problem. Uh so they are talking about deleting elements and we want to achieve something that is very much not sorted. Then if there is any unsorted part I can just remove those two elements. So I'm just going to say read everything.

1:32:17 If this element is greater than next then yes. Else no. Yes. No. Oh, we need to output. What do we output? The indices uh elements that remain in the array. Let's see if I get accepted then I will complain. Yeah. Okay. I think this is like the worst possible problem for this slot. Statement is hard to understand. It seems very artificial. a lot of math formulas like think about somebody in middle school let's say high school who is starting with programming and they see this problem they will be so I don't know discouraged from trying and then we talk about uh erasing elements like for me for me as somebody experienced I don't care about solving this in a competition it took me a minute to understand I knew immediately how to solve solve whatever the quality of a problem like division 2 a is about what it is for people who will solve it and for whom it was not trivial and for those people I think it's a very very ugly problem

1:34:04 maybe some people will say that this is a nice beautiful observation that only two elements should remain and stuff like that but for people for whom it's not trivial The statement is crazy hard to understand I think. So as a coordinator I would not accept this problem. Uh problem differs from problem G. Sure. Uh you must output the minimum. You're given an array. Uh here's the problem link. Maybe I should keep a spreadsheet where I give notes to problems and I think how good this problem is for its slot for people for whom this is an a challenging problem. Software engineered engineer but at problem solving really need few minutes to understand that's fine.

1:35:10 Usually statements require several minutes. Unless you already solved 5,000 problems. Uh there are elements from zero to n. You can perform the following operation at most once. Choose to indices and increase first by the second. Then the second set to zero. So the second element you transform somewhere to the left. output the minimum possible value of the sum of prefix minima. You minimize the sum. Doesn't it mean that you need to do something close to the end? Maybe it's just optimal to move the last element to the this.

1:36:04 Preferably you don't want to do this but maybe there is a zero maybe there are multiple zeros my first thought was last element you move to the second last element but I don't think it's correct wait what about this maybe second element you need to move to first if you have 555. You can transform second into first and you have 10 055 and then all the almost all the prefix minima are equal to zero which is very nice. Can I do something better here? Does it work for samples? Well, I not I might not transfer everything like we see here.

1:37:17 Maybe it's true that we only transform between first and second but not always everything. We can transform less. If there is let's say seven free and then stuff then transferring one unit from here to there increases this prefix by one but this prefix decreases by one so it's optimal to send everything. If this is the case though then transferring hurts because right now the prefix minima is free and free. If you transfer, it's four and four. So, it's worse. If you need to transfer here, it would need to be Oh, we transfer everything. I I thought that we can partially transfer. Okay, my bad. Uh, is 10 better? Well, here we have 3 + 3, which is six. Here we have 10 plus 0, which is worse. If we have a lot of big elements later, then this works.

1:38:30 What about this? If there is some element and from that element you want to shift to the left, is it optimal to always shift to your left neighbor? Because from now on this will be zero. So all the uh prefix minima for those guys will include the zero. So that's great. You want in this prefix to shift into such element that it affects the answer as little as possible. When you say easy, what is the rating of the problem you consider easy? Uh chando it's relative. I I don't have particular range. If you're talking about the title of the stream, uh it's not the defined range, but it's division to contests and not the last problems in such contests.

1:39:30 And when the title of the stream says hard or division one, it means that I don't expect beginners to understand anything. Maybe in the future I will be more specific. But for platforms other than code forces you cannot you don't have some objective difficulty. Even in code forces you don't have objective difficulty. Uh it's interesting that I struggle on this problem a lot. I'm sure the solution will be trivial. Okay, what about this? What if for every element I think if I shift into this element from somewhere on the right then from where I should shift? So this element will get some value. Now that's tricky because depending on what element it is, I will get here different amount. So the minimum in the prefix will be affected in a different way.

1:40:38 Let's make sure that it is sometimes optimal not to shift to your left neighbor. I think if this is a zero, this is a no, this is maybe five zero. This is 10. Then why would you shift? How about this? Well, this is an easy problem and I don't see a solution. So, what if I just try that? I will try a solution of Yeah, we always shift by one to the left. Yeah, I don't know. And this is what I would do at this point during a contest. If I for five minutes couldn't solve a problem that should be easy for me, then maybe it's good to take a guess because the solution cannot be too complicated. Shouldn't be for every element.

1:41:50 Let's do it like this. Maybe shift afi + 1 into ai. Okay. Then so far we had some prefix minima. So far uh this is so sum so far and this is prefix minimum by default some kind of infinity. Uh so maybe do this. If that's the case then so from now on prefix minimum or maybe we have the sum so far plus the there will be a i plus a i + 1. This is the new element here at position i. If I take its minimum with prefin then this is the sum up to i. And all the following sums will be zero because there will be zero at position i + one. The answer I can minimize with that then after that prefix minimum minimize with the value ai. Here I don't anymore consider shifting. I say maybe I will shift later. So let's uh keep going. So far plus equal pref uh at the end output the answer. So I did that for all the elements. And finally once more I want to do it for the last element and this is also a possible answer.

1:43:44 I don't know if I implemented it correctly, but let's see what examples tell me. 223. That works. Now, is was the solution correct? Uh, submit. Submit. Yeah, I think it's 50/50. Okay, works. Why is it correct?

1:44:10 write some examples of arrays down. Huh? You remember how I said that maybe we will only touch the first two elements? Maybe that's optimal. So I wrote a solution where we consider for every two neighboring elements we consider the shift something simpler is true and this this is why it's simpler to analyze. Maybe I should have tried harder with those examples to create a counter example because I wrote some stuff down but I think I didn't do much with that. I actually don't know what I did with the examples now because I recorded myself again. If I practiced much and I cared about my performance in contests, I think I would later view the recording and I would try to think critically what did I actually do when writing down examples because in this problem it was good that I wrote down some examples but I didn't do enough with them because I didn't get a simple observation that nothing else is needed only do this thing where you shift between first and second element.

1:45:31 uh if a1 is greater than a2 uh so if there is seven free then this is only better to move into 10 zero yeah that's I agree with and from now on we will have zeros and the proof here is that you cannot achieve better than the sum of them because if you don't touch those or you shift something from the right into here then the sum of 10 you already have then if 37 then it's optimal to shift. Okay, it's not entirely true that we only touch first two elements. We can shift third into second. Then maybe I realized that and from now on I thought that it's not so simple. Yeah, maybe that's what happened. So maybe you shift this, maybe you shift that and from that I think I assume that it will continue.

1:46:23 Hence then the guess that you will shift between neighbors. So you shift this and then but wait what's the answer? The answer is three twice and then do okay. So this way you get the answer of 7 + 3 and here you get the answer of 3 + 3 and it can be proved that nothing better is possible. Okay, the proof is easy. I see how I uh Okay, I will vote great problem because I struggled with it. So, it's a it's a trivial problem where I struggled. So, for me, good problem. What about the range deletions? Oh, I will rate uh bad problem, right? It was the one. Yeah, that bad problem. Great problem.

1:47:19 I will vote on others because I solved them before. Uh multiply I I remember I over complicated uh a little bit but it seemed a fine problem. So good. Make a palindrome. Okay. It was good. Good. Make it zero. Oh, I remember it was crazy easy for me. So, rate the problem. Uh, it was okay. Too easy for the slot for me. Maybe I'm too harsh.

1:48:15 You can use insert button for esoft to remove this. I wonder what AKC wanted to say earlier. If you mean that when I'm doing something like that and I want to replace a single character like this and I I do a five. this is what you were talking about because marking and typing is fine if that's what you were saying uh versus if I hit insert to replace then I need to remember to hit insert back and that's annoying uh okay so two problems solved and there was that other contest where I have one problem remaining shrinking array so let's do it and and wrap this

1:49:12 Oh yeah, then I'm aware of insert. I sometimes do it. For example, when I work with a grid, if I type like this and I want to replace some characters, then I will use insert and do this stuff not to mess up the grid. But for a sequence I usually prefer to mark and replace by using arrows. So this you can do with keyboard easily. Okay, last problem today. It may be last problem this week. Uh let's call an array beautiful if it consists of at least two elements and there is a position where two neighboring elements differ by at most one.

1:49:58 Okay, you're given an array and while it has at least two elements, perform the following operation. Choose two adjacent elements. Choose a value between them. Remove the values AI and AI + one and insert the number X in their place. So for example, if there is 515, you can remove them and just leave eight. You had this, you have that. You can in particular change both into a single five. Minimum number of operations required to make the array beautiful. If there is this sequence, then I can achieve the target in one operation. I change this into an eight.

1:50:56 If the sequence is increasing like so then it will keep being increasing. So I think if the sequence is increasing we output negative one negative one increasing sequence. Yeah I think the answer is just always zero or one. So if increasing then negative one if already there are two neighboring elements that differ by at most one then you don't need any operations and finally uh if it's not increasing then there is at least one situation where it's something small big small let's say or the other way around and then uh so like let's say this is 100 and then one of those values is smaller than the other like 50 versus 20 and then the one that is further away from 100, you collapse those two into 50.

1:51:59 Okay, not an interesting problem. Uh but it's it's fine. We need to check if it's increasing or decreasing. By default, increasing is true. Decreasing is true. If a of is smaller than that than next, then this is not decreasing anymore. If greater than not this anymore. Also if two consecutive values differ by at most one then immediately we print zero. Finally, if increasing or decreasing, then negative -1 else one works for the sample test. Spent eight hours on minimize sum. Took you a couple of minutes, but I was very happy after solving this. ended up using prefix array and array that tracks the minimum number so far. Uh so here's the thing. If you enjoyed the process of solving it and you to it took 8 hours then great great good for you. But keep in mind that this is not uh efficient way of practicing. You shouldn't spend 8 hours on a problem unless it's meant to be very complicated problem with multiple steps.

1:53:54 So for efficiency, you should have given up after 1 hour and look for some hints or just leave the problem for later. But that being said, again, if this is your hobby and you enjoy this, perfectly fine. Um, for example, I actually sometimes like playing video games on too high of a difficulty and I keep losing them. That's fine. I think if I enjoy it. Uh though that actually might be good for improving unless you set the difficulty too high then it's not good anymore. Uh tell us about future streams. Yeah. All in the analysis of the problem. Uh, Chandu, what you're referring to all in the analysis of the problem what I used I used Polish platforms before cut forces I was in school I didn't speak English good or well I still don't uh right let's talk about future streams also how does the problem set look like for me now solved a bunch of easy problems.

1:55:20 One contest without ratings. Okay. Uh so something about let's talk a little bit now. This will be just some random thoughts about future streams. I will tell you a bunch of stuff. I happily accept any feedback both now in the chat and later in comments below. Uh Polish platforms, you know, I practiced on Polish platforms 15 years ago. Those platforms partially don't exist anymore. Certainly, it's not that you should seek them. Okay. Uh so a few things is that I think I'm okay with uh during a stream mostly taking some contest and solving problems from there. Uh though also we need to distinguish between uh weekend and weekday. So Monday to Friday versus weekend.

1:56:31 Weekend will be more educational stream. I can prepare. So I I'm okay spending some time and preparing before the stream. Monday to Friday I will not prepare. So just open OBS and go. this I'm doing this for free and I'm not willing to spend several hours a day preparing for something uh okay so that's uh some difference for Monday I will keep this time I'm happy with the time so this will be uh for me 3 p.m. to at most 5:00 p.m. uh central European time like today. Uh for weekends it can vary time varies and on weekends sometimes I can do topic stream. uh it can be CSCS category a uso guide topic in particular from platinum and advanced I think uh Monday to Friday usually it will be some code forces/adcoder comp contest and uh always before the stream it will be announced that will be easy stream or hard stream like today it was supposed to be easy so I only looked at division two problems And I was going to solve problems that I almost immediately

1:57:58 can solve and I don't struggle too much in a hard stream. I still have some doubts about that. Uh weakened. Yeah, thanks. Wait, what? Uh I didn't misspelled. I thought that I misspelled. Uh wicked, I see. Oh, so you misspelled on purpose in the uh in the chats. Okay. Uh quick look at the chat. Oh, I I see Chandu. Okay, I got it. Hinamu, I don't think it's good strategy to give up on a problem and then end up not practicing for days. I think it's way better to accept the fact that sometimes you can skip a problem and be lazy about it.

1:59:00 Division 2D or in easy stream. I think today I attempted Division 2D. uh the way I'm practicing in the past couple of weeks does not affect my chances of returning to LGM much because I'm solving easy problems. Being legendary grandmaster is about uh solving hard problems too and during streams I'm not doing that. Uh I don't know mid intersection so I will not teach you that. It's one of few topics that I know nothing about. I have no idea what matrid intersection is and I've never used it. There are many topics where I'm bad at like suffix area flows uh some parts of number theory. Still I used them in the past. I know something about them.

1:59:52 I know nothing about mroid intersection. I'm not sure if there is CP topic that I know less about. M okay. Uh I have some thoughts about uh about hard streams is that I'm not sure I like the fact that if I stream on YouTube and Twitch 90% of people who will open the stream will not understand much. So, and in particular, there's also the chat and many people in the chat, they will ask questions where clearly the stream is not for them. So, I I'm not sure what to do about it. So, this is open question. And I have some idea. Let me share it with you. And again, I welcome any feedback. I'm thinking that maybe I want to do something like this. I still want to like Okay, first what my idea is is that this will be closed like something on Discord server but very cheap. So for maybe you know five bucks a month you have access to those streams that I do you know once a week or so something like that where the the only idea of that is that it's not available to everybody out

2:01:24 there. So if a random person opens the Twitch stream and they will start asking questions, I think it's perfectly fine. Though still for me it's it's a little bit of spam and I cannot focus and actually solve hard problems. Also those hard those streams they are extremely boring I'm sure for many people. But I still and I I don't know if this should be about the chat only or maybe only those who are in this discord server they attend the uh stream and later I upload recording and now I'm not talking about you know solving division one ABC I'm talking about I did that in the past where I would open at coder grand contest and I would solve one or two problems for two month for two course I'm just really struggling just practicing me practicing I don't know it's an idea but I'm not doing it efficiently during a stream many viewers will also kind of waste their time or they will not spend time efficiently viewing that and asking questions about

2:02:45 Chandu, one heart problem every end of a stream is a very bad idea because I often want to end the stream because of something and I want to have control on it. Uh, a hard problem can take arbitrary amount of time. So imagine that. So why hard problem bad at the end of stream? Imagine that I want to stream for two hours and then after let's say one hour 20 minutes I go to hard problem. What happens is then I hope that I will solve it in 40 minutes and most of the time either I will solve it way earlier or I will solve it way later because it's very random. No, I don't think that adding a hard problem at the end of a stream is a good idea.

2:03:40 No, I think paying solves the problem. I mean, you should know what you're paying for and I can kick you out. By the way, still I I I will still do paid classes where it's way more expensive. But this is about something where I there is something I don't like about the current format. I I talked about reasons for this. Uh which contest will be solved in Monday to Friday. Maybe that's a good idea. I will add this. I should announce which contest in advance. Yeah, I agree with what CJ said. Could you could we send you some original interview questions? No, I don't have time to review that. Um, starting from next month, I'm going to do uh paid lead code classes where we solve lead code weekly contests for example. And then there in the discord server, you can send me those original problems. Maybe you will from time to time help solve them. though after some time I don't want to help live life

2:05:07 and this for sure I don't want to do this for easy strips uh for collaborative problem solving I sounds good but I think harder to organize let me See most of the people listening to the streams uh to learn listen to your streams to learn. I guess around 70% of people are beginners. Uh, I guess h because you know what I also consider is sometimes really doing a hard problem. Sometimes it's nice and it's beneficial for me for my shape in problem solving to do a problem that will take me hours and then 90% of people will not keep up.

2:06:32 I don't know the matching between Olympiad versus code forces. Sorry. Collaborative problem solving. You can pick one of your viewers and make him her solve the problem live. No, I will not experiment with that. For sure, not a random viewer. If that would be the case, then uh yeah, it's too unpredictable both in terms of content and just how dangerous it is for the stream.

2:07:12 uh glamp. Yeah, sure. Hard problems are great. Uh around a specific topic that too, just not all the time. You can you shouldn't take a topic and keep grinding the topic. Do few problems then switch to something else. Uh, okay. So, what else? What else? Oh, the the weekend those streams will be no chat on the screen and I answer only uh topic related questions. This is something where I want to recommend people that if they miss a uh stream they should watch it and here actually in both for sure at the beginning slash end maybe maybe end Q& A at the beginning especially because then people keep joining and it's bad to join in the middle of solving a Well, I can sometimes do specific stream for people asking questions, but it will not solve the issue of new people asking questions.

2:08:49 What else? What else? Okay. Uh, regarding that, tell me if you see any difference between those two possibilities. Let's say that for first possibility there is private stream uh in discord server server later uploaded to YouTube as a recording. That's possibility number one. Possibility number two, there is public stream with chat turned off. Only special people can use the chat. Only some people can use the chat. Maybe the chat will be only on Discord. On Twitch, I don't really want to turn on subscriptions because there are some disadvantages to that like ads. Uh okay. In both cases there is some small group that where I know that they want to practice hard topics. And now the question is is is one version here better than the other.

2:10:04 Will you try hosting a mini contest and then start the stream editorial afterwards? That's uh time consuming. No, no, no. I I'm not going to create contests from scratch for paid users. No, that's too much work. Choosing old problems. Sure. Why is second option better if you cannot ask questions? Also, some people might get confused on Twitch. Can you even turn off the chat?

2:10:52 No, put chat in emote only mode. Is there something like that? Emote only mode. Yeah, I I will try to p announce problems in advance. I'm not looking now to new ways to do entertainment kind of streams. I want to maximize the educational aspect, not entertainment. if I have time and will to do it. The next thing that I will do regarding that more of showmanship will be getting back to the lockout contests. I like those. I will host host a lockout competition. I will invite four or eight people and I will commentate on the matches in I see in Twitch there is followers only mode that will not help sub only mode. I don't want to turn on subscriptions unless I need to.

2:12:30 Okay, I think I want to finish the stream now. I didn't like reserve that much time today. Option one is better. But why? Most people said option two. I didn't see many arguments for option one. Somebody already said that in Discord server people are more dedicated or something like that. Explain people's doubts while solving. Solve problems in stream and focus more on solving and explaining less doubts in the chat. Uh explain people's doubts makes sense if I know the level of the people. So historically what I find most efficient Oh okay. What is best is on-site teaching in terms of answering questions and stuff like that. When I have let's say group of students that are preparing for an Olympiad and I know their level. It can be during a camp or some regular classes in Warso like in some high school in Warso. I did free classes every week a few years ago. If I know those people, I know their level, I see their faces when I explain stuff, this is the best. This

2:13:47 is the best teaching. I perfectly know if something is too difficult for them or not. The next level is online teaching with cameras on when I see faces of people. Next is, let's say, Discord server where I know them, but they only can type with text. And then you know Twitch and YouTube open streams is the very worst in terms of me knowing how much I should explain. Can people speak here if it's a very small group? Yes. But also people wouldn't like it. I think people prefer to use text if they're uh if it's all being recorded or streamed at the same time. So let's say in this case it would be text. Okay. Uh I will finish now. Please if you have f uh further thoughts uh put them in the comments on YouTube. I will read that. And I spent time thinking about how to improve stuff. I I want to keep streaming in the coming months and I just want to improve it. Uh, make it minimal fee and private. I mean, I would prefer to keep it public, at least the recordings.

2:15:16 Oh, well, we'll see. Okay. Uh, thank you everybody for watching and I'm reading thanks in the chat. So, you're welcome to uh have a good day and see you maybe this Sunday, but also maybe just next weekend or something like that on code forces. Uh, check out Oh, I see that Jonathan is solving uh egoy problems. I need to check out what that is right now because I considered also using that for the II camp. Okay, here are my blogs. Uh so if you're II participant then join this camp for free. Consider the DP classes and there is my schedule of streams. Nothing will happen for the next few days because of the IIO icon.

Questions about this episode

What is discussed in "CF EDU 179 (Div. 2) A-E | algorithms problem-solving"?

In order: 0:00 II camp, Donut Master, DP classes, Red Outs; 15:00 Fibonacci cubes, CodeChef; 1:00:00 II camp; 1:15:00 Donut Master; 2:15:00 DP classes, II camp.

What is mentioned in this Errichto Hard Algorithms episode?

11 people, works and ideas are mentioned, including II camp, Codeforces, Donut Master, DP classes, Fibonacci cubes, OBS. Each one on this page links to its own page with every episode that mentions it.

How long is "CF EDU 179 (Div. 2) A-E | algorithms problem-solving"?

The episode runs 2 h 16 min; the transcript is about 14,715 words in 108 timestamped sections.

More from Errichto Hard Algorithms

• All analyzed episodes
• People mentioned on Errichto Hard Algorithms
• Topics mentioned on Errichto Hard Algorithms