ABC 413 | algorithms problem-solving

What is discussed, and when

1. 0:00 – 15:00: AtCoder, Huawei II camp 2025
2. 2:15:00 – 2:30:00: AtCoder

Notable quotes from "ABC 413 | algorithms problem-solving"

• At coder beginner problems. So easier stream than yesterday. Yesterday we tried the atcoder regular and those problems well some of them were challenging.

  about AtCoder · at 7:10

Who and what is mentioned in this episode?

People

• Baghdad Bob — Person · 5 mentions

Companies & orgs

• AtCoder — Company · 4 mentions · first at 7:16
• Codeforces — Company · 2 mentions

Concepts & topics

• CSS — Concept · 3 mentions
• IOI — Concept · 2 mentions
• Huawei II camp 2025 — Concept · 1 mention · first at 7:43
  A shooter devil. Hi, the registration for the IOI camp is on for the Huawei II camp 2025, the link is on code forces, but it's only for IOI participants.

Full transcript with timestamps

6:52 sound test. Uh we're doing at coder problems today. at coder beginner problems. So easier stream than yesterday. Yesterday we tried the atcoder regular and those problems well some of them were challenging.

7:30 Hi decoy a shooter devil. Hi, the registration for the IOI camp is on for the Huawei II camp 2025, the link is on code forces, but it's only for IOI participants. Okay. So, if you're going to II and you want to practice a little bit just before the going to the contest for one week or for less, if you cannot participate in all the contests, then consider joining. Yes, I do use virtual machine

8:19 and not this. Whenever I whenever I type at coder into the browser, the first thing that pops up is the atcoder dp contest because I use it a lot. I refer to it a lot when people ask me about stuff or when I recommend the DP problems to people. It's very good set of DP problems. This thing, if you're interested, it's this. I once did a live stream solving this. Um, okay. What we want is from recent contests we want atcoder beginner contest then this one sounds good at coder beginners beginner 413. I wonder if maybe I should go from oldest sometimes, not from newest because the first eder pro contest that were held in English, they are of very nice quality I think because they used more of standard problems, short statement standard problems. You can argue if it's valuable or not. For somebody very experienced, it's maybe more boring, but for the sake of educational content, I think it's very

9:31 good. Uh, so let's try this maybe. Here's the link commands. Hi cosmic boy. We have n items and one bag. The size of item I is AI and this is size of the bag. We wonder if we can put all the bags in the all the items in the bag. Okay. I I think that this is not a very interesting problem among the easy ones though maybe this is exactly how easy problems should look like. So we check if the sum of those values fits in M just the straightforward check if you know how to do for loops optionally arrays but you don't really need an array here. Do we have test cases? No.

10:48 an M and then read the values. Now I could read them into an array but instead I'm going to just as I go read a single value add it to the sum and print if sum smaller equal m then uh what do we print? Yes. else. No, old old contests aren't translated. I'm talking about the oldest contest that is translated. But you're right. I think the very oldest contests are not translated and then I would skip those unless I get information that they are of such high quality that it's worth using some translator. though then again I don't think it's is very convenient for the stream where you're supposed to learn something and the the problems I want the problems to be easy to understand for somebody who joins the stream hi Chandu what's my day job no I I consider eventually doing software engineering but right now my job is, let's say, teaching.

12:16 I don't have a full-time job. I do a lot of smaller things. Okay, the second task. We are all LJMs here. I guess it's a little bit like if there is some kind of disaster, let's say there is disaster in France, let's say, and then everybody in the news, politicians will say we are all French today. So did some kind of disaster happen to LGMs. Today we're all LGMs by heart. Distributed systems engineer job with CPP.

13:15 I mean, so Chand is that a recommendation for what job I should consider? I don't know anything about that. Researching algorithms. Yes, I considered that. But like it's it's not absurd for me to do something like that. That being said, I went into different direction. Uh n types of strings. N types of strings or n strings. Why? Why is n types of strings? I think it's just a translation error. Just n strings. Uh you perform the following operation once. Choose distinct integers i and j and concatenate. So glue together combine assign and sj in this order. How many different strings can be obtained as a result of this operation?

14:08 Uh and n is small enough that we can do all the pairs I think I think this should be interest should be solvable even if n is big right 100,000 while I solve it I will think about it but here they so still this is just about the brute force where we uh this time let's read the strings s of n. Now for every pair except for the equal pairs. So only if I not j here we consider a string s of i plus s of j. If you want to know how many distinct strings can be obtained the easiest possibility is to insert them into a set. Yes, a set can be named set, though I don't think it's very recommended. At the end, you can print the size of the set. Now, that being said, I usually wouldn't do things this way, and I will test on the sample test, but in a moment, I will explain why this is not perfect really what I did uh a on in 11. Okay, let's submit.

15:27 So this is I think here good enough but far from optimal. It's so annoying that after verify your human I need to wait for full second or something like that otherwise I get an error. So set is a very slow data structure. uh instead if you want to count number of distinct elements. What is faster if you care about the runtime is for example putting them in a vector sorting and removing duplicates and the time complexity is the same because this thing what what we have is O of N squar that is the number of strings N² time length of a single string time log of N². So basically log of n uh as this is time complexity of the set the extra logarith log of n and log of n squared is the same thing in terms of time complexity.

16:28 So we have this and this should be small it's small enough because n is 100 length is 10. So this is like 1 million operations maybe even less than that. Well 1 million roughly. Uh that being said, this the code would be faster if I instead did vector here vector push back uh then sort and resize after removing duplicates. Now this is a very strange command in C++. You can look up how to remove duplicates in C++ vector. But this should be faster than the set solution. I will submit it. Uh though likely we will not see a difference in the verdict because still the constraints are so low that it's negligible. It will be you know a difference of milliseconds. That being said, if you care about the runtime of your program, so you're afraid that maybe your time complexity is not enough. It will be close to the time limit, then this is faster. Then even faster will be not collecting strings but their hashes. So creating

17:44 for example vector of uh integers uh for example vector of longs after hashing the strings. And finally, I think that most likely we can avoid the double for loop. How would we do that? Well, if there is a repetition, there needs to be one string. Let's say ABCDE E and then another string F GH and then let's say ABC and another string D F GH. So we're talking about the string where it's shorter prefix exists as well and then another string where its shorter suffix exists and those two this guy and this one they need to have a common part.

18:52 So for the longer string for every prefix of it that also exists in the input and we can check that with hashes we mark oh if something starts with this prefix also we mark that as a hash uh mark it as something special and then for this other string when you get here after the e you know that this was something special. So the remaining suffix hash of it check if it exists uh in the input and if so something happens. Now what does it mean something happens? Do we subtract one? We would need to be careful what to do about multiple repetitions of the same concatenated string like this. But I think it's doable.

19:42 Is that your dog sleeping behind you? Yes. Uh that's the dog. Do I use other programming languages or only C++? I use a little bit of Python, Java. Do you feel teaching is boring as it gets repet repetitive? No, actually I don't think so. So what I'm doing for example today it's not exactly teaching I solve problems while explaining negligible difference this thing it's really just a variance in so one millisecond of difference is nothing in those um judging platforms you send hello world and it can show you one millisecond or five milliseconds lead code or code forces in the beginning I guess lead code unless you know that you want to focus on competitive programming.

20:41 Uh, hi Viking. Okay. So, this is possible without N squared, but the the organizers here did not require it. Yeah. regarding the teaching is boring. I still did not cover all the topics out there and in particular if I ever feel bored or something like that, I still know that I could go and cover like hundreds more algorithms on YouTube, right? And I haven't done that yet. So, no, it's not boring. 25% speed up. Well, maybe if we send the same code again, we will get two milliseconds. U there is an empty integer sequence.

21:32 Oh, also one more thing for easy problems. So for example when I work with beginners or with let's say high school kids or middle school something like that uh well kids students I don't like giving them such formal statements like choose distinct integers inj I would then phrase the problem as uh you're given a lot of strings count how many strings can be obtained by taking two of the strings from the input and concatenating so gluing them together. I hate this phrasing of at coder for beginners in advanced problems in hard problems. Sure, formal statement is perfectly fine.

22:16 Solving CSS on stream, I think that makes sense. Also, we have messenger. I need to close some tabs. One moment, right? Uh what was I saying? Oh, CSS. Yeah. Uh the CSS problem set uh got expanded and now there are many more problems. I guess it's something like it was 100 and now it's 200. Well, we can count that or estimate. How do I want to count it? I can count lines, right? Well, every problem comes with a uh with this character, the division. Will this tell me? No, it doesn't tell me. Well, from line 30 to line Oops.

23:38 Wow. Is it 400 problems now? CSS is now 400 problems. That's a lot. Was 300. Now 400. Okay, that's a little bit overwhelming. Still it's good. I often recommend CSS problems to people. I think it's good problem set with some drawbacks. Uh so you will have hard time using anything other than C++. Java and Python. Some problems are close to unsolvable and usually there is no example explanation which is bad. Generally example explanation is good because if somebody isn't sure about the statement they will go there and if they are sure about the statement they will ignore it.

