Codeforces algorithms problem-solving

What is discussed, and when

1. 10:00 – 20:00: AtCoder
2. 30:00 – 40:00: YouTube, Huawei, CodeChef, Twitch
3. 40:00 – 50:00: Google LLC, Google CodeJam, CP Hall of Fame
4. 1:00:00 – 1:10:00: YouTube, ICPC, University of Warsaw
5. 1:10:00 – 1:20:00: Google LLC
6. 1:20:00 – 1:30:00: YouTube, Google LLC, Facebook, Twitch

Notable quotes from "Codeforces algorithms problem-solving"

• Am I coming back to competitive programming? I still do competitive programming just not participating too much.

  about Codeforces · at 10:15

• Else we can print negative one saying that this is impossible at cutter has smaller statements. That's correct though sometimes they do not explain stuff enough maybe but usually I like the.

  about AtCoder · at 12:03

• Contests. There are some one week long or at least there used to be one week long contests. For example, there used to be code chef long.

  about CodeChef · at 30:51

• Yes, I do. I actually I don't watch Twitch at all. I do watch YouTube.

  about YouTube · at 35:35

• All if I have enough time to organize that and Huawei has enough time to approve this maybe there will be Huawei another Hawaii IO camp in second half of July. So let's say roughly July I don't know 17 to 22 just example dates. as in the.

  about Huawei · at 36:28

• So that's my plan. I wanted to share. if you have ideas or feedback, tell me I ranked two in Google CodeJam. Yes, I did.

  about Google CodeJam · at 40:46

• University for example University of Warso. I teach I help coaching ICPC teams in University of Warso.

  about University of Warsaw · at 1:09:31

• Participating today in the division one plus two. Why didn't you give Google interview? I didn't participate in Google interview because I didn't want to get to Google like if Google interview when you can create one at home.

  about Google LLC · at 1:19:56

Who and what is mentioned in this episode?

Companies & orgs

• Codeforces — Company · Business focus · 2 mentions
  A competitive programming platform frequently mentioned in the context of problem-solving and contests.
• AtCoder — Company · Business focus · 1 mention · first at 12:23
  A competitive programming platform praised for its problem statements.
• Huawei — Company · Business focus · 1 mention · first at 36:31
  Mentioned in the context of organizing programming camps.
• Google LLC — Company · Referenced company · 4 mentions · first at 41:06
  Mentioned in the context of interviews and competitions.
• University of Warsaw — Company · Affiliation · 1 mention · first at 1:09:31
  The speaker's affiliation where they help coach ICPC teams.
• CodeChef — Company · Business focus · 1 mention · first at 30:57
  A competitive programming platform mentioned in passing.
• Facebook — Company · Referenced company · 1 mention · first at 1:28:22
  Mentioned as a potential employer in a hypothetical scenario.
  I should join Google or Facebook.

Places & events

• Google CodeJam — Event · Referenced event · 1 mention · first at 41:06
  A programming competition where the speaker achieved significant success.
• ICPC — Event · Referenced event · 1 mention · first at 1:09:36
  An international collegiate programming competition.
  University for example University of Warso. I teach I help coaching ICPC teams in University of Warso.

Media & podcasts

• YouTube — Media · Platform mentioned · 4 mentions · first at 35:29
  A platform where the speaker watches educational and entertainment content.
• Twitch — Media · Platform mentioned · 2 mentions · first at 35:32
  A streaming platform mentioned in passing.
  And before that let me talk about one thing. do you watch anyone on YouTube or Twitch perhaps for gaming?
• Wendover Productions — Media · Referenced content · 2 mentions
  A YouTube channel the speaker watches for educational content.
  Let's say for entertainment for example most critical but also a lot of semi-educational stuff like Wendover production atriarch stuff sometimes about economics logistics.
• CP Hall of Fame — Media · Referenced resource · 1 mention · first at 41:15
  A website documenting competitive programming achievements.
  Because Google CodeJam website died. But there is something called CP Hall of Fame.

Full transcript with timestamps

4:10 Sound test. One, two, three, four. Suffering from yesterday's D. What problem was that? yesterday here. No microphone. I mean, you sure? Are you really sure? Mic is off. I think it's on your side. Yeah, it's working. Hi everybody. Token removing I mean, we can leave it for later. Not the first problem we do today. But if the editorial is not enough, maybe I want to take a look. It was very quiet. I don't know. So, the past two or three streams, actually, the sound should be much higher. Almost solved it during the contest.

5:20 Couldn't debug in time. That happens. Uh so do I want to maybe take a look here at this contest? I guess why not, right? So let's see some problems from yesterday. Uh skipping some you're given two non- negative integers. So maybe I will do this. So this is the problem we're trying. Not necessarily we will solve it. But usually with those first problems you can solve it in few minutes or I can solve it in maybe one minute. So doesn't hurt too much to solve to integers you can apply such operations. Okay. A only the first number you can modify increase it by one with the cost of X and X or if with one the cost is Y.

6:21 Now you want to uh make A equals B happen. I don't like such this this way of writing the statement. I think it's unnecessarily formal. What I would prefer to see in statements is that uh you have some value sometimes you can give it some meaning like it's the number of cookies but let's say that uh I don't know you're some this is how I would write this statement and I think it would be less discouraging for beginners to solve or maybe you disagree but I I actually want to hear your opinion. I would say something like that. Let's say you're a wizard or a wizard with n objects. N objects and that can be I don't know cookies, goblins, whatever.

