Codeforces algorithms problem-solving

What is discussed, and when

1. 0:00 – 10:00: Discord, Lead Code
2. 10:00 – 20:00: Lead Code
3. 20:00 – 30:00: Lead Code
4. 30:00 – 40:00: Lead Code
5. 1:40:00 – 1:44:10: Discord

Notable quotes from "Codeforces algorithms problem-solving"

• Think before that it's a good idea to choose the problems a day before so maybe today in the evening on discord we will choose I will ask you to suggest me some good problems…

  about Discord · at 1:54

• Lead code problems. Not today. My plan for lead code is to do some weekend classes starting from maybe half of July. we'll see. And maybe some streams from.

  about Lead Code · at 2:39

Who and what is mentioned in this episode?

Companies & orgs

• Lead Code — Company · 4 mentions · first at 2:39
• Discord — Company · 3 mentions · first at 1:59
• Codeforces — Company · 3 mentions

Full transcript with timestamps

0:16 Okay, Twitch works. Okay. Vibe half arpit occas hi hi for a moment I can put a chat here then later when I'm solving problems I will move it on the top of the camera because just yesterday it was an issue that sometimes I would cover something meaningful. So I think while talking with chat this will be best position for the chat and then while solving problems it will be like that. We'll see how it goes. Like this seems very chaotic. Uh so for a moment here

1:42 uh today division two problems tomorrow similar time actually I I will put it on code first as well. uh tomorrow we will solve harder problems division one and I think before that it's a good idea to choose the problems a day before so maybe today in the evening on discord we will choose uh I will ask you to suggest me some good problems to solve for tomorrow code forces add code or whatever just something hard and uh tomorrow there will be maybe a stream of two hours a little bit more than that where I solve let's say the target is two problems per stream today. Just a bunch of easy problems.

2:28 So, what is the most recent thing? Educational around 180. I don't see why won't we just read them in order. Lead code problems. Not today. My plan for lead code is to do some weekend classes uh starting from maybe half of July. Uh we'll see. And maybe some streams from time to time like once every two weeks. No lead code today.

3:05 Should it be thousand? Maybe this is better. Okay, let's read the first task. Uh, and if if it's ugly, I will just skip also. This is the link. One more thing I will try to remember in the future in the title for people who are joining later. Oh, I'm not logged in here. In the title, I'm going to put always a link command because you can use it if you join during the stream. All good. Polish Olympia problems seem to be a lot more challenging. I mean more challenging than division 2 code forces problems but not more challenging than other olympiots. Japanese Olympia is harder.

4:16 Okay. Uh when game starts the price is dropped to certain point. Whoever gets to it first will get it. Alice will start running at A. Bob not has not yet chosen the starting position. Uh, the price could drop either at point X or Y and we want it to be closer than that. Check if Bob can choose an integer point that is guaranteed to get to the price faster regardless of whether it appears at X or Y. I don't like it. Where is my drawing tablet? Here

5:13 it is. Oh, and the sound today should be much better. I modified some settings in particular. It should always be loud enough. I think yesterday it was way worse. uh on Tw okay the question to Twitch chat do you agree that right now the chat that you see on the right hand side is too chaotic with all those copied messages so I think it's enough if you see it on the screen right I think this this what you're seeing now on the left hand side like it's too much uh too much copy pasted thing right I think what I I can do is I can hide this copied stuff.

6:00 Sound seems fine. Yeah, great. Uh so before I code the solution, I want to reinstall Windows. Do I get the same license? I have no idea. A chat where is chat restream sound is good. Great. I've solved C. Well congrats

7:03 Okay, now it should not now it should not be copied. So, let's see. Test one Twitch and on YouTube. Okay, now it on YouTube test to YouTube. So, you should see those both messages on the screen maybe with some lag. Uh, but there will not be copy pasted. Yeah, I think that works. So, you will see messages on the screen, but they will not be copied between the platforms. I think that's less spam. Uh, yep, good to see you too, Beckers. Uh, okay. Uh, let's sol let's start problem solving. So the task is Alice is somewhere here. There are two points. Let's say X and Y.

8:13 There's X point here, Y point here. And we want to be closer to them. Well, in such a case where we want to start is here just after Alice and then I'm closer to X, closer to Y. On the other hand, if the y position is here, then we cannot win. Also, we cannot win if either x or y is at position of a. So, my logic will be if x and y are on the same side from a and they are not at a then I can win and I will be here also this can be on the left side and that's it. This is what we need to implement. Uh do we need to just print yes no? Yes.

8:55 So we don't need to find the position just test cases and read axy. If both x and y are to the right of a then this is good or both are to the left of a. I'm using min and max to simplify the code a little bit. I could also type x greater than a and y greater than a. If so, then print yes. Else print no. By the way, you can for sure shorten this code. For example, you can do this into turnary operation. Something like print if this then yes, else no. And you don't want to do it. I understand that this is shorter and this is one line instead of few. But you want to have readable code because if you make a mistake, you want to minimize your time of debugging. Uh I have not read the variables.

10:11 Okay. Uh let's run a on input in uh yes. Yes. Now submit. If the problem was harder and it would take me more time to code, I would just skip it. Maybe I will internally move some windows around. Put this thing here. Chat maybe here to the right. I mean, I would skip it during the stream. I not during the contest of course not. Will you solve Olympic code anymore? I don't know what is Olympic code. Have I tried Vim before? Only when I was forced to do it. So in my ICPC team uh like my my teammate used Vim and when I needed just for a few seconds to modify something there I needed to use Vim for a few seconds and it was hard but at least back then I could exit from Vim. That's something I don't remember how to do it anymore.

11:30 Something with colon Q I don't remember. Okay, let's see next problem. Maybe for those division two streams like the one we have today, I should in advance decides that we are doing for example this contest. I don't know WQ exclamation mark or something maybe. Let's call ar beautiful if there are two elements and there exists a position where the two next consecutive elements differ by at most one. Uh, choose to adjacent position. Choose something. Okay. Ugly problem. I'm skipping. I generally I understand that in competitive programming we care about the quality of a solution mostly, but for easy problems, I really hate when it's ugly artificial statement.