24:30 So it's only a good thing. Well, maybe I will do streams for some topics like intro problems, DP. Um, and what else? Geometry. I recall that somebody told me that my old code for one of the geometry problems does not work. I have that in my GitHub repository. So even more it makes sense to do the geometry problems and hardc well that's also some idea though I think I would skip some problems by hard you mean advanced no just additional problems some of those are about knowledge and I would prefer not to do them we'll interactive problems too. Is there a category? Yes, there is.

25:40 We'll see. We'll see. My plan for the following weeks by the way is that in the second half of in second half of July. So this uh there is the the IOI camp then in August there will be paid uh dynamic programming classes. I will in few days post about it on code forces. I mentioned about it during some of the streams in the last days. There will be two two groups. The easy group, hard group, easy about solving problem solving easy problems like NAPSAC. Hard group about learning hard techniques like DP optimizations and practicing hard DP problems.

26:32 Uh and then what in September I have some on-site contest and stuff like that. So I will have some trips but also I want to start here regular weekly classes weekly classes on again two different levels. We'll see. So s I think in July I will not start anything new like you know a series of CSS streams maybe in August we'll see uh good intro to types of problems in at coder what is that

27:23 so this is an explanation at cutter problems difficult ulty how it translates to ABC and so on. Uh how many what percentage of people solve it? I guess can you summarize it for me? Math background. So formal statements feel rigorous to me. I mean okay but not everybody is from math background. Okay. Next task, large Q. There's an empty integer sequence. You are given Q queries. You need to process them in the given order. Two types. Uh add C copies of X to the end of A. So append X C times. Remove the first K elements and output the sum of the removed K integers.

28:30 Okay, that's I think that's a reasonable easy data structure/ algorithm exercise. So normally if you keep adding elements for example you have new element three new element five 7 10 15 and so on and you remove elements from the beginning like initially the three then five and so on and you need to report about them. The name of a data structure for that is a Q. But here we can possibly add 1 billion copies of something. So obviously we cannot insert 1 billion occurrences of 3,000. But we can insert the value three with a count like let's say 1,00 times I inserted three. So this time it will be a Q or similar data structure of pairs with the value itself and the number of repetitions how many times it was inserted maybe. Then after that 11 was was inserted once. It is possible that twice in a row we will have the same value like here 11 is appears once and then 11 appears five more times. you don't

29:43 really need to collapse it because you don't need to detect that something can be compressed. You don't care as long as you're able to take elements from the front. And now if somebody wants me to uh take five elements from the front, I know that there are at least five elements free. So I compute what is the sum and then I decrease this by five. If now somebody wants 1,000 elements from the front, I will take those 995 elements and some more from here. The whole time I was talking about a Q that being set in program in competitive programming, almost everybody uses a vector for that because it's very convenient. It has indices and it's generally fast. In particular, remember this in C++ in competitive programming, do not use deck q or deck deq uh because it's for some reason very slow. You don't want to use it. It's just a terrible constant factor.

30:48 Okay. Um, so we have Q events. Repeat Q times. Uh, read the type of the event. If type is one, then we need to insert something new at the end. I will have a vector of pairs. Call this V or actually yeah call it V. Uh read C read X V push back and place back is like push back for pairs. It's a little bit better to use it. I want to insert value X C times. It's a pair of value comma frequency or number of copies. else the type is apparently two we can even check that if it's not true then I will see this assert failing and it means that I'm reading the input incorrectly read the value K and I want to grab K elements from the front while K exists I want to take the first element in V and now normally you will take V of zero but in a vector I said that I use vectors instead of Q. That being said, in a vector erasing the first element is slow. If you try to do V erase V begin, you you shouldn't do it a lot of times

32:28 because this is linear operation. You will get time limit exceeded because you will get in total quadratic solution N squ or Q ^2. What instead I do and again most of people do it this way. Uh he unfortunately al also uses the key. What are you sure Jiren? Because I think I used the I used Q in the past. So this would be big news for me. Let me ask my friends in some group conversation.

33:44 Okay, I asked uh deu or deck is not super slow but it uses lots of memory. Well, using lots of memory also means that it affects runtime. Using n operations or running n operations is normally way faster than allocating n units of memory and doing something with it. Interesting. So we will maybe in few minutes get the answer from some of my friends. of should we also avoid a Q in C++ in competitive programming? Anyway, I'm using a vector and to quickly erase things from the start, I will use an extra index of the start and when you want to do uh operation of erasing the first element, I will just increase the start index by one.

34:47 So here I will refer to v of start and if I need to remove the first element I will do start plus+. So what we are doing here is if um v of start dot uh second so frequency if it's smaller or equal than k then remove this full pair. So start ++ at first uh it's K minus equal that this is the case where I want to remove 100 first elements but V of start is let's say element three repeated 90 times 90 is smaller equal 100 so I want to say that those 90 elements are all erased I also need to collect the answer the sum of elements call it sum So here sum plus equal I need to add to the sum 90 elements equal to three. So casted too long long v of start second times v of start first counts times the value otherwise so if this is the case is 100 but v start let's say is element repeated 130 times I want to only take 100 repetitions of it. So the sum increases by k times the value and v of start second decrease by k. So from 130

36:18 elements you will take 100 of them 30 will remain at the end print or output the sum. Out of bounds assert starts smaller than V. Size failed. So I'm running out of the vector ring buffer with global row array is faster than Q. Well, that makes sense. Generally arrays are crazy fast. And if you want to operate with one big data structure, then actually array is faster than a vector. Vector also uses pushbacks. So big static array is faster than a data structure where you insert elements and it possibly gets to that size.

37:41 Why Jiren watches it's super easy for you. I I think I also watched easy stuff in the past or I solved easy problems. Just uh I don't think there's anything wrong with that. I actually think that it makes a little bit more sense than people who tell tell me during streams that they understand nothing but it's fun to watch or something like that. Well, I'm not sure if I would want to understand something where I understand nothing but it's your choice. Okay, so this must might be caused by uh some kind of logical error.

38:30 Let's read the code once also. Let's make sure that I'm properly reading that. Here we have three elements. So what's the order? See copies. The first is the count. We insert two times, four times, six times. In total that's 12 and we erase three and then five.

39:04 Okay. Greater than zero. You are inside of the bounds. If the frequency doesn't exceed K then you want to remove it. But first update the sum. This one doesn't matter. This operation cannot affect the error that I'm getting. The error of going out of the array. This is important. Okay. Decrease by that frequency. Okay. else uh increase the sum whatever and then this element gets decreased by that oh and k becomes zero right because here you're out of k you don't want to continue alternatively you could do a break here 11 and 19 works during a contest you might want to also run your solution locally for the other samples to avoid getting time limit exceeded and a time penalty because of that.

40:18 Accepted make geometric sequence. A bit longer statement. You're given an integer sequence A. Uh the values are not zero. Check if there is a permutation of A such that B forms a geometric sequence. So can we reorder the given elements? So it would be geometric sequence. Then it needs to be increasing or decreasing right. So should I we just sort it increasingly? Oh the values can be negative. I see. So we might have sequence one -2 positive48 positive 16 and so on. uh it could also be decreasing but I think then still it's sorted if we ignore the signs so maybe why this solution isn't time exceeded which solution oh you mean the previous one uh this one so briefly every element you will erase only once so it seems that you have for loop inside the for loop but this cannot happen that many times in total because you move only forward. So if there is some object that you insert, you will eventually erase it

41:53 once. In total, n objects will be erased. So it's amortized time complexity like in two pointers. It's kind of a two-pointer solution. Uh I think here we need to sort by the absolute value of the element. So we will ignore the signs for that. I had a OA. What is OA for MSFT today? Bombed the question. I mean, yeah, if you want to improve problem solving abilities, you need to practice code forces for competitive programming, lead code for interviews, online assessment. I see. I don't think tech lover that I will get R because R is a real value. So I would prefer to avoid that. But yeah, I'm going to here sort by the absolute value and this time we have test cases.

43:04 This line is an alternative way of typing repeated times. Okay, we want to sort given two elements X and Y. I want to sort by the absolute value of them. This is how you sort with custom comparator. Now what I could theoretically do is this. Take a of 1 divided by a of 0. This is some kind of ratio. The values are not zero. So this will not divide by zero. And is at least two. So we have at least two values. And I could now verify if the ratio works for all of the following values. But using double is not really perfect later. What I will want to do anyway. So not perfect because of real values. So precision errors. I can get the wrong answer after comparing this to ratios of other integers other ratios other divisions. Instead later I would anyway check this if a of i + 1 divided by a of i is equal to this.