7:22 Uh let's say cookies. Uh you can bake a new cookie for uh and it cost you something for let's say X coins. You can uh also apply some kind of magic. So cast a spell spell for Y coins and it will still of course this part needs to be artificial because you cannot describe the Xor operation in artificial way but let's say it will change the number of cookies using a formula n= nx or one uh or n becomes Maybe you need to specify that this is the current end. What is minimum total cost, minimum possible cost of obtaining exactly some kind of target cookies, Z cookies?

8:28 Target cookies. I'm not saying that this is different that this is significantly different. And if you are participating in contest and for you it's an easy task. I think it doesn't matter at all which version you choose. Actually, I'm not even saying that mar version is shorter. Just do we need to talk about it as like this where you are given two integers and you can apply two operations on a in this in any order. I mean well okay some some stuff need to be repeated anyway. But when I think about somebody who starts with programming this is terrible and this is okay. I don't know.

9:12 Am I doing a warm-up for division one plus two round? No, I don't have three hours. Certainly. So, no, I will not participate. Wild take maybe. And I'm not also I'm not a fan of long stories. I'm not a fan of forcing a story for every problem actually. So this is a little bit of forcing a story. But this seems so ugly. Also, usually when you start when coming up with a problem, when you start from a story, you should almost always keep it. But when you start from a formal statement and you try to create a story, very often it makes the statement unnecessarily long.

10:03 wizard is filling flavor text which people dislike too. I guess you're right. Okay. Uh let's start the stream where I actually solve the problems. Am I coming back to competitive programming? I still do competitive programming just not participating too much. I teach a lot. Uh okay. No. for actual the for actually the solution. Well, by exoring one, you will either increase by one or decrease by one. The decrease can happen only once, right? If your number in binary presentation ends with a one, you can exor with one to actually decrease it down to zero. Also by the way because of that I don't like this as division 2 a because many people again I think about beginners I think about somebody in middle school who just started programming they would do not know what this means. Okay so one changes to zero. Uh but then you cannot apply it again and hope that something smart will happen.

11:06 So this thing you can apply only once and only as the very first operation ever because later it never makes sense. It seems if you've just increased by one. So for example from four you made it up to five. It doesn't make sense to then decrease down to four. Right? So only if at the very beginning you have a five maybe you want to decrease it to four. So what you want to do is after reading the input a bxy if the target is equal to the starting value minus one then we can apply this decreasement the the decrease operation and the answer is equal to the cost of it which is why else if the target is greater or equal than Okay, then we will keep increasing.

11:59 But sometimes we want to we can do it with the extra operation. And finally else we can print negative one saying that this is impossible at cutter has smaller statements. That's correct though sometimes they do not explain stuff enough maybe but usually I like the atcoder statements. So in this case you want to keep increasing it will be a a + 1 a + 2 and so on and every second operation can be performed with the exor as well because if you for example increase from four to five 6 7 8 whenever you change from even to odd you can exor with a one. So every second operation can be xor.

12:53 Uh we need to figure out if the first one as well. So there needs to be something like this. Uh every second operation will be minimum of x and y and the number of times we do it is roughly b minus a over two. Sometimes rounded down sometimes up when is it rounded up. So when first for example here here I do three operations and if the first and third operation are both of this type then I want to do it twice. So I need to say if b minus a module 2 is equal one. So this is odd number of times that I apply the plus one and the starting value is even then the number of times actually is this rounded up not down.

13:44 Okay, then finally the answer is the every second operation times the number of times I do it plus every other operation has just a cost of X which is the cost of doing plus one times what is that? B minus A subtract times because this told us how many times we do one type of operation. This is how many times we do the other type of operation. Let's see if it works for samples also. Now I think that I actually I should have skipped this problem because I don't like it at all. Does it work? Uh there should be here negative one 3 6 1 3.

14:29 Uh so just for this test from two we want to make a one. uh which here oh I want to say that the initial number needs to be e odd so that the decrease would be possible now it's correct um why cannot send I see that somebody in comments already noticed my mistake uh proof you official yes sometimes I like I will skip something. But the getting wrong answer or seeing it wrong on the sample test also well doing something after that is also a skill that sometimes you should see me uh fixing just iterated from A to B. Was that viable? Was A and B that small? Oh yeah, I I actually misread this constraint. I thought that the number of times we will do stuff is big 10 to the 7th power and the costs are up to 100. So I misread the constraints but you're right. What I should have done and that would be way better is here just say uh while a is smaller than b if a modulo 2 is equal zero then do the minimum. So answer plus

15:53 equal minimum of XY else answer plus equal X and anyway I ++ this would be way better and then print answer. Let's submit that. I I'm not happy that I went with this over complicated solution. Let's maybe submit without running on the sample test. Uh during contests you shouldn't do it. Yeah, it's simpler. I agree. My first solution was ugly. You shouldn't do it that way. I misread the constraints. That's the only reason. So what uh second task given to points do something. Will I try again reaching for LGM? I think so. Maybe I just need to participate a few times. So you see when uh I reached the legendary grandmaster a few times and my logic was I don't want to stop participating. So I will not know stop participating in contests I want to keep doing it and if I drop below 3,000 I will reach it back. But as you can see, I stopped participating, which is a bit sad because I could have stopped somewhere around here. In

17:16 particular, I had a rating of exactly 3,000 apparently. I don't remember that. Maybe there was a recount or something re recalculating the ratings, but I should have stopped here. And with that, my rating, my nickname would look nicer. Well, geometry for hard problems. I generally like geometry for easy problems. It doesn't matter too much. You're given two points. You start start there and you perform n operations. Choose any point uh where the distance is exactly AI and then move there. Check if it's possible to reach that new terminal point.