12:28 uh when I work with students or just to recommend a problem to somebody. I would never recommend something like that because if you're at a level where this is a challenging problem then the statement will be I don't know disgusting. It will not make you want to solve it. This statement seems nicer. Alice and Bob are playing a game using an integer array of size n. Initially all elements don't have a color. Alice chooses three elements and colors them red. Then Bob chooses any element that colors it blue. If it was red, recolor. Alice wins if the sum of red elements is strictly greater than the value of the blue element.

13:09 Calculate number of ways. Okay, this is fine. So this is a link and how do I change it for the comment here? Okay, link comment will work. I I see vibe that you used segmentry for that. Uh generally I don't want spoilers. I mean after I'm done explaining my solution. So maybe I'm coding but I already explained what I will do. Then you can say how you did it and how you did it differently. Will I'll be doing lead code streams as well. Uh maybe just from time to time. Not as often as code forces once. No problem. vibe.

13:54 Uh, I stopped wearing specs at the beginning of COVID 4 years ago. I got a lasic surgery. Okay, I wanted to read the input. No, I want to solve the problem first. We choose three elements, color them red. Then Bob chooses any element, colors blue. We want the sum of red to be greater than the value of blue. elements are positive. So I think what will happen is we choose three elements elements A of I A of J A of K. And now I'm solving pro problem. So let me put this here. Let me know later if this is annoying for some reason.

14:43 And then Bob I think will choose max among them. So our score let's say say that AI is max then Bob will choose the maximum of them. So AI so we want a of j plus a of k minus a of i to be positive or instead we can say this we're looking for triples of elements such that the maximum is smaller than the sum of the other two. I can also write it down. Count triples such that max is smaller than sum of other two. Uh where I have been all these days living my life. Please do this more often. I will try to stream more during this summer.

15:44 I was lucky at this point. I've done a 90% similar problem. Then you were lucky. Sure. But you know, solving a lot of problems increases your chance of being lucky. Hi Ritik. Uh, how do we do this? Uh, and it's up to 5,000. So, we cannot afford to try all triples. If we do all triples, it's n cubic and 5,000 cubic is too much. Instead we want to aim at n squ and and I use the polish word and usually such problems can be sped up with two pointers or maybe here it will be three pointers. Uh so we want to sort the sequence almost for sure because that's how similar count pairs count triples problem problems are solved. So for sure I sort it and then think about this sequence when you have two elements let's say that those are the two smaller elements you want the maximum to be smaller than the sum of them. So if I'm looking at here value five here value eight then I want to count how many elements there

16:51 are to the right candidates for the maximum AI such that it's smaller than 13 the sum of the other two. I can for example here use binary search if that because the sequence is sorted. I could use also two pointers to speed this up. But if we have this I think it will be fast enough. 5,000 squared is like 20 million uh times logger 200 million operations should work fast enough like 400 million. I think it will be fine. uh though if time limit was let's say 1 second I would be worried about it uh so let's solve it like this in n^² log n^² * log of n uh we read sort and then ah For every pair of elements, I'm going to binary search on the remaining suffix for the maximum that works. Uh, count k on the right such that a of k is smaller than a of i plus a of j.

18:21 And Actually for a moment let's just check if I understand the statement correctly. In half a minute I can make a sanity check that it works for samples. So let's spend half a minute on that. Let's have a brute force. If a of k is smaller than a of i plus a of j then answer plus+ uh and print the answer and answer can be long long I think. So now I really spent half a minute and I will get feedback of is the brute force correct 10 to 164. No it's not correct. So I messed up something here and that's good because if I decided to go immediately for the more complicated solution I would struggle more debugging it. So let's see uh why do I say four?

19:21 Well because if I choose such three elements Bob will choose one. Bob can choose also something else. Here we go. That's an issue that wasn't a correct understanding. So uh okay but so you see this is where I saved possibly several minutes by spending half a minute and finishing the brute force because in this case the brute force was just few lines of code and imagine what it would what uh time it would be in a hard problem if I spent half an hour coding something and it would then turn out that I misunderstood the statement partially or I came up with a wrong idea.

20:03 So Alice chooses three elements and then Bob chooses max of them or max in the sequence one of those two. So let's still say that so we choose some elements and we want the following to be true. We want a of j plus a of k to be greater than a of i. Also additionally a of j plus a of k plus a of i should be smaller than global max. Now if in my sequence one of those three elements will be the global max will choose it. So this case needs to be covered and this is harder to satisfy because Bob will steal the maximum from us. So we don't need to worry I think specifically about the case where global maximum is one of those three values. I mean just we need to focus on that. So I want to here say uh this and additionally a of i plus a of j plus a of k is greater than global max which is a bug because the sequence is sorted. Now let's see if this works on the sample test. Uh I think it works. Yes, it does.

21:23 Uh so let me maybe simplify this because we want to get rid of this and we want to replace this with a two pointers or binary search. So now I and J are decided and I'm interested in what K needs to satisfy. And here we have one inequality for K. The other inequality for K. Let me transform this one to simplify it. I will move this to right hand right hand side. And now I have that a of k needs to be greater than this and smaller than that. Let's simplify this even more. Low is a back minus a i minus this. High is a i plus a of j. Those were the two values. And now ak needs to be smaller than high and greater than low.

22:14 I write I like writing inequalities in this order from left to right. Let's still see if it works for the sample tests. Still works. And now uh two binary searches are a little bit more time consuming than one. Well, twice more time consuming roughly. Uh but I think we will be fine. Let's see. Uh so I want to do some lower bounds. lower bound from a begin to a end. No, not from a begin plus j + one because I want uh to investigate the number of ways to choose the maximum on the right. So on the right from j a i and a j were two first elements and then I'm counting good third elements.

23:10 uh from this to the end I want to find something greater than low. So at least low plus one or I can choose upper bound of low. This will find me the first element that is greater than low. Also what I want is first element that is at least high because this is what I do not want to accept and then so this is first good this is first bad the difference between them will be my answer I think we can subtract iterators like Nope. Uh I got negative one maybe. Okay. So search for high. Oh uh I only want to do this if low smaller than high. Maybe I don't want something stupid. Negative.