44:31 So I'm checking basically this equation and here I can transform it to avoid the division. I don't even store here r as a fraction. I just transform equation and I will directly check it. I never I will never store the ratio though I could. If I multiply both sides by a of zero and a of i then I will obtain this and I'm going to check that for every i. Exactly this. Be careful when if this was inequality like that then multiplying by multiplying by both sides is dangerous if you deal with negative values that could change the sign. But here it's just equality. So I'm going to check this without caring about what the ratio is.

45:30 If a of one uh long longs otherwise overflow is what I would get. If this then it's good and if not this then this is bad. What do we output? No. And return. I don't want to output no multiple times if nothing happened. Yes.

46:14 No. No. No. That's not good. Uh maybe I messed something up again. A of 1 / a of 0 is equal to a of i + 1 / a of i. So a of 1* a of i. Yeah. It's the other way around. Yes. No. Yes. That works. F is the only interesting problem of this contest. Uh I think millant that for example here the fact that we should avoid real values and instead we can transform the equation is also something that I want to encounter and explain during my streams. And I wonder what I messed up. Can I get some more information? Free accepted. A lot of frank answer.

47:26 Interesting. Maybe it's not enough to sort like I'm sorting. What if all values are equal by the absolute value? So uh 5g5 5g5 5g5. I need to do them exactly in this order and not at random. So I think the counter test would be like this. If I have 10 values and those are one one one negative 1gative 1 negative 1 negative 1 and so on. My program says no, but the answer should be yes. The answer should be yes because I can put every second number as positive and every second as negative. We can either fix the sorting or we can do a special check here.

48:31 If absolute value of the first element is equal absolute value of the last uh sure that's why I enjoy your streams. Yeah. So I mean I I agree that this is not an interesting problem to somebody experienced. So in particular I wouldn't do it if I only practiced to improve. But I'm doing this stream so that you watchers viewers would improve. uh if this is the case then it means everything as I sorted increasingly by the absolute value if still the first and last absolute value are the same it means everything is equal I need to check if I can rearrange them positive negative ne and so on or negative positive and so on instead of actually arranging them like that I'm going to just check if it's possible by counting positive and negative uh neg is zero pos is zero for every element.

49:32 Uh if x greater than zero then positive plus+ else negative. Now if either the difference between them is at most one. So for example you have five positive values and four negative then you can arrange them like that. But also if positive is zero or negative is zero. So you have just all equal values. In all those cases, you output yes and you stop should work. I think otherwise we can hear stop but it's not needed. Let this check go. Anyway, it doesn't hurt that later we will check if in my sorted order the ratio is the same. The logic should just not detect that.

50:22 Hence, I didn't do the else here in this place. But I think I could in this place I think I could do else see out. No. Hi Ash. I accept it. Okay. Uh let's move on. I think one negative one one and so on. Why? Why do you think this would be wrong answer? Because this if will not be applied. So I will sort them in order of ones to 200 222 and then this will be detected as false. So I think everything is fine. Okay. Uh problem E. You're given a permutation of size two at power something. These trims help a lot. Thank you.

51:37 You're welcome. though I wonder if the format is optimal because it's not that really I spend a lot of time on every problem. I solve it and I move on, right? Maybe instead I should after solving a problem always I could do a summary like in five minutes present it with drawings stuff like that. Well, not sure. Instead, I think it's more that you're getting collection of small pieces of advice. Yes, competitive programming will exist after AGI like a lot of other hobbies. though it can be smaller and less important. So you have permutation of numbers from one to two at power n.

52:29 You repeat the following operation. Choose two integers satisfying this. This inequality is strange. What? How can this be not true? Why didn't just they said this? A * 2^ b is smaller than a + 1 * 2^ b. If the integers are non negative, then this is automatically true, right? Because this is at least one. What? And also this is automatically true. Why did they say this? Choose two non- negative integers AB. So zero or more then obviously this inequality is satisfied and this inequality is satisfied.

53:43 Strange. You only check if the numbers are all the same. That that was part of my code. I check that here if all the numbers are the same by the absolute value. But then there was that standard check that I did first of comparing the ratios. Okay, back here. Uh so I will just focus on this inequality. a + 1 * 2 at power b doesn't exceed 2^ n and then we reverse this range from here to here. So like a range of size two at power something reverse. Find the lexographically smallest permutation p that can be obtained by repeating the operation.

54:45 Oops. and B are not indices can be greater than N2. Yeah. And this is why I understand this inequality. This one, this is something we need to check. But I don't know why we have those two inequalities because what I'm highlighting now should be true anyway for any two non- negative in integers a and b and it doesn't depend on n because in highlighted part there is no n

55:39 If B is zero and then this is one. It's just to show that it is always a subar of the permutation. Yeah. But I find this confusing. And now if B is zero then we are reversing a range from A to A. I think so. What if B is one? Then it's a range from 2 a to 2 * a + 2 - 1 I think 2 * a + 1 if b is three we are reversing a range from four * a to 4 * a + 3 I'm guessing so this can reverse any two consecutive values four consecutive values val but only in blocks of four. It seems that if I have a long sequence, I can reverse the first four elements. I can reverse the next four elements, I can reverse, I'm guessing, the first eight elements. I can reverse the first two elements or the next two elements, the next two elements, and so on. And they're asking what is the smallest permutation I I can obtain. Well, the smallest value ever will go to the front.

57:37 Or maybe I will think like that. I will solve it recursively. So I will think about the first half of the array and the second half of the array. each of them solve optimally and then you wonder if we should reverse the whole thing like if okay let's work with eight elements say that we have eight elements I run recursively on the first four and I will obtain some optimal order let's say this I run on the second four and I obtain optimal order. Now I want to I wonder if now I can reverse the whole eight elements. However I want to do it depends on what is the smallest element among C versus E. They are distinct because initial numbers are distinct. Let's say that E is smaller than C. Then what I want to obtain is first this and then that.

58:46 I can always obtain that because I reverse the whole thing and then again reverse those four elements and those four elements. For example, for example, let's say that the sequence is 2 1 no uh 3 4 2 1 running recursively here, I obtain that the smallest I can obtain is 3, 4. for this smallest I can obtain is one comma two. Now I compare those two elements or pairs of elements and I see one is smaller than three. So I want to move it to the front and I think about reversing all the four elements. By reversing I would get two one four and three. But I know that each of those can be reversed back to its own optimal form. So actually I will get one two three four.

59:50 Which means that really when looking at those two optimal orders for each of these pair internally, I just choose the smaller of the pairs to be first. And that should happen in general, which is oops read n. Then you have a sequence of size two at power n read all the values. You don't need to iterate index. You can also do it like that. And then solve recursively. Passing a copy of a vector like this is not really very fast, but it's it will be good enough. Here 2^ 18 multiplied by logarithms. Even with big constant factor it's it's fine.

1:00:51 If size is one then you don't need to do anything and otherwise you have the left half and the right half. left half, right half. When you create a vector, you can provide the iterators of start and end solve recursively. Actually, you don't need to return if you pass by reference and it will be automatically faster. Uh so solve recursively L solve recursively. Right? Now if L of 0 is smaller than R of zero and those elements are distinct then you want to copy L plus R otherwise you want to copy R plus L. Let's say what I will do is in this case I will swap them and then no matter what I want to return L+ R.

1:02:06 Uh you can do it like that. L insert at the end everything from R begin to R end and uh A is L. By the way, when reading the statement I before I finished reading the statement I guessed what it will be about that it will be blocks of size power of two like first four next four and so on. It seemed not really obvious but it seemed intuitive that this is what they will really mean with those operations that are possible.

1:02:58 Okay. One two 1324. Oh, that's incorrect. That is incorrect. Oh, it's correct. I was looking at the input instead of output. 1 4 2 3 and so on. Seems good. What about 2 3 4 1 2 3 4 1. Well, I will solve this half optimally 2 three. This half optimally 14. And then I can put four be before 2 three. So I claim that this is optimal.

1:03:46 And regarding the previous comment from Jawin, I think I would if I wrote this statement, I would leave only this inequality because only this means that we are inside of the two power n range. If you want to convey that it's a range that fully fits from zero to something, then just say it. Okay, let's submit.

1:04:33 I wonder if uh for people working on AIS for including open AI if this is the button specifically for them so they wouldn't spam so much training their solutions actually do you think that companies like OpenAI they will have a deal or they have a deal with at coder or code forces to have direct access to the tests. Maybe not. Is that easier for Well, they have a lot of computational power. So maybe they would prefer to run things on site also. Um code forces I saw an announcement that there is at coder heristic contest soon. I think it's for the finals in Japan.

1:05:31 at coder. I lost it. Uh so I think people are going to Japan for the on sites and there will be heristic contest optimization contest with a stream of human versus AI. I wonder what this will be about.

1:05:56 Okay, next task. No passage. Somebody said that this it's the only interesting problem in this contest. Could you briefly explain how you quickly figure out that problems like this are divide and concurrent, not something else?