18:04 That to be honest seems difficult. If it wasn't division to be, I would think that it's very very hard. I I have some ideas, but they will not work for that number of test cases. Oh, points do not need to be integer. Thank you, Zicus. I see. I thought that it's integer only and then I wanted to do something like DFS on a 2000 by 2000 grid to see what is the smallest distance I actually can move by something like that. Yeah, I think they should have specified that and put that in bolt. Is there an announcement about it? No.

19:09 But do not shout. Capslock is bad. Okay. So if you can move by any non- integer um you can move to a point that is exactly that far away. Cannot you reach everything? Oh n operations. I see. So just the number of n will be important. Right? Because if n is one, it's a spe special case. I think n is one must be exactly uh this distance away a of zero away and then no no the distance is given in every operation. So maybe let's let's uh maintain the distance that I can be the distance from the starting position. I think that's nice. In particular there we might be forced to move very very far away. I think I want to draw it.

20:33 So if you can from the start move by let's say three and then move again by two then you can combine that to almost everything. You can move by at most five but you will go back to the starting position to the distance of one and you cannot be closer than the distance of one. You can be anywhere from the distance of one to the distance of five. If your distance from the start to the target is between one and five, you can do it. Similarly, if you start and then you have few small steps and then a very big one, what matters is the big one minus the small ones. Even if you have multiple new small ones like here, still the big one minus small ones matters a lot. The there is a helpful observation here that so observation the order of operations does not matter.

21:35 So you can first think about that big jump and then the small ones or the other way around. So what I claim is that here the longest jump matters a lot. Oh, there was even a drawing. I think we will want to find the maximum. Uh so find max and then this maximum minus everything else. This is the how far from the starting point you need to be at least and then sum of everything is how far you can be. Finally, I want to use integers only when computing distances. You want to avoid the square root because that might lead to precision issues.

22:21 So we read n we have the two points px py qx qy read them their distance I'm going to compute using integers and that's long long type let's make a function for square. What am I typing? px qx. Um, okay. I typed something stupid here as well. Square root of py + qy minus qy. So many typos. So this is actually square of a distance. I'm not going to square it because precision errors are possible with real values. Basically, you don't want to do something like this. This is equal square root of something. Avoid that if possible.

23:27 They tweak the constraints in this problem such that regular double squar just works. I think that's a good decision for division 2B problem. Uh, okay. and then read the stuff. I could do it in constant memory, but I don't think that's very convenient. Also, sorting is an overkill if you only need maximum, but whatever. And now what I need is sum of everything and then the let's say difference this will be the maximum minus everything else there is a function for that like accumulate but I'm just going to do this sum all plus equal a of i if i is not n minus one div minus equal AI.

24:31 This is not the shortest way to code it, but I think it's quite safe. And finally if uh this is the minimum, it needs to be smaller equal that the distance. Let's remember about the square root and this then this is good. And because this is squared, then this is also what I want to square.

25:04 If so, then print. Yes. Square not defined. Find the comments should be removed. Why was it so slow? That was suspicious. And the the answers were all over the place. Am I reading something wrong from the input? Did I watch any of friends and seniors coding like we are watching your stream? I mean maybe maybe five years ago streaming competitive programming was a little bit more popular and few people like know Pet or Gennady also did streams and then I would watch it. Yes. I'm not sure if any of my friends in Poland did that.

26:29 Didn't read n uh yeah and I even got warnings for that right compiler told me. Thank you. So what I think what happened is uh while there was compilation I already went to copy paste the test because of that I didn't see okay so n I think was some huge value and I tried to then read end values and it took a lot of time. What do you do to earn your livelihood? I teach programming. I teach algorithms. Wrong answer. Maybe some kind of overflow.

27:25 I'm not happy about what happened here, but let's test a little bit. Uh let's say maybe create a test for that. I want maybe second file. I want two test cases. There will be two n equals to uh points 0 0 10 0. So the distance is 10. And now if I have six and three the answer should be no. If I have six and four the answer should be yes. So I should see a no. Yes. That's correct. Now if I go with 10 three and 10 four different reasons the answer should be um yes and then no. No. Here it's barely yes as well. If I do five now it should be wait what am I doing? No no no no. So for this to be a no I need to go very far away like 15 and then for now this is too much. If I do 155 this is okay. So I go to by 15 I go back by five. That's okay to reach a 10. And here 15 minus 4 that's too much.

28:55 It works. Different all might be negative. Good catch. Congrats to Q I AO123 for catching this. That's a Chinese nickname, right? So, Kisha. Yeah, this changes obviously. So what happens is if this is let's say negative negative 1 million then and I should it yeah I should basically up it to zero but it will be treated as 1 million instead. So this is bad. I in few minutes I could even create a counter test but what I should do here is just maximize with zero and as always I will repeat I want in in streams I want help like this with bugs because especially after I'm done coding or maybe let's test again because it's just annoying to do it especially during a stream where I want to I want it to be educational.

30:16 What I don't want help with is coming up with a solution unless I ask for hints. Maximum time you spent on a problem and what topic was that of uh I don't know 50 hours maybe more. So there are maybe 100 hours there are two week optimization contests with a with a single problem. So you spend two weeks on that and that that's that's when you can spend a lot of time for nonoptimization contests. There are some one week long or at least there used to be one week long contests. For example, there used to be code chef long.

31:04 Also, still in Poland, we have algorithmic engagements or potichi and there you can spend several days thinking about the problem even just a normal problem where it's not optimization. Also, there was bubble cap qualifications. It was maybe one month. I think it was one month. So I actually spent one week solving a single problem there. I remember eventually barrel camp mass was useful. Uh so there I did spend sometimes like 20 hours solving a problem not 20 hours non-stop maybe I did spend 15 hours non-stop so doing some optimization problem. Uh I'm not sure. I did participate in 24-hour contests where I would solve a single problem for the full time. So only you know taking breaks to eat, go to the toilet and at close to the end of the contest to also take a nap. Can I explain again the solution? Uh yeah because this the explanation is short.