24:26 Okay, now it works. I think yeah, it works. Now you have a choice during a competition to submit this or to test. For example, here I'm not sure about the the runtime. I'm not sure about the constant factor. Can I explain the problem again? I'm finishing it. So just wait for the next problem. Have I done to some problem in lead code? Yes, I have. It's similar. Now, uh what we can do is either submit or test the speed. And I'm lazy and this is a stream where I mainly want to talk about solutions. I want to solve problems. In a contest, if I was really unsure, I would use custom invocation here to test how fast this is on code forces judging judging system for a max test. And max test sometimes is hard to find but here I think a random sequence of values would be okay. Uh but we got less than half a second. So it was it easily fit in time limit of 2 seconds and a half.

25:32 Okay. So summary of the solution here is that as follows for this problem C that we have just solved is that you have a sequence you sort it and you want to count such triples of values I J K such that some inequalities are satisfied. You cannot do it in n cubic. You cannot iterate all the triples and the inequalities they boil down to something like this. When you already have the two elements I and J let's say those are five and eight. Then you want the third value to be smaller than 13. So this third value that you want it should be smaller than the sum of those two five and eight. So smaller than 13 and also greater than the last element in the sequence. Let's say that the last element is 20 minus the sum of those two. In this case, that's seven. That would be a little bit stupid. Let's go with 15.

26:35 No. Uh 23. Okay. Let's say the last element in the sequence is 23. The story says that the our opponent can choose it. And then we don't want that value to be greater than the sum of our three values. But after transforming inequality we got that the blue element that we now want it should not only be smaller than 13 but also it should be greater than the greatest element minus the sum of those two 23 minus 13 that's 10. So in this case 10 I want to after iterating two elements 5 8 I want to here count elements that are in between of values 10 and 13. So here this will be some range of values that indeed are greater than 10 and smaller than 13. Sorry about my face covering the stuff.

27:27 And you can do it with binary search. You can binary search this position where values greater than 10 start and this position where values greater equal 13 start. If you subtract those two indices, you will get how many possibilities there are. This is n squ that multiplied by logarithm from binary search. And there are other solutions too. In particular, you could achieve faster n² time complexity if you went with uh with two pointers. And I'm like 95% sure it's possible. Uh how can I always choose three else so that Bob can beat it with max global?

28:10 Bob can always choose max of those three. Yes, Bob can choose max of those three, but also could choose the global maximum instead, and it might turn out better. Okay, problem solved. Let's move on. We skipped B because I thought it's ugly. Reachability and tree. Let's see.

28:50 I need to later set up OBS some more so I could click a single button and change the layout when needed. One moment. Right. I'm back. Go for e this easy ad hoc. I mean I want to read it. The statement is short enough. This is the link. Let U and V be two distinct vertices in a directed graph. Okay, directed. Um, it's good if there is a path from U to V. You're given a tree. Check if it is possible to assign a direction to each edge of this tree so that the number of good pairs is exactly n. Uh, print any way to do it.

30:36 Well, I I I want to solve it. I think maybe I will not code. Maybe it will only be thinking about a solution. Okay. So given a tree, choose directions of edges so that exactly n pairs would be reachable. Well, n minus one pairs are reachable by default because for every edge you direct it in one way. So this already gives you something.

31:20 Right? So for example here this is already one pair where from three you can reach five. If you direct it the other way it would be the other way. So what you want to achieve is that only one extra pair is reachable. So there and here that pair is three and two from three there is a path of two up to two. So I think that the goal is direct three edges in such a way that there is exactly one directed path of three nodes two edges and nothing more and the question is is it always possible I don't know so far so in a general tree how do we want to achieve If I direct let's say everything almost everything I want to direct depending on parity. So if this goes down I don't want those to go down because it would give me a lot of paths.

32:25 So instead it needs to be like mirrored. So if from the root everything goes down then from children of children everything goes up. So like this. And from here everything goes like that. So there are layers like everything here goes down. Everything here goes up. Everything here goes down. This is by default what we do. And I want exactly one thing to be the other way. And most likely I don't want to change something in the root because that will give me a lot of modifications. Maybe it's enough to change something for a single leaf. If I choose a single leaf like this one and I flip it, uh, no, that doesn't work because there can be multiple siblings.

33:21 So instead, maybe I'm looking for a node that has a small degree. Generally I'm looking for a node where one edge will go in, one edge will go out and nothing else. If there is another edge going out, this is already game over because this will not be satisfied. There would be one and second edge. So it seems that I'm looking for a note of degree two. If such a note exists, we win. And the solution is to run DFS from anyone anywhere like think about it as the root and always when you enter a new node the direction to its neighbors will flip except for this one special edge where that's not the case where going out of it one edge should be out the other should be in.

34:18 So one possible implementation find such a node A and treat this node as the root from this root run the FS but it's it should have degree too it will have two neighbors call them B and C give different directions from A to B versus from A to C one should be in one should be out and then DFS should just continue flipping the state always yeah this is why this is one note indeed I use just a Wacom drawing tablet. It doesn't even have a screen. So, it's like a mouse. Uh I think I can code it because it's like what four minutes.

35:06 So I will skip a problem either if I don't like the statement or what it is about or if the code is annoying for some reason here. I don't think that's the case. What do we print? Yes. And then print the edges the directions of edges.

35:48 I'm looking for the root and that's something where the degree is equal to two. If so, then root is equal to I and break. If root is still negative one, so I didn't find such an edge, then print no. Don't skip E. Is it such a nice problem or is it a hard problem? Well, actually, don't tell me. I'm not going to skip E. If everyone hates those longass storybased problem statements, then why don't problem setters just switch to lead code styled problem statements? lead code uh uses more standard problems and you cannot do that in code forces.

36:35 You will not get enough problems and not enough variety and difficulty of problems. Believe me that it's very hard to create thousands of code forces problems and that's how many there are such that you would only use short statements. um and return and otherwise run DFS. Here there is a parent and there is the direction for everything among edges going out of A. If it's not equal to the parent from where I came then run DFS flipping the direction and additionally if direction then print uh A B else print B A