1:06:26 It's a tricky question what you're asking. How did I know that it's divide and conquer? Well, I did some I first understood the process. I understood what they are saying that it boils down to the fact that I can swap those two this pair, this pair, this pair and so on. So initially I didn't know that it's divide and conquer but I visualized what I can do. Then I would argue that this visualization already looks like divide and conquer or like a segment tree right because we we have the full thing and halves and so on.

1:07:09 And then I knew that for every pair here I can put them in whatever order I want. This thing this thing also. And now I thought how the first and second pairs will interact with each other. And I figured out eventually that yeah we can just the smaller of those two pairs will be first. And just the fact that a half interacts with other half to create a bigger part. This is how divide and conquer works. To be honest, when I said recursion, I didn't even think divide and conquer in my head. Yes, it happens to be divide and conquer, but recursion just was for me the easiest way to implement my thoughts.

1:07:59 How would we solve for any range? I mean, if we can do any range, then we would just sort the sequence, right? Because for B equal to zero what you provided is any range. I mean if you can always sort two neighbors if you can swap two neighbors then you will sort the whole sequence. If every if in particular you can swap this. Okay. Now onward to problem F.

1:08:42 Long statement, but somebody said it's worth it. There is a grid. K cells are goals or targets. The two players play a game and a single piece on the grid. We perform the following series of operations until the piece reaches the one of the targets. Alkey chooses an integer from one to four. Then Takahashi chooses an integer from one to four but a different one. Let J be the current position. Then we move the piece. Okay. So that was direction. Ai chooses the d one of four directions and Takahashi needs to choose a different direction and moves there. It seems that this is what everything boils down to.

1:09:54 So Aki chooses one direction that will be forbidden for Takahashi. I will call them Alice and Bob. for Bob. Bob chooses one of three remaining directions. But if he chooses a direction that moves the piece outside of the grid, then nothing happens. Bob's objective is to minimize the number of moves until we reach one of the targets. A key to pre to prevent that from happening. And Ali is apparently a man because it says his. So Alice was not really perfect choice for me for the name. For all pairs of integers, solve the following problem.

1:10:48 Find the sum. Okay. Uh it will it be some kind of DP? How to be focused? How to be focused? You can write one question and wait for the answer. I guess that's more about being patient, but it's related. I don't know how to be focused. If I think if we search in Google for how to be focused, you will get a lot of results. In particular, for example, don't watch Tik Tok. I think this is what destroys the attention span. So also it makes it harder to focus for a long time. Is bit manipulation important for combative programming in interviews?

1:11:34 Yes, a little bit. Like many other topics. Had a meeting recently and two people had names Alice and Bob. Did they like each other? Is there a chance that they will form a relationship? If so, they need to name their kids also in some alphabetical order like you know Charlie, Derek, Eve, Alison. Uh okay, this seems to be some simple DP. I I don't know if there will be any kind of analysis here is well DP but we cannot do things in order from top left because we don't know optimal order of movement here but if there I need a drawing for that

1:12:44 maybe If there is the target somewhere, this is one of the goals, then you can put value zero here. If you start here, the number of moves is zero. Why the dog sleeps too long. What What is he supposed to do in the apartment? Also, he's an old dog. He's 9 years old. So, this is the majority of time for him. How long should a dog sleep per day? Here we go. And how long should 9-year-old German Shepherd sleep? 12 to 15 hours.

1:13:40 like if you're if you're wondering he's alive just he's used to the fact that morning to afternoon he doesn't get much affection so my wife is at work and I also try to work and he's used to the fact that in the morning and in the evening like late afternoon to evening there is more activity plus I we had a walk just before the screen. Uh okay, back here if what about neighboring cells for this cell? Normally we would say that the answer is one because from here you can make a single move. That being said, Alice will forbid this move and this will be minimum of remaining cells.

1:14:37 It seems that for the game to actually not go infinitely, there needs to be here a second cell that also is the target, the goal. Also, we've written zero here. So that now from here, Alice will forbid one of those two directions, but Bob will choose the other. So we can put a value one here. And always for every cell once two neighbors are chosen because by default in those DPS or Dextra or BFS you can put infinity there. Infinity infinity infinity. And what this problem boils down to is that DP of cell DP of any cell is second minimum of neighbors plus one.

1:15:35 That's because Alice will forbid the first minimum. Alice will forbid one direction, the one that leads to shortest game. If for a cell the neighbors are one infinity infinity infinity then this cell stays at infinity. Alice forbids one direction and Bob will choose one of the infinities. If you have two neighbors that are already non- infinity for example this one is a three. Eventually something happened and we put a three here. Now we know what to put here. It will be a four. And like usually in BFS or Dystra we will go increasingly from smallest values.

1:16:17 Uh so it's not that we will miss something. It's not that later this infinity suddenly will change into a one so that we are incorrect to here put a four. No we go increasingly through values so that when we see a three here and because of that we put a four here because that's second minimum among neighbors which is three + one. So F4 uh later the Infinities will also change only into F4 or worse. What keyboard? Uh some old Logitech keyboard. They don't sell it anymore. Lessons about heavy light de composition. Don't think so. No.

1:17:00 Senior citizen indeed. The dog. I mean uh Goraf for your previous question I think the question and the answer to it would be very complicated how to you know revise concepts and keep them I don't know how to reply to that fast uh well maybe after I finish this this contest. So there is F task and after that G I will then spend a little bit more time answering questions. Okay. So initially all the G's all the goals from the statement or from the input we mark as zeros and then we need to use recursion. No, no, no, not not recursion. We need to use BFS or BFS style algorithm to go from smallest values and always for when we put a value somewhere we need to check if for any neighbor now it has at least two field neighbors and if so we now also can put something there also. What about stuff at the side of the grid? So if there is a number that has nothing on the right then do we treat that as infinity?

1:18:31 I think so. If at the bottom we have a one and here we have infinity and infinity what will be there? Alice will forbid going down and then going anywhere here that's infinity or a cycle. So yeah, the outside of the grid should be treated as infinity. I believe to to make it easier to handle, I'm going to actually assume that infinities are outside. So for example, if the grid is 3x3, my indices will go one, two, three, one, two, three for rows and columns. And well the actual array that I store will be h + 2 * w + 2 to account for that to account for the extra infinities. So if the grid is like that then actually in my memory in the array I will have this everything outside is infinity.

1:19:38 So long since the last time you streamed. Actually, I streamed yesterday. Okay. It's unlucky that it's actually a nice problem, but such a long statement. I think I wouldn't as an outer write all of those things so formally.

1:20:27 All right. What do we have in the input? Why is the number of targets up to 3,000? That's strange. I'm not using that fact. Yeah, that that's suspicious. If it was a division one contest and not for beginners, I would now stop and think a few more minutes about it that maybe my solution is incorrect because I'm not using the fact that the number of targets is small. Strange. Strange. Okay. Uh what follows those initial stuff? Okay. So we have the grid. I'm increasing the size by two to avoid ifs about going outside of the grid because it's n square login. No, my solution is of h * w * log. I can also do it without logor logarithm. But what whatever k is not part of my time complexity.

1:21:53 I mean this will be how I initialize the let's say BFS but I don't have K squ and I can imagine there exist other solutions that rely on interaction between the target cells but I think those solutions would be way more complicated. Okay. By default fill with infinity.

1:22:47 A of row column is equal to zero. And you want to do it as a BFS. So just some kind of Q push back row column as just like in one of the previous problems. Actually I'm not using a Q. I'm using a vector. This is what I always do.

1:23:15 Wait, what was the way to untie a pair in a single operation? Was it like that? Does it compile? I need to start using modern C++. Yeah, it's like this. Okay. Uh so we take row column and now for each of four neighbors I need to update it if it has uh at least two non- infinities as neighbors

1:23:53 I don't remember my cirillic hello Abdf Good enough. Abdf I used to be able to read ciric but it was several years ago. CP only relevant for red coders. No, I don't think so. We have calculators and yet math I think is important in particular. No, no. uh tech lover that wouldn't work if here's a code that is undefined behavior defined behavior. Uh vector with few elements for every element in the vector if it's a 20 push back 40. It's important to keep in mind when using vectors in C++ that you cannot iterate the vector like this with a for loop iterating elements directly not using indices and push back inside.

1:25:05 You might think that this will just push back 40 at the end and that's it. Not entirely true because a push back can move the full vector in memory and the for loop will be broken. So this is undefined behavior and for the same reason we are not allowed to here do it as a for loop without indices. That's a disadvant a big disadvantage of using a vector instead of a instead of a Q. If I did for uh the out row column maybe with amperand with the reference I don't think that matters. This will fail if I here push back something to the vector.

1:25:47 This is why I used indices. Okay. Here I want to do for every neighbor count its neighbors. Get neighbors. I wonder if this will work like that as a one minor row plus direction first and now V in place back RC. See