32:16 So we were told in this problem B we were told that we can go we want to go from the start to a target and we are allowed moves in any direction by let's say F3 then a2 then let's say eight then a1 and so on and the question is can we reach the target using exactly those moves turns out that the longest jump matters a lot because it might uh move us too far away from the target or the start. For here, the order of moves does not matter. So, I can as well think about the eight move being first. And if eight move moves me there, then all the other moves I want to use to go back two.

33:05 Three. This is not up to scale. One. And the question is, are the small moves enough to move me back to the target? So what I want to check is the distance between the start and the target. Is it smaller than or equal to the maximum which is in my example is jump of eight minus everything else. So -3 - 2 - one. You don't see it. -3 - 2 minus one. In this case 8 - 3 - 2 - 1 is two. And if so this is good. Obviously also the target cannot be too far away. I also compute the sum of 8 + 2 + 3 + 1 the sum of everything and this is how far I can go and we can take a guess intuitively that everything in between is possible.

33:54 I can do different angles like I can move by three here and then by one here. I can move use different angles to reach any distance in between. There is code forces go for gold long contest in dream every month problems are fun there if so great are you into software development uh no I'm not really a software engineer or developer I want you to make my profile grandmaster how much I pay nothing I mean look if you pay me $1 million I will make your profile grandmaster but I can bet a lot of money that nobody would want that deal.

34:46 Uh I will I will not do it for any amount that any reasonable human would pay. Uh more problems on DP bit mask or DP3. Actually I have some plan for DP classes. Uh we'll see. So next what we will do next is this statement nice. No the statement is horrible. Skip token removing. I I want to read this because somebody was talking about it. So I'm going to read this. I don't know if I will solve it. And before that let me talk about one thing. Uh do you watch anyone on YouTube or Twitch perhaps for gaming? Yes, I I do. Uh I actually I don't watch Twitch at all. I do watch YouTube.

35:42 So for the let's say for entertainment for example most critical but also a lot of semi-educational stuff like Wendover production uh atriarch stuff sometimes about economics logistics a little bit of politics but only its effect on actually people I I don't like politics just to complain Uh C isn't that bad. Still I'm skipping. Okay. In a moment I will try this. Before that let me tell you about uh my plan for classes maybe starting in two weeks. So first of all if I have enough time to organize that and Huawei has enough time to approve this uh maybe there will be Huawei another Hawaii IO camp in second half of July. So let's say roughly July uh I don't know 17 to 22 just example dates. Uh as in the previous years this would be free for IOI participants.

36:58 We'll see if this happens. Uh so that's first thing. Second is I'm thinking about something like this and I want your feedback or ideas. I want to do paid group classes uh where it would go something like that. I think the target difficulty would be every week. So maybe this is first thing. Second thing, every week I choose 10 old division one B/C problems. uh inside of a discord group we vote on which ones to discuss and then you know 1.5 hour class with discussion of some of them no lectures no choosing particular topics just old problems on some chosen difficulty let's say this one this is division 2 D/ E the price I think would be this hundred euro per Uh I I think I don't want to go lower than that but this seems reasonable for people.

38:10 So every week there is a class and just after it you get 10 new problems to solve in a dis sorry in code forces group and in discord group uh in few days there is a vote on which pro or just discussion which problems we want to discuss in detail. So that would be a plan for this thing. Any suggestions for improvements of this in particular? If you want to take part, you can tell me uh what you think and what I should modify in this plan. So this is quite I think simple description, simple plan. I I see we're back to me taking tourist in a street fight.

39:07 But from now on, please stop repeating that. Uh I think you you can figure out yourself if you enjoy trying to solve problems of this difficulty. So if you can solve them quickly anyway, then you should enjoy. If you cannot even approach division 1B, then you shouldn't join. And for people in between, you can uh yeah, my my mail is public. It's this. You can find it on YouTube or Forces. Uh so far, I'm not accepting people to this. I'm just thinking about doing that. Uh, and also before the summer ends, I want to do maybe some shorter classes like I'm thinking two so two summer groups. So this summer for one month let's say in August uh one group would be solving just very difficult problems just very hard problems. I choose few problems we discuss it after a week and second is some kind of DP class for be starting from beginning. So I assume that you can compute n Fibonacci number in linear time and just go from

40:35 there for beginners. This would be two times per week. I think something like 250 euro price. So that's my plan. I wanted to share. Uh if you have ideas or feedback, tell me I ranked two in Google CodeJam. Yes, I did. I guess it's hard now to verify, right? Because Google CodeJam website died. But there is something called CP Hall of Fame. Uh there is this you can search for my nickname and you will see some of my achievements here. And in particular, this is my biggest individual achievement. I was second in Google Code.

41:40 There is even the my total prize money won through the years, but it only accounts for those contests. And I can tell you that actually it's around uh $30,000, not 4,000. But you can check this website if you want. Using GPT allowed to solve problems? I don't think so. At least not in most platforms. Uh, is this class only for high school IOI students? No. No. The first one is this is only for IOI. This one is open for everybody. My sound is slow today. But nothing nothing changed. I didn't update OBS. I didn't change my microphone.

42:28 So strange. Am I sitting differently? I want I will later check the recording. Balance work in development, day job and competive programming. It's this is a very personal question. It depends on how you spend your day. U right? Let's read the token removing problem. We'll see if I want to solve it. Breakfast skipped. Maybe this is why the sound is slow. How to be good at DP uh practice? No, I will not participate today. Also, maybe you can get good at DP by attending this class of mine that I will do in August. We'll see if I do it. I will announce in few days on code forces.