37:49 here edges clear edges resize n + one. So this dfs will just always flip the directions. And here what I want to do is dfs from the root into its first neighbor edges of root of zero with value of false and to the other neighbor with value of true. Let's say zero and one. And that should automatically do everything I think. Let's see if it doesn't break. Uh I didn't print. Yes. Now I'm not going to compare my output exactly with this one because there are many possible ones. I think my output is too long. I print stuff multiple times. Everything almost everything I print twice.

38:49 Why do I do it? Oh, because this is the other way around. I want to say no. No, no, no. Huh? Why do I print stuff twice? because only if I'm not looking at the parent I want to print and run the FFS the if was in the wrong place because of that I would always always print also when looking back at back back at my parent uh now is this good number of lines yes it is and in code forces you're not penalized with time penalty for wrong answer on first test. So even during a contest, I wouldn't check my output. Uh what why did I add int if statement?

39:52 Uh this one because otherwise I would get a warning with proper compilation flags and you want to have a lot of proper compilation flags with a lot of warnings. This is different type from here. This is uh this is an signed int. This is unsigned int. So if I did this, I would get a warning. I would not get the warning. Why don't I have a warning? C++ warning. uh put up different types and site

40:38 I want to have that warning. So I'm talking about compilation flux. Maybe it needs pedantic but I used to compile without pedantic on the previous machine. I never used pedantic and I many times did that w is here. Strange

41:29 H. Do you get the penalty when you get runtime error? Yes. Compilation error. No. Okay. Strange. I mean, I could add a ped w extra. This is something I did use in the past. So maybe it's that. Let me try.

41:54 Still still no compilation error. So I want 23. Uh pedantic though pedantic might give me more warnings. Still not. That's very strange. I will investigate this after the stream. Still I'm used to doing this so I will keep doing it. Okay. Uh so recap of problem D before we move on is that we needed to achieve something that boils down to this. We want to direct every edge in a given tree in such a way that there is exactly one directed path of three nodes two edges. So almost all the paths we want to see this shape of one edge going into another edge only once in a tree.

42:53 And easily you can figure out that if there is a node with big degree then all the edges need to be directed out all or or instead all the edges can be directed in but not both. It cannot be a mix because you will have a lot of paths of length two. And there should be one exception. There should be one node of degree exactly two where one edge goes in one goes out. So the solution is find such a note where degree is equal to two. Say that one get one edge goes out one goes in and everything else with the fs continue uh analyzing edges and do the direction opposite to the previous one. If you went in, then here you want well also in but as you go outside as you go to the right you want to direct them to the left. So this one was to the left so to the parent in the tree. So this one should go to the right. So in in the FS what I did in the FS is I had a current node. I had a parent from where I came and I had a zero or one

44:00 value of direction. Do I go to the right? So to the child or to the parent and I would always flip it to the opposite value when continuing the DFS. Shall you do streams for upcoming cut forces contest also? That's that's a vague question. If you're asking me if like today I will do a stream for the next division to round then no. But yeah, I will continue doing streams this summer. I have time. Please try streaming more often if possible. I will try. Do you offer coaching for II by any chance? Uh yes, I will soon on conferences announce some group classes for summer.

44:48 Uh so so far the only thing I can like uh I can suggest is this. So this is what I already set up in the past few days. Here you can in particular schedule either a class or a short call with me. Uh and uh yeah and soon though I will start group classes. So that's a little bit cheaper per person. Obviously you can look this up. Okay. Uh let's continue. E three colorings. I wonder if we should even tackle the F problem. We'll see. This is the link. Cons. Consider a rooted undirected tree. Each vertex can be colored three colors.

45:50 Blue, green, yellow. Coloring is beautiful if it meets these conditions. The root is green. Blue and green vertices are reachable from each other without passing through yellow. Yellow and green are reachable without passing through blue. So this is a connected component and this is a connected component where green is like middle part. Blue and yellow and the root is also green. The tree is rooted. So, oops. Uh, you want the root to be green and some parts connected component I guess with the root. That's my guess. And then some outside parts will be yellow, some are blue.

46:46 Okay. Calculate the minimum number of vertices of a true exactly M. Beautiful colorings. What is the price? €50 for a call. So like discussion, €200 for a lesson. Okay. Full 90 minutes something mock interview or class. For if you decide to do go with weekly classes with me, one-on-one, it's a little bit cheaper. And group classes will be like I don't know 30 euro per person per lesson 40 euro something like that. W extra is what gives you warning while comparing signed and unsigned. I just checked. Uh, let's check that. But didn't I try to compile with that?

47:52 So now I don't have the int here. I have w extra in my compilation flag and it didn't give me a warning. Also, I don't know if double all should already turn on double extra by default. Yeah, strange stuff. Okay. Uh the when you read such a statement, you cannot immediately jump to analyzing how to get beautiful coloring colorings. You need to understand the nature of the problem. Maybe there will be some formula that you figure out. Still we don't I don't even care for now about this part. I want to analyze what this really means.

48:41 We want to understand this. So uh let's maybe leave this on the right. Okay. Does that work? So green vertices at the top. I want the root to be green and I think it will be a connected component. I'm not sure though. Then blue and yellow. There can be something blue here. Let's say edges are not colored. Vertices are colored. What's well if I add something green here and there is at least one yellow then this is already bad because green and yellow is not connected without touching blue so this is what you cannot have the blues can also be let's say here yellows can be there now can I do anything more complicated than what we're looking at so will this be a sub tree of green. We're connected to it. We have sub trees of other colors.

50:06 Do we need at least one blue, green, and yellow? Because if we don't have anything yellow, then green and blue can be in every configuration. So well still the root is green but this would be okay right I think this is okay 4 seconds limit I mean it's not that important like M is here big maybe M instead could be 200,000 and you would have a standard time limit There isn't a big difference between time limit of 1 second and 4 seconds. If you see five plus seconds, sometimes it might be a hint that this is a square root time complexity or they wanted to cut out some logarithm solution. Because of that, they needed to increase the limits a lot. Maybe it's an FFT problem.

51:16 But mostly up to 4 seconds while solving the problem, I don't care about it. You can have all green, all blue, etc. I mean there the root needs to be green. Oh, if you consider all yellow and green vertices, they are reachable from each other. Okay. So, I understood it subconsciously as if you have any pair of yellow and green, they need to be reachable without going through blue. Okay. Uh you're right, guys. This doesn't work. So, it's only this sub tree of green and connected to it this stuff. Uh calculate the minimum number of vertices in tree with exactly M beautiful colorings.