1:26:41 though this will get me stuff from the border. Well, we'll see. Okay. For every RC among get neighbors of row column. Let's go full screen. Paint resources to learn data structure concepts like graphs. No, he's red. Don't teach lesson to Eric though. Oh, I strongly disagree with that sentence. I'm red, which means I'm good at algorithms. That being said, I'm not, you know, that good at C++. It's perfectly fine. And actually a minute before Techlover uh posted the comment with that for auto I said out loud that I don't remember how to do this and I need to start using modern C++.

1:27:42 So after that it was perfectly reasonable to give me a piece of advice about how to do it shorter. Red coders are not necessarily good at programming language at knowledge of about but they will know how to do any basic stuff in some way. It's maybe not the shortest or newest way. Okay. For every neighbor you need to now count if it now has two neighbors. First if afrc is equal to infinity. Now count the neighbors. Maybe this for every its neighbor. And now I think we can get outside of the grid. So we need to be careful side uh v push back a of r2 c2. Not v was already used. So I neighbors nay and then sort the neighbors and you want to use second minimum if neighbor of one that's second value if this is not infinity then we do something my own value RC is equal 1 plus that second minimum and to the Q.

1:29:14 Oh, the V was actually not used yet. Well, whatever. And place back RC compilation error. Apparently, it's not enough to put those brackets and hope that it knows that it's a vector of pairs or a list of pairs. Okay, at the end, what am I supposed to do? Uh, output a single value, the sum of everything.

1:29:58 Okay. Your row call is not infinity. Finally, we here have a cell that is inside the grid. If I go to neighbor, it can be on the boundary. And then this can be even outside of the boundary. So I think here we need to do if at least this otherwise I would get runtime error. What I could have done is I could put two layers of extra walls surrounding my grid and then I wouldn't have this issue. Let's see. Two. That's I think a very weak test. Uh not 43. Okay, let's run again in a contest. Run all the tests from the statement. So there was a third test.

1:31:17 I was just lazy during a stream. I'm not penalized for every wrong attempt. Oh, actually it's incorrect. So I will get wrong answer. Yeah. Uh I failed one sample and I failed a lot of big tests. Okay. I did not expect that. Please teach me heavy light de composition. Look, if you pay hundred something euro per hour, I can teach you just make a border of two souls instead of one cell. Exactly. Uh how Erica, how are you doing today? I'm okay. And yeah, let me repeat the logic because maybe when repeating the logic, I will realize what I'm doing wrong.

1:32:25 the task set that there are two players Alice and Bob let's say and in the big grid there are some cells that are targets or goals so this might be a goal this might also be a goal and there are a few other such cells we consider starting somewhere uh for every cell we consider that maybe we start from there. And what Alice does as the first player is she chooses some direction to be forbidden. And then what Bob does is he chooses one of the remaining three directions and he goes there. In particular here, he will go directly to the goal because it's optimal. And then after one move, we are at the goal and the game stops.

1:33:17 If instead we started here, most likely Alice would forbid this direction. Then uh then Bob would go here. Then Alice would forbid one of those two directions and Bob would get to the target after two steps. So the answer for this cell is one. For this cell is two. For this one is zero zero zero. And for this cell by the way it would be free because we would for bit here. Bob would go there and so on. Uh for this one it's also free. For this one is four. For this one I think it's five. Uh and the general logic for this one it will be one. General logic is that for every cell if the answer is already computed for some of your neighbors. For example, for this neighbor of yours the answer is two. So if you are here the game will last for two more steps. Here the answer is four or maybe let's say five. Here eight. And here it's not computed yet. So infinity by default.

1:34:20 Then at every cell its answer is well Alice will forbid the direction to the cell leading to shortest game. Bob will choose the second best. So the shortest among the remaining. So basically the second minimum and Bob will basically go there which means that we will put here value six generally second minimum plus one and that's my code. My code is that in BFS order we always check all my neighbors and for each of them so once I'm updated I need to think about it for some more maybe is it maybe I actually need priority Q I did BFS uh when I'm updated to some value I check my neighbors and for each of them I check if now you have at least two non-infinite values as neighbors

1:35:31 sold 380 on lead code. I can solve a single one on my own. Wait, you're saying you solved 380 problems, but you cannot solve a single problem on your own, even the easiest ones? If so, I will be straight with you that you shouldn't do algorithms.

1:36:02 Cut doesn't go to sun for nothing. I don't disagree, but I don't know why you're saying that. Is there a way for me to analyze this? No. 157 is too much. Let me check something. Let me check if after this process for every cell if I here again collect assert af row column is equal to 1 + second minimum. So create a vector made of neighbors

1:36:56 sort. And now assert a of row column equals infinity and v of 1 is infinity. Or a of row column is not infinity and a of row column is equal to 1 + um 1 + v of 1 or a of row column is equal to zero. That's one of the targets from the input. Okay, interesting. The assert failed. Let's see if it doesn't fail for the other two tests. Sadly, I overwritten them. I overwrote them. Normally, I call tests in in two in three, but here I did not. Okay, I think I'm very lucky that my assert fails because it will be way easier to analyze.

1:37:57 If you have wrong answer, then yeah, it's there's so many things that can be wrong. But this is a test. Uh this is a test. This whole building is quite new and still in a lot of apartments still people do not leave and instead uh there are some you know work renovation a lot of drilling and stuff like that. And when the dog hears that, he will bark.

1:38:46 500 here. Yeah, guys, if if you solved hundreds of problems, but all of that with editorials, then I mean that's fine. You can do it, but don't expect that to suddenly change. I guess it's like solving sudoku and every time looking up answers and putting few digits from there. There's nothing wrong with it if that's your hobby, but it just means that sudoku is not for you. Name of the dog, Oscar. Uh, okay. This strongly suggests that my order here is wrong. Let me think about it. I think I I kind of assumed that. Uh yeah, by the way, sorry that my soul just left my body. I'm guessing it refers to that barking. How loud is it compared to my voice?

1:39:53 Was it very loud? Sell updated more than one time. I don't allow it but maybe uh I think I can at the end output everything Well, I got something. Maybe I want to know where this fails, but it would need to be without that.

1:41:06 close to the end. Wait, at the very end? No, around here. Somewhere in this row. 0 1 0 Okay, for these five things do not work. How did this happen? Why is this guy F5? Second minimum among neighbors is A2. So this should be a three. Now let's get back here. Also one more thing. If I output a of row column and then return zero, do we visit things in increasing order? Oh no, we do not.

1:43:06 Why? I mean, I could during a contest I would just here slap priority Q or set on the top of this and I would get accepted. I want to understand it though. I thought that what happens is when I see some number something changes from infinity to non- infinity it can trigger a neighbor to now have at least two neighbors so automatically it value its value will become my value plus one right so the moment the moment when this value let's say changes from infinity to five I check the neighbors and if for this neighbor of mine now it has two neighbors in total that are not infinity then its value updates and it will update always to six I thought apparently that's not the case

1:44:14 but I first do all the zeros How can this three this one it becomes a one because it has two neighbors of zero. But when the second of the zeros is considered Okay, so a zero updated its neighbor and it will be neighbor of this guy. Then for here it has a neighborh.

1:45:13 I think there could be updated values updated to six earlier. Then such a five and a six together give us seven which gets added to the Q quad early. Okay. So, five updates a neighbor of six. Let's say six also had a two. There can be other sixes that were before or are after this six is somewhere in the middle. I mean, it's a new six. Some other sixes. We're already in the queue. This six will go after a lot of other sixes. Now, after this five, I consider some other five. And this other five. So, maybe I'm doing this first. Then I go to this other five.

1:46:46 And this other five sees a neighbor that now has two neighbors like this. And we put a seven here. So this is now not monotonic because now maybe there we have another five which is here. I consider it third. And now the this five and this five will have a neighbor with now two non- infinite neighbors. And I will put a six here. But the order how I inserted things is first I inserted six then a seven then a six. So now it's not monotonic. Six seven six. Okay. Got it. Uh random stop spamming.

1:47:39 Um okay. Yeah. So, apparently it's a little bit more complicated than I thought. Uh, so priority queue, I think. Yeah, actually I always implement Dexter and similar things with a set. Call it set. Set insert a pair of zero row column while not set empty ro. I wonder if this will work. This is set begin second and the star

1:48:40 and then erase set begin Q in place back set insert arc and RC See? Okay. What do you want? Will you work without the star? Yes, it works. So, also brackets are necessary. Uh cool. Try now. Still doesn't work. If I remove the assert, will it work? It stopped working. I mean, it it worked. It works differently now. I messed something up. Uh,

1:49:47 okay. Random last warning. Stop spamming. Okay. Oh, and obviously now if this is dystra style style then we need to sometimes we insert things multiple times. For example, we might update a of 22 into value seven but later we might update it into value a better value like a six. then this seven should be ignored. So set erase if a of row column is not equal set begin.

1:50:43 Okay. So if I encounter a pair with the first value being different than what is written in the array. So the best value ever then ignore it. Though I don't see how that causes wrong answer. It only slows the program down a little bit. Yeah, still wrong. Uh so always take the first if you're looking at infinity or now we should just do it always maybe.