43:22 How can I be dreams like you? Medina, do not spam too many questions, please. just a little bit less or fewer. Okay, let's continue. Uh, define a sequence if a i smaller equal I. The weight of a sequence is token is placed at each integer point in the closed segment. Perform n operations. FA is this remove a token in the closed segment from AI to I. Uh FA is the number of ways to remove tokens. Two ways are considered different if if we do something else. Okay. I'm not a fan of the statement but somebody said mentioned the problem. So I would at least think for one minute but I think I will skip it.

44:34 So, what are we really looking at? Can I spin this a little bit? from zero to n for every index i. Let's say for i = 3 and then yellow will be i = 4 then red will be i = 5. For every index i, we choose some value a i smaller than that. So for examp let's say here a i equals 1 in yellow it will be a i equals I don't know three and so on and those are ranges there is a range from one to three one three there is a range from three to four there is a range from let's say two to five initially a token is placed at each integer point in the closed segment from one to n. So there is a token uh let's say that it is in green token square token token token and so on.

46:13 Then in order from one to n we remove a token one in the segment with of this color and we sometimes have different uh ways to do it because there are many tokens. So first here if the blue was first uh we would choose one of the green tokens within this blue segment. Then we do the same for yellow. Then we do the same for red and so on. We need to now consider all possible sequences. So all possible segments in particular AI can be zero. Then we do not do anything. There is no token. We need to sum the weight of what number of ways. We need to find the sum of the number of ways we can remove tokens for all the sequences.

47:20 Okay. Is this problem nice? Is it worth it for me to actually try to heavily understand it? I'm tempted to skip it, I think. language is very bad indeed it wasn't easy to understand the statement but it's it's not the choice of the problem outer of what they put in the story just that the idea for this problem is difficult the idea of what we what is asked of us best way to learn books are solving problems or both? Both. You should study sometimes and you should practice by solving problems.

48:16 Is this almost II level? It's not. Then would be I think easy II problem. Please solve. Okay, then I think we can do it. Uh just one more check. I will I want to make sure that top people didn't spend too much time. It can be solved in six minutes. I will try. I'm going to solve it maybe with the editorial. Let's try. So maybe 10 minute timer. This is how much time I'm giving myself to think about it without any hints. Uh oh, and let's do a small survey. Can you type your code forces rating in the chat? I'm actually curious what is the the range of that. So, can you type just a number? What is your code versus rating?

49:39 So, It goes to 200 something. I see that God gamer answered with rating of this problem. Okay. Uh Matt uh sorry but time out for now. I will ban you if you keep spamming so much. Okay. Uh then here's the thing. I want to try this problem if you recommend it. But I already made a similar mistake last time where actually I want to separate the difficulty of the two streams, the division two and division one. Tomorrow on Monday I'm going to stream again and I will start from this problem. Okay. So this problem I will do tomorrow.

50:45 I want to actually separate the easy and hard streams. So that today it's something that I want actual division to participants to follow along. So we're leaving this for later. Now something else there is division three contest here but we will not start from A. That's too easy. Let's take a look. If the statements are short I can try this one. I do not like. Let's try this. And then didn't I solve this? Okay, I did not. Okay, those two problems I'm going to do next. First, this tournament and then this one. I'm just using some heristic in my head to choose problems that seem nice.

51:58 Go to resources to learn recursion and backtracking. I don't remember anything that is particularly good. Okay. Tournament. You're given an array of integers AI. Uh there is a tournament with n players. While there are more than k players, two remaining players are chosen at random. Then the chosen player with the lower strength is eliminated. Okay. If two chos if the chosen players have the same strength, one is limited at random. Is there any way for player J to be one of the last? Okay. Remaining players. Okay. Those are queries. No, it's just a single thing.

52:52 So, you're given a particular player and you wonder if they can survive. Okay, there are a lot of players. We keep choosing two at random and we wonder if somebody can survive. That seems easy to analyze because if we have a sequence of strengths and there is one that we actually let's say it's sorted there is one that we care about there also can be ties. So there can be several equal values and then here there is smaller values. Then after this there are bigger values eight and so on. Now you want this one to survive as long as possible.

53:45 Wait, can't a player always survive because almost everybody else will die? Oh, okay. I I my my first idea was actually incorrect. I wanted to count smaller values and equal values different than you because you can beat everybody here and everybody here. But actually what can happen theoretically is that look at the maximum value say 100. This 100 can eliminate everybody here except for the player that we want to survive. So the 100 is going to eliminate those guys and those guys. And sometimes they can lose against the seven if it's actually equal. So there is a special case that the person we want to survive is equal to the maximum.

54:37 If so, everybody else can be eliminated. Otherwise n minus two always n minus two players can be eliminated. It seems okay. Let's go. So I only want to check if this is if this guy is equal to the maximum. Read this. Read the sequence. If a of j Now they number things from 1 to n but I want to number from 0 to n minus one hence j minus one. If this person is equal to the maximum then I can beat n minus one players. So basically I can always survive no matter what. No matter what the case even if case one I want to be one person remaining I can survive else if K is greater or equal to I think if at least two players we want surviving until the end it can be this player and the maximum so then print yes actually let's do it as a single if and else print. No

56:32 worked for the samples. So you mean only K equals 1 is special case? Equivalently? Yes. If k equals one, we want to be equal to the maximum. Uh otherwise I can always survive. I think that uh by racking if you're going uh will I end the stream before today's contest starts? Yes, I will. So I will stream for 30 minutes more. I think that this problem has a lot of potential to also be a hard problem if we analyze something else like what is the probability that somebody will survive until the end until Kk K players remaining stuff like that for low enough constraints might be solvable maybe even for the current constraints. So you're given this and do not print yes or no.