52:16 So what I want to do is like figure out the shape of a tree such that number of ways to color is something. So we are given a tree. I'm giving a white tree and not given I need to consider it. So I'm given a tree and now the task is everything by default touching the root will be green and starting from some points I I think it will be very important to consider such cut points there should be some cut points where I decide everything below has a different color and one of the two colors Uh so I choose some I can choose some edges in this tree.

53:10 Uh as long as they are not with vertical orientation to each other. I cannot choose this edge and this edge. And for every such edge I have two possibilities of deciding the color of stuff below. So it's almost almost but not exactly the sum over value k of number of edges that will change a color of n minus one choose k multiplied by two at power k I'm saying almost this this would make sense because among n minus one edges in a tree you choose k of them for each of them you choose if the color of sub tree below will be blue or yellow That being said, you don't want uh two vertically two edges such that one is below the other. It's a one is it's sub tree of the other. Um you cannot for both of them decide to cut it and to change color of stuff below.

54:11 Why does earlier idea not work? The tree that I erased doesn't work because it actually doesn't satisfy this condition if you think about it. check announcement in the explanation of Yeah sure. Why didn't they make drawings? What also might be important is that we're not investigating arbitrary tree. We want to find the optimal tree and because of that only some shapes maybe we want to consider. So this doesn't work because it doesn't understand that edges can be above each other. But that being said, this would work for a star. If the tree was a star, so just one root and children of it, it this would work.

55:27 If maybe size of the tree will be small. If size of a tree is no, this is not an easy problem. Huh? So I let me explain why I dropped an idea. Stupid idea is I I wanted to say maybe n turns out small. N is the optimal number of vertices. And I thought for a moment maybe the number of colorings grows exponentially and because of that n small n is enough like up to 50 and because of that I can do different things. That was that would be stupid because every m needs to result with different n. What? No. Oh no. That that's not true because uh it's different shapes. Okay, never mind.

56:30 Maybe it's not a stupid idea. So maybe even though M is big up to 500,000 N is very small. Just trees of size up to 20 should be considered. Still there are a lot of them. Where is the wind screen with formulas? Uh it's there behind that behind that uh wardrop thing there. I don't know if I will want to take it out for every stream. I will see.

57:21 Okay, given a tree, I'm sure I could do it with some kind of DP that goes bottom up and it counts number of ways to choose different edges or notes to cut so that they would be like next to each other. It's some it it would be I think DP of node by count and in the sub tree of this node how many ways there are to cut that many edges so that we would only cut you know cousins not ancestor descendant but we don't have a tree if m was up to maybe 10,000 I could try all possible possible shapes of a tree up to some size like up to size maybe 10 or whatever and then for each of them count the answer but I cannot possibly I don't think I will be able to consider enough trees to hit all the values from one to half a million

58:44 Maybe for some reason we will need to look at binary representation of m because here we hit something exponential. In particular, it's a power of two. Should I be able to solve this problem by now? How how quickly did people solve it? Uh 10 minutes, 10 minutes, 15 minutes. Okay, I should be able to solve it in few more minutes.

59:45 Well, if you look at a sub tree, you can say that it has some number of colorings. And it's basically independent from others. Maybe it's one big DP problem. Maybe there will be FFT involved. Can it there be FFT here? Not sure. So if the root is green, uh what are possibilities for children? Either this child is also green. It has some sub tree size here. And it's basically the same problem as originally. So whatever the number of nodes here you can read it from DP uh or instead a child can be already yellow and then uh everything here is yellow only the shape matters.

1:00:51 Oh then I mean no matter the number of nodes here the number of ways to color will be one. So if you have like x nodes here then number of ways to color this child of the root is 1 plus dp of x where this is number of ways to color it assuming that this node itself is green. So this will be the answer for that sub tree plus one because this also can be just fully yellow or fully blue. So actually two not one. So this will be multiplied by something like number of things for other children.

1:01:44 Oh and wait now I said something at the beginning maybe about factorization or product. If you have the you want to achieve m as the product of such values in particular those values will be at least three. You want to express m as the product of values each of them at least three. And what do you have as the very basic thing or what what if this is a prime or something like that if it cannot be expressed as a product. So if for example you want to achieve m equals 7 I think it means that the root needs to have exactly one child and its dp of x needs to be exactly five.

1:02:48 So let let's say that m is seven. Then you have the root and you want to here create something with answer of five. Five also is a prime. So it seems that okay you have this and you now need to here create something with answer of three. So free is also a prime. Uh so we have this.

1:03:26 But wait, won't we get an eight here? What is the answer for seven? For seven, the answer is four. They didn't explain. I feel that I'm on the right track. I want to do a brain scan while AR is solving problems and see how many neurons are firing. That would be interesting. Uh you've been hitting gym lately. How many collaps pull-ups can you do in a row? No, I'm I don't go to the gym, but I play a lot of volleyball. For the past year, I go to volleyball twice a week, sometimes three times. If the number of trees with only green and blue is X, and then for green and yellow, it's also X.

1:04:19 No, no, no. If something is uh let me try to reply to this message regarding this message I don't separately count I don't actually count uh trees with green and blue and trees with green and yellow when I look at my child when I have the root and I look at its child I have a possibility that it's green the child itself and then below there will be whatever it's like a recursive sub problem of the same thing where I count trees that have green blue and yellow so that's dp of x and the other possibility is that this child is yellow and then below I cannot have another green everything is yellow yellow that's one possibility Remember that we consider that the tree is given. It's not given but we need to find such a tree. So there is one possibility for yellow and there is one possibility for blue. So this is 1 + 1 + this. This is means child is yellow and everything below is yellow.

1:05:41 Child is blue everything below is blue. And this means child is green. Everything below is green, blue and yellow. So actually it's not that we ever here count something that is only green and blue. That doesn't happen though. Reasonable question. This is why I'm answering. Uh, and what's what did I do? What did I click? Okay. What's DP of one? Uh, DP of one is well, you can only have green. What's DP of two? You have green. Green. Green, blue, green, yellow. So we should get a free. Okay, that works. All right. Now, regarding factorization, I wonder if we should do it greedily or we should do it more like DP.