1:51:23 Oops. How is how is this infinite? Now I need to say if this is better than what a of RC is right now. This is an improvement then I do this. still in feet. Plus one. Okay. Uh I think it's still wrong, right? No, it's it's good. So now I fixed it into a proper dystra logic. The asserts are necessary. I guess I can leave them.

1:52:29 So, it was I think a nice problem. I struggled a little bit, but that's okay, too. Sometimes I think it's educational to see mistakes. I thought BFS is enough. I thought that something will be in monotonic order. I got wrong answer. I eventually was able to produce order where things are not monotonic and I get sequence in non-increasing order. I fixed BFS into Dextra. Time limit exceeded.

1:53:14 Is it a constant factor or did I mess something up for time limits and we see run times of 2700 milliseconds. 2.5 is the limit. Or maybe they kill it after that much time. I don't think that I don't think that using set is a bottleneck here. I think that what hurts is that for every element what I do is I iterate neighbors and iterate neighbors again inside which takes a lot of time. And then I sort those neighbors. So the log from set actually will not be bigger than this four * 4. And then inside you push back things.

1:54:20 What we want to do instead is I can premp compute neighbors for every cell or change this into some kind of oneliner like I did in the here for the sake of computing assert. But I still think the set is not the issue here because this set will be set operations will be done not that many times I believe or maybe every time we see an improvement actually it's not clear to me if we will see an improvement h* w times or maybe this times 16. Let me premp compute neighbors.

1:55:25 I just want to know if I put good number of characters. Okay. neighbors. Okay. For everything neighbors of row column and place back this. I think we computed neighbors for everything among neighbors of row column. for this among neighbors of RC still works. No, no, it does not. I hear don't have neighbors of the stuff on the boundary. Maybe I should because that was the logic before.

1:56:57 Yep. And let's try now. So getting neighbors for a cell will be now so much faster because it's already computed. But it's also possible that the bottleneck came from the set usage. I just think that it's not the case. Fastest way to become experts, solve problems. Grit is always annoying to work with. I don't think it's that annoying. It's unusual that I needed to iterate neighbors of neighbors. In particular, it increases the runtime 16. And it seems like it's not optimal. I don't know. Still time when it exited. Okay, set it is sorry. Prior priority Q it is. Uh, where's my set

1:58:09 top I don't remember all the operations. And now I want to do it in the opposite order. So, do I now need to here type greater and a lot of stuff here like this? I don't remember exactly. No. How priority Q will increase the performance here? It's significantly faster than set. If you don't need set operations, then well, priority Q is simpler. So, faster. Oh, it's greater without anything extra. Still doesn't work.

1:59:36 vector than greater vector than greater I don't understand and in both places I insert There's that. Okay, thank you. It's great that my priority Q is called set. Beautiful variable name. I again got four time limit exceeded.

2:00:41 Thank you detective by the way for telling me how to do this. So how to reverse the order in priority queue. Still time limit exceeded. Also, I wanted to do the stream today for 90 minutes and we are at two hours. But I will take a look at the last problem after I get rid of this timing exited. Uh maybe it actually is important that there are 3,000 elements in the input. Maybe the solution is completely different.

2:01:31 Why is it not faster? It's hard for me to test locally because it's I think hard to create a good max test. I don't know how good a random test would be. I think it would be bad. Maybe if you just put the targets on the main diagonal that makes sense. Not sure.

2:02:09 What about this for a speed up? Now since we are doing things in increasing order, I think we will always assign our neighbor to my value + one. So I think it's correct when trying my neighbors to say if a of r c is greater and a of row column + one then only then do this and moreover it's enough here to count non- infinite neighbors if a of r2c2 is not infinity then count ++. If count is at least two then do this

2:03:08 also we can hear if a of rc is not infinity. Oh no I have priority. Never mind. I wanted to erase the old element but that's possible only in the set. I messed up. I want to make sure that I didn't make some stupid bug in the code that I've just done for this neighbor of mine. If it would be improved as my value plus one, then check if that neighbor has at least two non-infinite neighbors. If so, then it becomes second minimum, which should be myself + one. Well, apparently that's not correct. Maybe this if at least is correct.

2:04:30 Seems so. So this will be faster by constant factor. You don't check neighbors that are equal to you or smaller. You can maintain two minimum of a cell. Yes, I can. By the way, for such a small thing like if that for every cell I maintain neighbor values, priority Q of size two or something like that isn't even optimal. You should just use array or vector.

2:05:25 You can use this to generate huge test cases. If it's just a tool to generate tests, how does that help? Chando TC frame this frame C++ framework for generating test cases of competitive program problems. I don't have issue in using randomness but here it's just very difficult to do it. How do you want the test to look like? It's not that some tool will tell me how to generate a strong test in this particular problem.

2:06:23 Well, I can speed up this a little bit. The input output reading cannot be the issue because we don't have much Well, let me generate some test. I'm putting things on the main diagonal, right? Grid of 5 by five, five targets, one one two and so on up to five. Now we wonder how much time it will take if I run 3,000 by 30,000 a lot of time three and a half seconds also I don't know why sometimes the real time is so much smaller There is something wrong I think with time command on my machine. Maybe because it's a virtual machine.

2:08:21 What about getting rid of the pairs and storing cells as the hashes? Yeah, that that can help. Uh I want to first make sure that this part of the code is slow. Well, already this part takes a second. So I guess push back into a vector I can replace that with inserting to an array that will be something. So this takes one second and I'm guessing it's because of that operation.

2:09:35 some constant optimization. Okay. Okay. Do you do I want to bother with this? How to join your discord? Isn't there a link on Twitch? Can on guys on Twitch? Can you type exclamation mark discord? There will be a link and I think it's a very simple link like something discord gerto.

2:10:17 Yeah, this thing. So, this will copy it for you. I I'm not a Vim user. Well, let's compress things into integers, I guess. Get hash or something. Given row and column return row times this plus column. Uh so now this is vector vector in

2:11:38 every direction. I guess we can put things here already. If this so if you're inside the bounds the neighbors of get hash of row column push back get hash of RC. From now on we will use integers not pairs. Also the priority Q now is doesn't have pairs here just single integers.

2:12:26 Get hash of row column. Okay. Now this is auto sell a of this. Should this still be two dimensional? No, I don't think so. Uh, but all of this seems very annoying. And this is supposed to be an easy problem, right? I'm now flattening the grid. It will be one-dimensional. Instead of 3x3, it would be an area of size nine.

2:13:28 Woof woof. Okay. So we grab this if a of cell for every cell two. If a of cell two greater than a of cell + one, uh for every cell three among neighbors of cell two, this is already checked. Cell three. Sword.

2:14:21 Cell two. Cell two. Cell two. Cell two. And here let's get rid of the assert. But the only thing I will do is if get hash of row column then get the answer from get hash of row column. Well, this was annoying. Not very time consuming but still annoying

2:15:01 and there is low chance that I got it right. Well, I got it right in terms of correctness. And for time, it's a little better. It was 3.5 seconds. I'm going to submit. But this would would be such an embarrassment during a contest. Right? What was for example the previous task reverse that I solved that what in one minute after understanding the statement I had the idea for a solution in one minute and coding was I don't know five minutes unless I made some bug and for this task I spent an hour yeah 1 hour 10 It's push back on precomputing produces memory allocations. I agree. Yes. Uh one of the speedups I said I consider is to here avoid push back and instead have arrays.

2:16:25 Also here I have a small vector to which I push back and sort. That's not perfect. I would argue that if we want to allow solutions like mine, then the constraints and versus time are very tight. So I'm guessing that the intended solution is just four times faster that my solution. Okay, what next? uh I will populate this with vectors of four negative ones. And here instead of push backing

2:17:28 instead of push backing what I'm doing is this for every element inside of this vector if it's negative one then replace it with the value and break. After this you have some unnecessary negative ones. So what I will do is for everything inside of neighbors if there is at least one negative one but this will only happen on the boundary then while vback is negative one then pop back now I think it's faster because only some vectors will be you know reallocated

2:18:22 It's significantly faster. It was 3 seconds. So I think I the prep-processing got three times faster. Next speed up is here. I want the second minimum among some values. Second minimum you can maintain using two variables. Min one, min two. Uh for everything a of cell three if x smaller than min equals x but first min 2 equals min one. Else if X more than min 2 is X min Oops. Uh

2:19:16 down to 1.3. Let's submit. But all of this should not be necessary. The next speed up would be for every cell to maintain the two minima and then when some cell changes for all the four neighbors I only try to update those two minima. though it's tricky because it's not that I just maintain two minima as values and I put the third value there instead I need to realize if my old value was one of those two minima and I should replace it or I I'm a new value that should be next to those two existing minima okay got accepted barely now how do you do it fast so two things first standings I want to see somebody strong in the leaderboard.