57:35 Print the probability of them surviving. I think that's quite interesting. And then some solution is to count the players who are weaker, equal and stronger. So three values. And in particular you can do it with three-dimensional DP but that's n cubic. And the question is whether it can be done faster. Yeah, interesting. Maybe it's solvable, maybe not. Uh, next problem. Next code. Do I code in Python? Yes, I do. Sometimes when I teach something at a very low not low level, that's that's not a good word. When I teach beginners, sometimes I do use Python instead of C++.

58:37 How many people win with probability greater equal 10%. Uh Gupta that seems very arbitrary and as somebody who created a lot of problems I can tell you usually problems do not look like that like for example count people with win greater equal than this 10%. in particular because of precision errors there is uh I don't want to go into detail but I'm answering to this comment uh I do not want to go into detail but most likely this exact statement would be extremely dangerous because a small precision error in a solution would cause the output to be completely wrong and the output here is integer. So I think that almost in any time complexity this version is unsolvable unless you do it with infinite precision. So you use big numbers which worsens the time complexity.

59:35 So as an interesting fact this is not something that I would even consider as a problem setter here. But computing probability for a single person. Sure. Also this almost obviously we should start by binary searching the person and then it boils down to the statement that I wanted to solve. Okay. Uh max count you could store percents as per int infractions. uh not necessarily int comma int maybe they will overflow int or overflow long sometimes it's a pair of big num comma big num so instead of software engineering I teach algorithms I teach am I still active on my main channel that is Ericto what maybe I will start doing from next week is those easier streams like today I will move to the main YouTube channel And regarding short videos, I don't know if I will get back to doing them. I understand that that would be very valuable to people. We'll see.

1:00:50 How do you level up your intuition and ad hoc skills? By solving those type of problems and maybe by solving logical puzzles and math problems. Max is the smallest integer not present in the array. For example, if you have 013, then the smallest not present is two. It's the smallest one missing. You're given an array. For every k, count the number of possible values of max after removing exactly k values from the array. Let's think.

1:01:48 Maybe this is better. Okay. If the array doesn't contain something small, so in particular, if it doesn't contain a zero, for example, it looks like this, then max is always zero even after you remove k numbers. So this is easy to handle. What is more tricky is if we have some zeros, maybe some ones, some twos, some and so on. Some numbers can appear out of times and maybe then uh some number is skipped like a five in range 0 to five. In this case, max is five. But if we remove a few values, then max can be something in range from 0 to four. For max to be for example three we need to remove all of this. Sorry we need to remove all of this.

1:02:49 If we can remove all of this then max can be up to three but and always it can be five because not not always. Uh it can be five that that's some kind of edge case. For it to be five, we need to remove this. I'm I think I said something stupid. Try speedrunning a contest with new fresh account. Why not speedrun a contest with my account? It would surprise the community. Too many people do it already. So I don't think they would be surprised. It's just like they treat it as another cheater or somebody's second account. So it's nothing new.

1:03:48 Max will be zero. Yeah. Yeah. I I I completely I said something very very stupid. No, max is zero if you remove this. Max is zero if you remove all zeros. So count of zeros needs to be smaller than or equal to than k. Then max is one. If you remove all ones and leave at least a single zero. So what does it mean? It means that K minus the count of ones. So this is after you first of all number of ones needs to be smaller equal than K because you want to remove all ones. And additionally after you remove all ones, you still need to remove some stuff. You want at least one zero to be alive.

1:04:58 No. Yes. Oh, I think we just need to say that the number of zeros is at least one and k= n special case. K= N max is always zero always K equals N means that we remove everything not max also here I wanted to say max. Uh now otherwise so if k is smaller than n max is one. If number of ones is smaller equal k so you can rem you can afford removing all of them and there is at least one zero. Then when max is two max is two. If you remove all twos and leave at least one one and at least one one zero one one. So following conditions number of twos is enough that you can remove all of them. You need to have at least a single zero, at least a single one and additionally you cannot be forced to remove them. So k needs to be smaller than equal to n minus two. I think this means that at least two numbers will be remaining. Oh yeah, let's think about it this way. Forget about all of this. Let's transform k

1:06:37 into n minus k. Now we want k values remaining. And let's think this is the same n k minus n minus k values remaining instead of k values being erased. And now let's think about that. We will choose just few values. And how can we achieve something? I claim max can be let's say x if every smaller value appears. So there are values 0 1 2 and so on up to x - one in the array. And additionally the number of remaining values k is greater than or equal to x - one or maybe I will say remaining and additionally we don't know any we don't want any x so I want to say erased number of values to be erased should be at least enough to remove all the occurrences of x. Okay, so forget about that.

1:07:51 This is the I think general condition. You want values up to x minus one to exist. Each of them should be there so that max could have a chance of being x because max is smallest one that is not there. So you want smaller ones to be there. Number of remaining values is enough that those exist or at least x because there is also also zero. So number of numbers in the highlighted part is actually X and the how many we want to erase needs to be at least enough to get rid of all the values equal to the max that is the target.

1:08:29 Uh am I calculating contribution of each max? Uh Gupta regarding your question for for now I didn't think too much about what I need to output and so on. I just wanted to understand I wanted in any time complexity other than exponential to figure out if some max is possible. Now I figured some conditions and I want to code it and now I will think about time complexity. So I would say no I didn't exactly calculate yes I guess now I will count contribution of each max but that's not how I thought about it for now I only understood the nature of the problem so that I could turn it in into anything.