1:06:52 So if I have some value like m is equal to 40 should I consider all the different factorizations of it into values that are at least three because 40 can be four * 10 also can be four times or maybe 8 * 5. I don't feel like I can say which version is better. So I think we need to recursively find all possibilities. I don't think there can be many of them. But it's very hard to say. I would need to just test it for a reasonably big value with a lot of factors. So I feel like we will have a recursive solution that will try to break M into a products of values at least three. And for each of them we will run recursively to see how uh big the tree size can be.

1:07:55 So DP of three should be five. Wait, what is this exactly? What am I writing? I'm saying that for a tree of size two, the number of ways is three. Uh, shouldn't I say the other thing? Shouldn't I say for number of ways equal to three the best possibility is two nodes. I think that's the order I want to go with. So I want to define DP of M defined as minimum number of nodes. So that's the actual answer. And when you want to compute it, you try breaking M into different values. For example, if m is 40, then one possibility is that it's 8 * 5.

1:08:49 uh you know that m you should represent as this and you say then dp of m you want to minimize with the possibility that you have the root which is one plus dp of 8 - 2 plus dp of 5 minus 2 the meaning of this is the following I want to have a sub tree with eight ways to do it. But I have two ways that are basic. So I want Okay, maybe this uh Okay, ways ways.

1:09:46 Okay, I want this to be 40. I want 40 ways. There is a possibility. I can represent 40 as for example 8 * 5. So maybe this is eight and this is five. So this is six and this is three. I want a three. I want smallest possible tree such that it will give me six ways. Hence this. So I represent M as the product of some values not necessarily primes. Every AI is greater or equal 3. And then DP of M you want to minimize with 1 + DP of A1 minus 2 * DP of A2 minus 2 and so on. I think that's the solution. What did I write here?

1:10:49 DP of phrase too. What? Oh. Uh, I didn't fix this. this meant I mean it's not easy to figure out but there is a tree with three nodes such that this and DP of four is also possible no it's not possible no it's not possible but DP of 9 will be and I think DP of 9 happens to be three nodes because it's this shape. So 9 is 3 * 3. Three is possible this way. No, it's this. So five. Well, let's see what program tells me. I think that this is correct. But it's very easy to mess up the order of thinking here. Uh like it's it's in particular unusual that the dimension of DP is number of ways.

1:12:14 Uh P of 9 is three. Okay. So wait wait wait I confused myself. DP of 9 is achievable like that. Will my program correctly see it? M will be represented as 3 * 3. Oh and we read not DP of three. We already DP of one. So this times this and this is plus not product. It's number of nodes needed to achieve this number of nodes needed to achieve that. Okay. Okay. Okay. A bigger example for a moment. Let's say m is equal to 1,000. In particular, I can represent this as 4 * uh 25 * 10. Okay, that's one of many ways. So I say that what I can create is I can try to create such a tree that it has three children.

1:13:30 There will be small sub tree here, bigger one here and even bigger one here. And I want them to have uh I want this one to have two ways 23 ways and eight ways to be colored such that the uh this one is green. I want eight ways that this is green and this is whatever and I recursively ask for a number of nodes needed to achieve that. Why eight and not 10? because there is also a way that this is everything yellow this is uh everything blue two extra ways if I see that oh it's possible not not green it's possible to use let's say five notes 1 2 3 4 5 it's possible to use five notes to achieve eight ways then I will say okay five notes needed here plus let's say 10 notes needed here plus let's say one note needed here plus the root itself 12. So that's 1 + 1 + 10 + 5 that would be 17. 17 is a possible answer. The number of nodes to achieve result of 1,00 ways.

1:14:49 No, I'm not connecting tree to another. There is a root and there it's children that are independent from each other. It's not the children. So the sub trees made from children. they are independent. So if this one for this one I need you know uh if this one gives me 50 possibilities to color and this one gives me 20 possibilities to color then 50 * 20,000 possibilities to color and if this one requires five notes this one six notes then in total that's 11 nodes notes I add up ways I multiply uh let's so what was the most important thing this I'm Going to copy this.

1:15:43 There are many test cases. So we need to solve for every M. To be honest, I didn't think about it too much while solving the problem. Um okay. Uh let's also define DP DP of M defined as minimum number of nodes to achieve M ways. Okay. And because it's minimum by default it will be infinity. I I saw a question in the chat. It will not be negative one. It's easier to use infinity when you minimize. So there are test cases. I'm going to just in main for for a moment forget about test cases. We'll take care of this later.

1:16:44 We have This is the max. Can I do this? Okay. uh DP of one is one. Okay. And for every greater M. You tried it. You try to split it into the product. Why did I remove what I copied from one note? Uh this will be by the way the last problem I'm solving today. Uh stream on common proving techniques used in solving code forces problems. Common proving techniques.

1:18:06 This would be more of a math slash logical stream. I'm not sure. So it it would be I think it would need to be a lecture that I prepare for a lot. The idea of those streams that I do every few days is that I just solve problems. Maybe it's a good idea for a lecture one day and stream on constructive problems. I think we can make such a topic stream one day. I'll think about it next week as I posted in code forces. Uh next week few days I will not stream because I'm out of war. So maybe then while out of war so I will think about it.

1:19:01 Can I say that DP of smaller M already considered this? Interesting. I think that I don't need to actually split into all the pos recursively into all possibilities of how this splits. I will just say that iterate the the first divisor and then this already some other value of M considered and DP of this smaller M was its own value of this already. It includes a plus one. So I don't need to add it and I just need to add this DP of 2 is unreachable right I cannot do anything with it. uh also then what I will do is just read M if DP of M is infinity change it to -1 print it

1:20:26 okay for a moment slow quadratic version iterate the first divisor if m module a is zero Then DP of M minimize with DP of A minus 2 add to DP of M / A. That's like how the the rest works. In particular, this can be one and if so it will be just one plus this which is correct. Okay, let's decrease the maximum so it would work in time. So recursive function wasn't needed.

1:21:23 Why so slow? Oh, I thought that I'm changing this to 5,000. 1 2 3 4 3 That's good. Negative 1. That's good. Okay. So just what's needed is we if you want to iterate all divisor then you should do it by iterating multiples actually just like in prime.