2:20:28 Obviously, they solved it in like few minutes. Can I see the code? Yes, I can take something from the front. Wait. So, this is a cube. It's some there is no logarithm here even. Um what about the editorial? No editorial. Now that now I remember that my first code didn't have priority Q but it was BFS style and I knew that it doesn't make sense. I mean I found the counter example. So why does this make sense? What is happening here? We maintain degree and I guess the DP value. We grab a cell for each of four neighbors. If it's inside the bounds, decrease the degree.

2:21:41 By default, the degree is two. If the degree becomes two, then do this. How is that not equivalent to my first coat? You can see the Japanese editorial by clicking above. No editorial. Well, we do from Japanese. I don't know much Japanese, but I think this those three characters you can read in Japanese as BFS. How is this different from what I did first? So, my intuition to try the BFS was good. it matched the difficulty of the problem. But I thought that we're we're seeing a counter example here for the order. If I have multiple fives, it's possible that I will see a neighbor and I will update it as a six. Then another five will see a neighbor and it will update it as a seven. Wait, no, no, no no.

2:23:24 This seven doesn't exist yet for this five. I see how what I did is different from what what they are doing. When my five updates a neighbor into six but six weights in the queue, it's not yet visible from a seven. So this is not yet processed. When I consider this five and it looks at this neighbor of seven, it tells the seven. Well, right now it's infinity. It tells this uh infinity, hey, you have a neighbor that is not infinity. But the infinity does not yet see the left neighbor. So it doesn't change itself into a seven that is not yet. Only when we get to a six, then it will mark the infinity as also having one more neighbor that is not infinity. And then infinity will change into 6 + 7.

2:24:17 So what I did from the very beginning is over complicated and do this wrong where whenever I get to some element in the BFS Q for example to five for each of the four neighbors I look at the four neighbors and I see if there are two non- infinities this is incorrect instead what I should do is when you have some value in the BFS Q for every neighbor you need to right now tell you hey I exist I exist take care of that and keep for example a counter initially counter is equal to zero then it will be one then will be two when it's two you need to do something so add this element to the cube this thing was incorrect uh that's because this element checked too much among neighbors it checked something here that was maybe a six and itself it became a seven and five should not insert seven into the queue because now it's not a BFS Q where you only insert the plus one value anymore for BFS to work

2:25:30 for BFS Q to work you need to have only transitions where uh a note with distance five will insert no another note with distance six this is so edges have cost one versus what I did first because my code checked too much let's say is sometimes I was at five and I tried to update a neighbor that became a seven from infinity became at seven so I kind of had an edge of cost two and this will then propagate into bigger errors and this eventually the costs will grow even more. This is why it didn't work. My edges in my let's say abstract fake graph, they had costs bigger than one.

2:26:28 That's interesting. So I was unlucky that my first solution was slightly over complicated compared to that. I then realized why it's wrong. But I thought to correct it, I need a setter priority Q. But turns out that the limits were not really adjusted for that which makes sense because here the intended solution is just linear. So priority Q seems to be an overkill. Okay. Well, that's I would say that uh it's interesting that something like this happened. I could code the new solution, but I leave it up to you as homework if you want.

2:27:11 Are you reading YouTube chat? Yes. Not always. Big B. I'm going to read this and then most likely finish the stream. Uh because it's too long for me and also I want your opinion like I often do recently. Uh so what we did today today we solved almost the whole ABC contest ABC let's let's call this division three. Now the issue with that is that first problems were some problems were not interesting for everybody for every person some problems were boring either too hard or too easy. So there is big spread of difficulty.

2:28:07 I will type this as a minus big spread of difficulty and as a plus I will say easy to organize the choose. It's very the structure of the stream is very regular not random where I just go through problems from one contest. As a plus, I will also say I could announce which contest in advance so that you could before the stream try the problems on your own and I think then it's been very beneficial to watch the stream. Uh, what I can do instead during a stream is watch. Sorry, not watch. Solve a lot of problems of similar difficulty.

2:29:05 Like in code forces, let's say only difficulty around 12 or,300. In atcoder maybe it would be among at fromcoder beginner contests. Let's only solve C and D from a lot of contests. What version do you think is better? One contest only or one difficulty only. Let's call this version one and version two. What do you want me to do for future streams? Can you you can type one or two whatever you prefer and you can also give me some arguments some explanation because I don't know what is better. Hi you have been my biggest inspiration for journey into CP even this late in my life. Thank you for all your teaching. A simple column that's very nice to hear.

2:30:07 You're welcome. Chef Jeff's choice one difficulty or one concept contest solving ad hoc problems has more value but Chando you're talking about the style of problems I don't know then which version of the stream is better one topic only But one topic only. The issue with this is that many problems do not match really a topic or also a topic is a huge spoiler to a problem. Especially nowadays a lot of art color and code versus problems let's say it's a sequence and you do some operations. After reading the statement you don't know what the solution will be about.

2:31:14 Yeah. Uh I agree with Nikil. So do we accept spread of difficulty? It seems that this is good for regular well organized classes and so is the topic thing where if you're doing competitive programming if you want to practice for that and you are waiting for the stream and you want to plan some No, no, that's not what I want to say. If you want to improve and the difficulty will be right for you, so it's like slightly above your level somewhere around that then this seems best to learn. If you want to really treat this as a learning experience where if needed you're going to pause the stream or you want to watch it again if needed to actually understand everything.

2:32:18 So as I lecture to a fixed group of people, it seems that this is beneficial. That being said, for the remaining people, for those stronger and those weaker, this will be not a useful stream. So this will alienate a lot of people. For this one, everybody will get something just at some moment of the stream. Another thing is that uh I wanted to keep the separation and alternate between division two and division one streams. And when we get to the end of this atcod or grand contest, what am I saying? Beginner contest, not grand contest. For grand contest, we wouldn't solve six out of seven problems.

2:33:09 Uh when we got to the end, it wasn't easy anymore. And actually I struggled. I had bad luck but still I struggled. Uh best way to prepare for Olympiads first be good at competitive programming in general then start solving Olympia problems. Glump I I see your correction. Uh but this also might mean that we will solve those harder problems. What about this? I think chose one because I wrote agency. I What about let's say some kind of hybrid of this? I think that a contest, a full contest is too big of spread. It has a very big spread of difficulty.

2:34:15 So maybe what I should do is during a division two stream like the goal for that was today division two stream. It's okay to solve let's say ABC or division three A to E problems. And once I'm done with that, move to the next contest. So keep doing easy problems. Still it's okay to do a lot of problems from one contest. So still for a lot of people it will be beneficial. And then in a division one stream, what I would do is I can still warm up with ABC/Division 3 F or G, but in practice I would rarely do that because it's doesn't seem very interesting for experienced people. uh instead it would be just well division two let's say or division one A to C problems and maybe then move to another contest.

2:35:22 So let's it's kind of between of those two where it's half of the contest. Do half of a contest and then move on to the next contest. And another thing about this is that the reason why you see me you see me stream a lot in the past couple of weeks is that I have time and it's easy for me to do a stream for such almost daily streams. I don't have time to prepare for it to spend one hour in advance and prepare in particular because I don't earn from this. This is just a hobby for me and spending two hours several times a week that's already a lot of time but adding preparation to that and is also adding some kind of stress because it's completely different in terms of mindset. If you turn on the stream and you do some stuff and people happen to watch it versus you want to plan it, that's really a huge difference. And if I was to do go with this in practice, you would just not see that many streams

2:36:46 or just no streams at all because it's so much easier. Maybe this stuff makes sense for weekend streams on Saturday and Sunday. It's natural that more people will watch So maybe I can think about every weekend doing a topic stream. I would prefer to have two free streams a month from only one topic. CSS problems for example. Yeah, I think that's reasonable. So on once a week usually on a weekend there would be something planned where I need to on code forces announce it at least a day in advance. Some people might want to try those problems.

2:37:38 But for those daily streams like if I just today what is it today? Friday. Friday I have some time I want to go live solve some problems. So practice a little bit and also teach you then it needs to be one of those two. Solving recent contest helps being organized. Yeah. Uh is it fair to say we don't push immediately in the neighbor but the second time it is visited? Well yes. I think it is fair to say that

2:38:30 why you're not doing camps. What do you mean? What kind of camps? Like onsite or online? Next, just next week I'm doing I'm teaching at an online II camp. It's free for II participants. So it seems that the plan will be so once a week in practice it will be three times a month. No, sometimes on weekends I'm busy. Uh, so maybe Saturday or Sunday three times a month on average it will be a topic string. For example, DP or some section of CSS. No, I wonder if advanced section of CSS counts or maybe USA guide. guide topic. Psycho has also a lot of materials though it we need to I need to choose the difficulty as well and then sometimes daily.