1:09:21 Do I teach only by yourself or do you work somewhere too? Uh I teach by yourself and I work with companies. Sometimes I work with some university for example University of Warso. I teach I help coaching ICPC teams in University of Warso. Remaining values can be smaller ones too, right? You can have duplicate zeros. Yes, but I don't care. remaining different than x.

1:09:59 I think I like this condition. This says exactly the following. I can or those two in total. I want at least one occurrence of 01 and so on up to x minus one. At least one occurrence of each of those should remain. There are two highlighted conditions combined to that. Best book to improve greedy observation. I'm not sure if there exists such a book. Are we discussing only division three problems today? Uh well no but roughly on that difficulty. So like 1500 and so I guess uh so now let's copy this to the test case.

1:10:49 Now what are we actually doing? Read n for okay count the number of possible values of max. Uh I guess I want to iterate by max instead. I see. So there is some part that is still remaining and it's about this exact thing for now. Now during contest what I will type now is what I would do in my head or on paper. But roughly we want to do this for every max from zero to I think n + one. That's because max cannot be greater than that. If you have n values and you wonder what is smallest missing, it will be n plus one or smaller than that. For every such max, you have those conditions.

1:11:58 Uh that in my logic it was x. So let's do it like that. I want those values to be in the array. So if if x minus one not in a then I will do break because it's not worth continuing. Now this actually uh goes like that like not set count xus one here I'm turning a into the set. Yes, you can name the set with name set. Uh so this will make sure that smaller values indeed appear. And now I have those two conditions. I want the number of remaining values K. No uh erase. This is K. K greater than or equal to X. Oh, I need frequency. So actually frequency frequency of AI++ for every number I know how many times it appears because of that let's remove the set. I can just do this.

1:13:20 So if number xus one does not exist then break because from now on this max is no longer possible. For example, if you know that five does not appear in the input, then what it means is that max six, 7, 8 and so on impossible. This is what happened here because five will be the max or smaller. Okay. So we have this and remaining which is n minus k greater than or equal to x. Uh or in other words this transforms to k smaller than or equal to n minus x. Just simple transformation of this inequality. Uh let's do it like that.

1:14:13 So this is what we have. I know the frequency of x and I know this. Now I want low smaller equal k smaller equal high. Every such k gets plus one to the answer. So maybe for every k this is a brute force answer of k++

1:14:51 I went up to this. This can be negative. Does that make any sense? How can high be negative? That's suspicious. I don't think this is correct. Let me read the chat. Stream volume seems pretty low. I will check that after the stream. Comparing it with previous ones. Is this solvable if AI is up to 1 billion? Oh, I didn't see that. It's up to n. Yeah, it's just for values greater than n. values greater than n do not really contribute anything. They do not matter. So this wasn't this is not a very important bound I think.

1:15:41 Do you also use corman? I've read corman but I don't recommend it for to most competitive programmers should not read corman should not read it. Is this how long it you usually take you to solve division for E? No, I talk a lot here. So, this one not really. If you see me struggle and being if you see me being stuck on some problem and not having ideas, that translates to what happens during a contest. So, if you see me not having any ideas for 10 minutes, it means during a contest I would also not have any ideas for five to 10 minutes usually.

1:16:25 Uh I I'm not doing lead code problems today. Uh so I'm suspicious that for x= n +1 this becomes negative. So no k is possible. That that shouldn't be the case. k equals z should be possible. So this bound I think is wrong. How did I get it? I got it I think from here. remaining smaller greater than this. It means n minus k greater than equal to that. For k is zero. The number of remaining is n right? Max equal to this is impossible because the values start from zero. If you have values 0, one and so on up to n minus one, then the max is n. So actually the max of n plus one was impossible. Okay, I unnecessarily thought that something is wrong. I should have just finished coding and then start thinking. Usually it's not a good idea. Okay. Um so this is non- negative. This is also non- negative. So this will be fine.

1:17:44 Now this is right now a brute force. It's quadratic because of for loop inside the for loop. But let's see if it works for the samples and then I will speed it up. How much time do we have? Like 17 minutes before the contest today. K not declared N plus one. Okay successful. Uh, I guess I want to compare that using the command line. Oh, actually here's the nice comparison. Type one file. No, not this. Um, what did I want to do? I only am showing that to show how stupid and inefficient I am. Sometimes what I do is I run the program on some input. I then print the output that was copied and just with my eyes I see if there is any difference. And here it's easy to see that I'm doing this, I'm doing that. It's exactly the same.

1:19:02 Of course, what you should do instead is the diff command. So into compare with that. Uh here white spaces are shown. So I think minus B or minus W is the command to ignore that. I don't remember which one of the two. Uh maybe let's check. Which one was it? W or

1:19:40 ignore space change. Ignore all space. I guess they are the same almost. Uh okay. Anyway, submit. Oh, not do not submit. Time limit is exited is what I would get. No, I'm not participating today in the division one plus two. Why didn't you give Google interview? I didn't participate in Google interview because I didn't want to get to Google like if Google interview when you can create one at home. Okay. Uh so here when you want to add plus one to a range what you should do is prefix sums or some variation of it. So here actually I'm going to do answer assuming that this range is non empty answer of low++ and answer of high + one minus minus I'm not going to explain that but you can look up prefix sums this is some variation of it prefix sums and after I did this I while I iterate I want to add up to actually apply prefix sums if k answer of k plus equal answer of k minus one. So this puts + one