1:22:09 And now it's an login. That being said, I find it strange that the time limit is so big. Maybe it's because of another solution. Uh, sorry to comment about specs at the beginning of the stream. No problem. I mean, this it's not a surgery to save my life. It was my choice to to get it done. So, it's not something that you need to be sorry about. No problem. Oh, changemax, of course. Uh, thank you. Thank you. Thanks to Luxa Gamer. Usually during the streams, I don't want help solving the problem. I want help debugging because debugging is boring and annoying to observe for you. May you stream on persistent bits dynamic segmentry.

1:23:14 uh to be considered the smaller x as in this don't have the same factors as m. See uh zru I want to consider different representations of m as the product of this where every ai is represented as 2 + x but so because of that the values here should be greater or equal three still this needs to be a divisor of m but actually when I see that this is divisor of m what I will look up is this value minus two uh I don't know if that answers your question can you summarize your solution once please cheating yeah that's I mean help getting help with debugging is cheating I agree still I don't know why the time limit okay summarize the solution though the problem is quite abstract so if you don't know the statement yet you will not be able in one minute to figure figure it out and understand the solution okay so and this is the last think we're doing today. Uh so problem E summary we we are given the target number of ways

1:24:46 M. We want to find the smallest tree such that exactly m colorings uh with m colorings and I will define colorings in a moment and uh output only the number the min number of notes n m is the input value m is up to half a million. Now for the number of colorings we want to find such a tree that if you consider it you analyze number of possibilities to color it green blue and yellow so that green would be the root and some connected component of it like next to it let's say and then out of it they grow blue and yellow sub trees for example this can be yellow maybe this is yellow and then this is blue you cannot mix blue and yellow in the same sub tree.

1:25:48 In other words, it's some green shape and growing out of it. Blue and yellow sub trees inside of blue sub tree there cannot be something yellow or green. You count the number of such colorings. And now if you want so that that's the task and we can observe that if you have the root which needs to be color green that was the requirement and it has let's say three children or any number of children for every child it of course has some big sub tree below there is a sub tree either this uh child is yellow and then everything below needs to be Uh so that's one possibility.

1:26:41 Or this child is blue and everything below is blue. That's one possibility. Or finally this child can be green. And then the number of ways to color this is equal to DP of size of this sub tree because it's the same as the original problem. So plus DP of X where X is number of nodes in this sub tree. This is the total number of nodes to color the sub tree. The 1 + 1 comes from the fact that for this child of the root we don't require it to be green. It can be yellow or blue and then everything below is defined in one way.

1:27:17 This is number of ways to color the sub tree and then you have some number of ways to color the second sub tree, the third sub tree, the fourth sub tree. So you have the product of such values. If the first subree size was X, second is Y and so on then you have you will have this. Let's simplify it to 2 + DP of X. You multiply it by 2 + DP of Y and so on. So M the target number of ways is equal to this. You have target number of ways and it is equal to those things. What is DP of X here? It's number of ways to color uh this a tree with X nodes.

1:28:02 But I want to minimize. So actually I don't know this and I cannot afford to iterate always how many nodes will be in such a sub tree. So instead I think what will be this value? Let's say that m in particular can be represented as 40 * 70 * something. I consider factorizations of m. So if one of divisor of m is 40 I say okay maybe I want such x such number of nodes such that this value is 38 that's the my divisor of m minus 2 if there is such x such number of nodes that there exists a tree with answer equal to 38 the number of ways equal to 38 then that's good because that gives me 40 here multiplied by some stuff it will give me m ways but I want to Well, how many notes are needed for this? So, I want to know if I want 38 ways for tree of some size. I want to know that minimum x size is equal to for example maybe 15. Maybe there is a tree with 15 notes. Let me hide the camera. Uh there is a tree with

1:29:11 15 notes with exactly 38 weights. This is very important for me given the number I want to know min number of notes. So actually I would in my code I used different kind of DP not DP of nodes is equal to ways I didn't use that I instead used DP call this DP2 of ways is equal to nodes that's quite unusual but knowing the number of ways I want to achieve I want to know minimum number of nodes for example here it would be DP of uh 38 is equal 15 when I read M from the input I want to just print DP of M right the I'm given number of ways I want to print how many nodes are needed and now how do I compute this DP for every M I consider its possible divisor if I know that M is equal to A1 * A2 a A3 for example then I say DP of M is equal to minimum of itself comma uh DP of A1 minus 2 plus DP of something and so Y minus 2. I explained it here. Why do we add? Because this is number of nodes in the first sub tree. This is number of

1:30:29 nodes in the second sub tree. Number of nodes in the third sub tree and so on plus one because you also have the root dp of this. This is number of nodes in the first subree. So sub tree of the first child of the root number of nodes in sub tree of the second child of the root and this is the root itself. You cannot afford in terms of time complexity to try all factorizations of m but you can only iterate the first divisor and you can do it primes style by iterating multiples actually and instead of immediately factorizing this it is just some kind of smaller m prime that you already consider different factorizations of. So you just say I you wonder what this should be. You iterate the divisor a1 and then this this plus that that's just dp of m prime. So let's this this this is dp of m prime.

1:31:32 Uh and we can then once again take a look at what the code said for that. The code of course eventually it is just few lines of code. So very simple but coming up with it wasn't necessarily trivial. Here we prime if style we iterate first the divisor. So that's a is basically number of ways to solve to color the sub tree of the first child of the root and this is the multiple the value m so that for that a would be a divisor and then I look at dp of a minus 2 like if I want 40 ways for this first uh sub tree then I want it if we consider that the root is green I want it to have 38 ways plus one way that all is blue plus one way that all is yellow. And DP of this is what I called M prime a moment ago and my n / a is the remaining number that I want to factoriize and dp of that already tells me.