2:40:06 Well, if sometimes then it's not really daily. How do you spay daily? Why do you spell daily this way? Why isn't it daily? English is so stupid. Sometimes daily it will be just division two or division one stream. Solve have a contest move to next contest. I think that will be the plan. For example, from today, if this was supposed to be an easier string, I should have stopped after E. ABCD E. Move to next contest and again solve ABCDE E. Keep the harder problems for the harder stream.

2:41:03 Yeah, for for daily streams we can do ABCD from either division one or two. Yes, though division two a division one ABCD can take really a lot of time. So for division one stream I think it would be more like ABC and move to next. U let me answer some chat messages. What do you consider Q&A streams? I mix that in between of problem solving. I don't think it's such a useful idea to do just a Q&A stream. I think it's better if at the beginning of the stream or the end of a stream I do it. Maybe I should focus more on it at the beginning of a stream.

2:42:00 Uh the II camp is no code forces. No, the camp is only for II participants. I will consider advanced CSCS, but it's a lot of time. If you want to prepare for IO for Olympiads, you know, spend as much time as you can as you want. 20 hours a week is certainly enough to not feel bad about not spending time. So let's say 20 hours a week that's that's a nice amount but not everybody can do it. Ramsey you should read my blogs in code forces.

2:42:54 So generally code forces is is loading. I see. Do I have I have the internet. If you go to my blogs, you will see a lot of stuff. In particular, the II camp announcement. Uh some stuff is not announced, not posted yet. Uh oh, and for example, here when talking about my streams this summer, I mentioned that you can book a 50 call with me in particular. Then you can for 30 minutes ask a lot of questions. I put a link, but you can also search for code versus Erica. This particular thing is here though next week starting from Thursday I will not have time because of the II camp.

2:43:56 Uh the camp will be recorded and posted in half a year or a year but there are recordings from the previous free camps. You can watch those. Okay, that seems to be a reasonable plan right? All right. Uh now, uh I wanted to look at that last problem. Even though I've just said how stupid it is to have such a big variety of difficulty, I just want to read. So, it's this thing.

2:44:47 There is a grid there. Okay, obstacles. We are here. We want to get to the opposite corner. We can move up, down, left, right. Check if we can reach. Oh, that's Oh, that's a very standard problem. Uh, well, I know a solution here. Uh, so the task the the issue here is that the grit is huge. You cannot run BFS or DFS because the grit is 200,000 by 200,000 and there are some obstacles. You want to check if there is a path from one corner to the next. There is a hard solution using data structures that actually tries to find reachability to everything. When you are in some row, you can use some data structure to see how far to the right you can go and use in some way mark that region and so on. Different implementations are possible. Maybe a segment tree is one possibility. Maybe it can be done without it. But the easy solution to this, so if you have a huge grid like 1 billion by 1 billion and some blocked

2:46:08 cells and you want to check if there is a path from one corner to the other, if there is any path here, then instead what you check is you check if there the path is blocked, which means that there needs to be a path of blocked cells that goes like that. So it connects it needs to connect this side of the grid with this side of the grid. If there is if you could move up, left, right, down, then if there is a path of let's say this blocked cell, this blocked cell, this blocked cell and so on, then it will prevent you completely from moving. Let's say this. As you can see here, this makes one corner not reachable from the other. And this is because there is a path from here to here.

2:47:06 And if I can move, if the statement says that we can move in four directions, then the blocked cells, they can move in eight directions. So diagonally also is enough to block. Basically the I'm not sure about proper formulation of that. But for adjacent reachability uh of one corner between corners is well equivalent or dual. So it's a duality to eight adjacent reachability between sides of the grid. And by the way, if we could move in eight directions, then we would need to check if the there is a path of blocked cells uh where they can move only up, left down right.

2:48:02 So I guess I can as well implement that because it will take five minutes then I will finish the stream. So that's a very standard problem that is perfectly fine for a beginner contest. But this would make no sense in a division one contest even as division 1A because it's too well known. Beginner contests or division 3 is a good place to explore such standard problems. Let's move this here. this here test cases. No, I'm surprised that there are no test cases. If there is yes or no question, uh do I need this? No. If there is a yes or no question, uh then usually test cases help.

2:49:01 Otherwise, you need to create really a lot of tests. Uh yeah, Ramsey, I already gave you some links. Go through those. Also, in important contests, it would be bad to have two problems of similar style in a row. This is a grid problem. The previous one is also a great problem. And that's good. That's a bad combination. Now, how do I want to do this? A set. And let's do DFS for everything in the neighborhood. This is how you iterate the eight neighbors. Up, down, up, down, left, up, and so on. Eight neighbors.

2:50:26 Visited. visited insert row column and here if this neighbor if it's not visited but it's in the cells in the input then go there. Additionally, if it's at the end, if row equals the last row, no, the first row or column equals the first column, then uh we output no and we stop the program. This means we got to the opposite side. In my drawing, it's this thing or this thing.

2:51:33 I need to run the FS and if nothing happens then output yes. And here what I do in between I need to say if if row equals the last or column equals first then starts push back or place back row column for everything row column in the starts if not visited yet DFS.

2:52:25 Okay. Cells count No. And I want to see a single yes. Again, I've overrote the test. Now, how much time did this take me? Four minutes. And the previous problem took more than one hour. Here we see half an hour since the last submission. But this is because I uh talked about other things at coder or code forces for problems practice you should mix. Did you have software uh experience, engineer experience? A little bit. Stream schedule. Uh no, it's not the same every day. I will try to make it more organized. Uh how do I this?

2:53:52 There is this calendar. And usually a day before the contest, I put the announcement there which is displayed on the Twitch channel. I think it's nice if you plan to solve beginners since it's very educational. I agree that beginner or division three contests are educational. here below the uh Twitch video you can also see this calendar and I think there should be some way to import that or use the link it's the it's the same thing the link is taken from here or the other way around but it's not that I have organized enough schedule that it's weekly same uh a day before if I see that I have time then I will put stuff here additionally I will put it on code forces so in forces on the right. You will have the the countdown.

2:54:54 Will I beat LGM again? Maybe. We'll see. Division 3 are less educational. Then maybe it's a good idea to solve old division three. Oh, another question to everybody here. uh when solving problems it can be division three division one that color beginner what whatever should I use option one new contests recent contest I mean or old contests let's say five plus years old you can type one or two the advantage of this is maybe you will see a problem that recently you tried to solve but failed also it's basically uses well newest algorithms, the newest meta of what we should solve, what we should know how to solve. And this is generally more educational. More often there will be an algorithm that you should know.

2:55:55 You can type one or two in the chat. Chinaya, why did you type one old contest? Was one was new contests? No, no. I agree. I have problems in solving Isako Bronson gate. What to do? Not sure how to help you. If it seems that you are trying to solve stuff at some level and it's too difficult then generally the advice would be drop to lower level solve a lot of problems of easier category.

2:56:52 Uh I don't know how many comments are repeated in the chat. I hope not many but generally that two one. I will keep that in mind. Okay, I think we can wrap this up today. Uh, so yes, solving is good for practice that you practice competitive programming by solving problems. Two new contests. Uh, okay. What was I going to say? So, just to make sure in add now we solved everything, right? How do I check that I solved everything? Why is it not green? Results. My submissions. U status accepted. Search. A B C D E FG. Okay, great.

2:57:49 Uh, okay. I see some new comments. I will answer to this. Is it good strategy to absolve all for all the problems I can solve? Yes. Generally if you participated later you want to solve at least one extra problem something that you couldn't solve during the contest. Though if for example you solved during a contest let's say ABC then it means that you should absolve D you should maybe try E but further problems are likely beyond your reach so it's not that you need to try them you don't need to try all the problems will I take part in next division one I'll see if I have time but generally I want

2:59:02 virtual contests from time to time are good. Okay, now that's really it. Today we did uh articular beginner contest something 413. I'm going to change the title of YouTube stream. Uh, by the way, if you want to help a little bit in in below the YouTube recording, if you want to find timestamps of when I start every problem, you can put a YouTube comment of something like at 1750 problem A, at 30, 33, problem B, and so on. If you do that, I will pin the comment or put it in the description and then the YouTube will automatically take that into the video to so that you would see timestamps.

2:59:46 if you have time for that. If not, that's fine. Okay. Thank you for watching everybody. If you're II participant, go to code forces for that II camp. Have a good day. See you. Oh, three hours. I wanted to

Questions about this episode

What is discussed in "ABC 413 | algorithms problem-solving"?

In order: 0:00 AtCoder, Huawei II camp 2025; 2:15:00 AtCoder.

What is mentioned in this Errichto Hard Algorithms episode?

6 people, works and ideas are mentioned, including Baghdad Bob, AtCoder, CSS, Codeforces, IOI, Huawei II camp 2025. Each one on this page links to its own page with every episode that mentions it.

How long is "ABC 413 | algorithms problem-solving"?

The episode runs 3 h; the transcript is about 17,182 words in 166 timestamped sections.

More from Errichto Hard Algorithms

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