1:20:56 somewhere negative one somewhere else and it will propagate automatically later on in linear time. Okay, it works. How is doing nowadays? I think he's fine though. He messed up the potki contest a month ago. Okay, accept it. I think that difference arrays. Uh yeah, Ali, I think we can call it that. I always think about it as prefix sams, but you're right that we apply difference array. What is my profession? I teach algorithms on Twitch. There are a few comments, few very old commands. for example this one job and it should be mostly up to date though I created those comments maybe five years ago and for few years I did not really stream much this should mostly be okay uh so what there is code forces around in 12 minutes should we try one more problem something that will take five minutes at No. Too long statement.

1:22:25 Nope. Nope. Nope. Likely to heart, but I will read. on YouTube the comments do not work. Yeah, thank you Pranai for nice work for nice words. Yeah, see you Ali. Everybody please remember to participate in the code forces round. For two integers we define f of a comma b as the number of positions where their digits are the same. You're given two integers LR of the same length. Find the minimum value this. So you want to find number in between that differs as much as possible from both of those. Then this is actually this I think is very simple.

1:23:48 Okay, it's very standard not simple. Simple is a bad word. Uh you can do it with DP. I'm not sure if you can iterate the common prefix at next digit. Maybe I think this will have two solutions. So when you have some number like let's say the r here is equal to sorry b is equal to let's say this and a is also equal to something and maybe with a common prefix 71 2 one something too long usually you can go with dp where you have the current digit or maybe the position of what you're looking at right now let's say here and information about what digits you chose so far and that boils down to am I already greater than a boolean information greater than a and am I already smaller than b uh and this will be int dp uh min possible f plus f the the thing that we minimize if you do not know digit dp what I'm talking about here does not make any sense But it's impossible to teach digit DP in five minutes.

1:25:09 Still this is one possibility where for every new position you just iterate what will be the digit you put there and with some simple logic you will uh update those two values. So this is in DP of the length. So nine or 10 by 2 by two. This is the DP we do. I think also what we can do is instead of DP we can iterate the number that we will use how long common prefix it has with a or with b and what will be the next digit for example if you have this b one possibility is that I want to use the same first four digits seven one two three and then the next digit will be let's say four then the trick is that no matter what you do Here the number will be smaller than b and it will be greater than a automatically.

1:26:03 So here I will say that I will always choose digits that let's see minimize that coincide with those if possible. So if there is six here I will put six. If there is seven here in both numbers I will do this. So basically you just copy this 671. I will copy 671. So I'm going to do this for iterate length of common prefix with B the number that you're creating iterate for how many first digits it is the same with B then inside of the for loop another for loop iterate next digit then all remaining digits copy from B from the suffix of Then what you do here is check if new number if a smaller equal obtained number smaller equal b let's say then you do the same with a do the same with a because maybe you will have a very long common prefix with a then another digit then you copy from a or from b that one actually does not matter.

1:27:24 that will be a solution that does not involve DP and I think many people do not know about this style of solving such problems. They go for DP immediately and that's almost always uglier implementation. Now I will not do the round in few minutes. I wonder if the editorial talks about something easier. Well, the tutorial is long, but it talks about something greedy. So, it's certainly not DP. Yeah. Yeah. It's simple. Actually, it's simpler than what I described. I think it's more of it looks at when the numbers differ and it does something with that.

1:28:13 But what I described I think is better because it works for many many problems. I should join Google or Facebook. Look, if you have such a dilemma, then you're you have a very nice situation. I do not know if you should join Google or Facebook. Depends on the offer and your personal situation. Maybe one of in one you already know who you will work with and you like that person. If so, that's a strong argument. Yeah, there is a contest in five minutes. I will not attend. Please everybody register if you want to participate.

1:28:57 I will finish the stream now. Maybe I will talk with you for two more minutes. How to practice for people with rating smaller than thousand. Go through some course about programming. So like you know if you search for C++ course online free just try any of those and once you think that you your implementation skill is enough solve those 800 rated problems a lot of them often the solution will be five lines of code still solve a lot of them if you think that you struggle with that take a step back and solve some math problems grab a book with math problems for let's say middle school maybe high school and solve those will top coder resume contests I don't think so how to get master from candidate masters same as any gap practice you know I mean I I've once written down this you can go read that how do you break through competitive programming plateau uh have a break of few days or weeks then

1:30:13 then maybe go back to it. Struggle with edge cases well be more careful with n equal to one that that is like oneird of the test of the edge cases. All right. Uh that I think this is everything for today. Tomorrow I will do division one stream. I will start with this problem uh the token removing because it was recommended to me. I will try it. So this thing um there is I think still the wait did did I make the calendar or schedule comment? Yeah I see you ga still not anyway on code forces after the contest today there will be countdown to my stream tomorrow I will not make it one because I don't want to bother people who are participating in the contest today.

1:31:09 Uh and in few days I will on code forces announce my classes for August and following months paid classes if you want to join that stack overflow error of brain while solving problems maybe don't do not try to do things recursively not sure okay good luck everybody in the competition I wish you all the best solve a lot of problems gain some ratings Maybe exactly thanks to what you've just seen today. I don't know. Uh so Matt, you really want a bun, don't you? Okay. See you

Questions about this episode

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

In order: 10:00 AtCoder; 30:00 YouTube, Huawei, CodeChef, Twitch; 40:00 Google LLC, Google CodeJam, CP Hall of Fame; 1:00:00 YouTube, ICPC, University of Warsaw; 1:10:00 Google LLC; 1:20:00 YouTube, Google LLC, Facebook, Twitch.

What is mentioned in this Errichto Hard Algorithms episode?

13 people, works and ideas are mentioned, including Codeforces, AtCoder, Google CodeJam, YouTube, Huawei, Google LLC. 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 32 min; the transcript is about 10,286 words in 83 timestamped sections.

More from Errichto Hard Algorithms

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