1:32:38 So this actually this highlighted part it hides inside the 1 + dp of a2 minus 2 plus dp of a3 minus 2 and so on. This instead can be replaced with iterating the sequence of other divisors and using that time complexity m log m because it's like prime uh will dp of m divided by a be computed correctly? I think what I used here without explaining is the fact that every m can be considered in order of decreasing the so in order of increasing factors. So fm maybe can be represented as 50 * 20 * 15 * 40 but in particular it can be represented let's say uh like this I mean one of the ways I think so what do I want to claim here I claim this when I get to value a equal to 50 those values val were already considered. So DP of this highlighted M is computed correctly using values smaller than 50. So now when a is 50 and I consider this M that is product of all of this DP of M divided by A will be

1:34:06 computed correctly using those things. So here let's say invariant every dp of m is computed correctly using divisor from 3 to a minus one something like this. Uh yeah, by the way, Gupta, very good question and it would be perfectly possible that this is some huge issue causing the code to be completely wrong. So good that you asked. I actually did not think about it at least not not for more than half a second where I maybe subconsciously said ah maybe it will be fine n square root of n solutions. Oh, maybe maybe I'm not sure. Let's take a look at the editorial. Stuck at candidate master. What to do? Just like stuck at every other level. No, practice properly. Solve problems that are challenging for you.

1:35:11 Yes, you need to indeed Gupta think about the largest one. So we always in this factorization what we basically iterate is the biggest divisor to be used which doesn't necessarily be mean the biggest sub size but there is correlation. Uh what does the editorial say? Oh the solution m square root. Okay so that was allowed. I I could do it like that. Uh interesting how short the final code was while solving the problem. I thought that it will be more complicated to code. Do you live stream on YouTube every day? No, far from it. I will live stream tomorrow and maybe in two days and then I will have few days of a gap.

1:36:02 Uh okay, few things. No, uh I I don't remember if we have command for calendar or something like that. calendar schedule. Oh, I have this here. Does it work? Oh, it works. Okay. Uh, I will now post some stuff. Uh

1:36:39 this is a calendar that you can import if you want. But also on code forces I maybe a day before I will try to do it a day before I post the schedule of my stream and there is a countdown on YouTube. I don't know maybe I will also create events but that's more work. But once you add up a few things that each of them takes two minutes you eventually have something very annoying. uh it's where it's easy to miss something and because of that I might just eventually uh sooner than later decide to again give up streaming for a few months because I don't want to bother setting up stuff for 20 minutes. That that's just really annoying compared to solving problems where solving problems is fun.

1:37:37 Uh there is also this blog I made uh where you can look it up with just schedule for the next few days. Uh, and finally, if you want to book a call with me, here's another link. I need to make all of this into comments. I also should maybe put some text at the bottom of uh my screen like no, you know, here at the bottom of the screen from time to time there will be some message like advertisement of stuff. Uh, okay. Uh, are we good? Should I do anything else? What should I study to understand time complexity of this? Should I?

1:38:21 So, Adam Vinovich, regarding your question, what should I study? Basically, if you study prime, cif of eratseness, you will in particular see there the time complexity chapter and it explains why it's an login. what I used here today is the same. Uh so let's say make sure you understand that algorithm. Don't give up streaming. I will try but for that I I for sure I want to keep the stream setup to be simple so that in at most 10 minutes I could start streaming. That's let's say my limit. And I will actually stream more often and for more months if I keep it simple.

1:39:14 Uh okay. Oh, I know what I want to ask uh everybody. So today, was there much spam today in the comments? I didn't read everything, but I think it was fine, right? I remember from the previous year that often somebody especially on YouTube somebody would often repeat the same question and it would be very unrelated to the stream. I think it was fine. Did you find it annoying that the chat messages were on the screen as well? And was it a good strategy that when I'm solving a problem, the messages are here and then when I'm talking and the right hand side of the screen is black, then they can be here as well. Is that a good strategy?

1:40:08 I know some questions were repeated. It's very hard to avoid that, but I think it wasn't that bad today. Oh, Anit, uh, good point. Select problems for next on Discord. Okay. Uh, by the way on Twitch you have Discord command favorite Linux distro. I keep using YUbuntu but I don't really use others. So should I be able to compare and recommend.

1:40:45 Okay. General I've opened the Discord server. Where do we want that to happen? Just I don't want it in general. Anybody using the our Discord server, what is the proper channel for this? I want to ask uh I want to ask you like not not a single person. I want to get suggestions for division one problems for tomorrow. Something hard, you know, difficulty 3,000 or so. I think there is Gupta a reason why I don't full screen editor after reading the problem. there are people who join and having this on the screen helps a lot in particular including this. Uh I understand that they can hit a comment to get the link but not everybody uses the chat. There is a huge difference between this and doing something on the right versus full screening because if you see you join the stream and you see this you have no idea what is happening.

1:42:04 Maybe what I could add traditionally do is on the top of my camera I could display some like here here the text information what we're solving. But I think that it's very valuable for people who are joining in the middle to see this also because they can look it up. They can even search for code forces three colorings and they will be fine even without a link swapping left right. I'm too much used to this but I will consider

1:42:43 how can I start doing code forces respect. Uh I have a YouTube video about that. If you search for Aria YouTube how to start code forces you will find my video exactly about that. Okay. Um for I will just use general for now. I need suggestions for good recent division one problems tomorrow stream. Okay. Uh so that's it. Uh tomorrow the stream will be when it will be 12:00 Polish time. So 1 hour ear one hour later than today. You will see countdown on code forces. Thank you everybody for joining for the suggestions questions and so on. I hope you enjoyed the stream. I would say put it in the announcements generally we move ahead easily. Yeah, Gupta. But I want to also collect the ideas and I can announce in announcements, but how should you guys post your suggestions?

1:43:56 So, not sure. We'll see. We'll see what happens. Now, I need to go. Bye, everybody.

Questions about this episode

What is discussed in "Codeforces algorithms problem-solving"?

In order: 0:00 Discord, Lead Code; 10:00 Lead Code; 20:00 Lead Code; 30:00 Lead Code; 1:40:00 Discord.

What is mentioned in this Errichto Hard Algorithms episode?

3 people, works and ideas are mentioned, including Lead Code, Discord, Codeforces. Each one on this page links to its own page with every episode that mentions it.

How long is "Codeforces algorithms problem-solving"?

The episode runs 1 h 44 min; the transcript is about 12,154 words in 104 timestamped sections.

More from Errichto Hard Algorithms

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