Transcript

CF EDU 181 (Div. 2) | algorithms problem-solving

From Errichto Hard Algorithms · Episode page · Watch on YouTube

· 1 h 32 min · 9,150 words · 94 timestamped sections

This is the full, timestamped transcript of "CF EDU 181 (Div. 2) | algorithms problem-solving", an episode of Errichto Hard Algorithms published July 28, 2025 (1 h 32 min, about 9,150 words). It mentions 9 people, works and ideas, including Walerus, Rakkesh, Huawei II camp, Jane Street, University of Warsaw.

What is discussed, and when

  1. – 10:00: Huawei II camp, Rakkesh, Walerus
  2. – 20:00: Jane Street
  3. – 30:00: University of Warsaw

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

  • A particular message that is usually about the problem that I'm solving. Hi Rakkesh.
    about Rakkesh · at
  • So, in the past week, I did the Huawei II camp.
    about Huawei II camp · at
  • I don't I think all red coders are joining Jane Street. Maybe you know a few and just they know each other as well and they all happen to join Jane Street. Jane Street doesn't have an office in Warso and I don't want to move.
    about Jane Street · at
  • Yes, University of Warso prepares for CP contests. Every Thursday we have a 5-hour training contest using something some old ICPC contest and the analysis session. I'm one of the coaches in.
    about University of Warsaw · at

Who and what is mentioned in this episode?

People

Companies & orgs

Products & tech

  • OBS — Product · 1 mention

Concepts & topics

Full transcript with timestamps

Sound test. One two three 4. Sound test. One, two, three, four. We will start in few minutes as always. Hi Walerus. All right. Uh here we are live live life live life live life live life live life live life live seems all is good that's great and look at what I can do this Uh around a week ago, I experimented a little bit and I managed to find a way to highlight messages which should be very convenient because I sometimes respend uh reply to a particular message that is usually about the problem that I'm solving. Hi Rakkesh.

I also changed the chat settings so that the display above my face would be only for 15 seconds. I think that's already enough. And if I want to reply to something, I will just highlight it, which by the way was not simple.

Hi. Hi. Hi. What do I think is the rating of problems E and F? I have no idea. I don't know the problems yet. I'm going to solve them one by one. So, in the past week, I did the Huawei II camp. Uh then I also spent some time uh changing the settings in OBS for for the stream, stuff like that. For example, now my camera will not hide such a big area. So there there is background removed. Hi God Gamer, welcome back to the stream.

stuck in problem C. Oh, looking at the number of acceptance, I would say most people should be interested in the solution for problem D because there is a huge drop of number of acceptance. And then E,

I like the comment, good evening and in brackets Indian standard time. Good evening to you. This is how people should greet each other in the internet. Good morning to you and in brackets you provide your time zone. Okay. Uh

I don't think I will manage to solve all problems especially look at how many people solve this No, I don't think I want to talk about the climate change crisis. Okay, so this is linked to the contest. We will start from this thing. Oops, that was by mistake. Uh ju just a question both on Twitch and on YouTube. You now should see in the chat this message with my link, right? Let me know if you don't see it. So you cannot click it. I'm just I'm using a different setup today. Hence the question. Okay. Uh difficult contest.

Contest is a string S with uppercase letters that denote problems. uh contest is difficult if it contains FFT or entities substring. I don't think many division 2 participants know that task is rearrange the problems. Uh the problem well that's unusual that's a very simple typo. Rearrange the problems in contest S in such a way that this contest is not difficult. You want to get rid of FFT and you want to get rid of entity. So what about we put T before F and T before N? Oh yeah, just put all the T's at the beginning.

Then you don't have a way to get either of those as a substring. And there are test cases. test case I will build a new string call it out for every character in s if it's equal to the t value then I don't know increase the counter else put it to the new string so the new string will contain anything other than the t characters and at the end I want to output that many characters T and then the out string there is a counter starting at zero and this is how many T's there are

it puts this at the front CSS problems. Uh, one day, yes, for sure. Actually, I asked the author of CS Problems like whether I have his permission to do stuff like this. So, or he doesn't want people to generally do full editorials of full categories. I'm waiting for his response.

Will the stream end before the contest? Yes, I will stream until few minutes before the contest. In particular, I won't do much I couldn't even do much submitting after the contest starts because the I will not have the priority of judging during the code forces contest. It's hard to use code forces outside of the contest. I need to remember to un when when I highlight the message like this, I need to remember to unhighlight it. By the way, do you see this green tint under the message? Like it's not entirely white right there. There is blue background for the whoever sent the message and then there is this white greenish background for the message itself. It is because of the let's say green screen behind the message.

The setup looks like this where there is green screen that I need so that I could only capture some part. Accept it. I think I spent more time waiting for the verdict than actually coding it. Second task left and down project oiler. I think that first of all I I believe that project oiler idea is that there aren't many editorials online and you are supposed to try to solve a problem on your own. Second thing is that I'm not that good at math. I would struggle heavily with difficult tasks and I think it's not very fun to watch because I might even lack knowledge to solve something. For algo problems, I will always have some ideas. I can even explain why I think something is difficult. I'm I'm an expert at algorithms. I'm not that good at math.

Better than average, but not that good. out and not as whatever I not not a big difference I felt that this is the output string compared to the input string this was opposed to the string s there's robot located at AB on infinite grid uh we want it to move to 0 0 we have integer k choose two integers move by that much to the left and down. The cost is one if you use uh some operation first time. So once you use a pair like - 5 - 4 you can keep using it forever bring it down to cell 0. So we want to preferably use some operation and then keep using the same operation. Then the most basic operation that allows us to do almost everything is to move by 0 comma minus one or to move by minus one comma 0. Those are two unit operations such that I can with just those two I can move anywhere I want. I will pay one for the first time I use something.

So this always cost of two is possible. But maybe cost of one is enough. cost of one is enough if one type of operation is enough. For example, if the target is at let's say 8, 10, I can make my only move to be 4a 5 and I can just keep repeating it until I get there. The question is, can I have a move that fits within the bound K? And for that, I'm going to use greatest common divisor. I will look at the target in this case target GCD is two. I tend to they have common divisor of two. If I divide by two I have this smallest possible move that I can perform so that I would get to the target by just doing this move. Then the question is whether it fits in K also K is long long.

So what we are doing is AB K compute GCD divide both. If now this fits so I can make such a move then the answer is one. Else it's two. The two represents applying operations like that which should always be legal

one two one two correct have I considered high frequency trading firm uh I don't I think all red coders are joining Jane Street. Maybe you know know a few and just they know each other as well and they all happen to join Jane Street. Uh Jane Street doesn't have an office in Warso and I don't want to move abroad. I did consider high frequency trading. I even had an internship in one company several years ago and I had a follow-up offer. How is it called? when you continue with a full-time job. If not for teaching algorithms, maybe I would do that. But that being said, I like teaching algorithms. I like competitive programming. So, if possible, I would want to continue here.

Uh though, yeah, I don't earn close to the amount I would get in HFT. And I'm sure that I could get a job. Count good numbers. task C also in my setup here the difference is that I don't see the number of viewers can I fix that easily can OBS show me that I don't think so what other option do I have chat oh this will work test in OBS. I can also open the chat from restream and it shows me the number of viewers. Okay, fine. Prime number is defined like this. Prime factorization is splitting into primes. We call number good if all primes consist of at least two digits. So number is good if it's not divisible by 2 357.

Calculate the number of good integers from L to R. Okay. So in range the task is in range LR count numbers not divisible by 2 3 57. Uh obviously when you have a question about such a range you should focus on counting such numbers in range from 1 to r minus subtract those in range from 1 to l minus one. So now we focus on this we focus on given some upper bound count the number of numbers not divisible by this in such a range. I see two solutions. One is inclusion exclusion. Another is that when you look at those numbers and you look at their product or least common multiple but let's say the product this is uh 210 I think uh if this is 210 then once every 210 numbers everything repeats itself.

So whatever the good numbers are among the first 210, the next 210 have the same pattern because they have the same divisibilities by all of those. So I will use this solution instead of inclusion exclusion which is also fine and you should know how to do it both ways. Uh maybe even I will do it both ways but I will now focus on the function count up to given n. Ah so up to n count values not divisible by 2 357 and I will do this if n is for example 300. I know that the last 210 numbers have the same pattern as everything else. So I will instead work with this because I know the consecutive 210 values they always have the same count of how many of them are not divisible.

So what about this uh answer equals fixed value already computed in advance multiplied by n / 210. So whatever the full amount of 210 I have uh I multiply it by then the count of it that I will count separately. And also for every i up to n modulo 210 like here up to 90 uh smaller or smaller equal.

Yeah, that's that's a small inconvenience for this. If I or maybe I will make a brute force as well here is count is zero for everything from A to B. If I modulo 2 is non zero and I modulo 3 and I modulo 5 and I modulo 7+. So this uses a brute force to compute for a range. The value fixed I can even compute it here whatever um maybe with static fixed is brute force in range from 0 to 209 let's say in every consecutive 210 values it should be the same. I I see that in the chat you're telling me how many are there and I could actually also compute that using inclusion exclusion. Uh that being said I'm lazy. Let's say I already need I anyway need some code that will finish with the last few values. So as well I can use it.

uh answer is this and then answer plus equal the brute force in some range and that is usually from 0 to n model to 110. You just need to figure out plus minus one return answer. Inside of the test case, what you read is low and high. And we need to output count up to of high minus count up to of low. Finally, what about this model exactly? Um well I need to count n as well but if n is 210 then this takes care of everything. Well, I can say that this takes care of numbers from what? 0 to 209. And then this only counts zero up to zero, which isn't counted, so it doesn't matter. I think this will work, though.

It's not obvious. I'm not I'm not particularly proud of this code. 2127 something 70. Uh, this is incorrect. This is incorrect. How is this? I see some suggestions about prefix sums. Oh, low minus one is obviously. Thank you. Yeah. Uh I'm not going to speed this up because it's not needed. There are thousand test cases in it. If in each of them I do extra 210 operations. That's fine. In competitive programming, you're not supposed to necessarily try to get the fastest possible code. You want to get the easiest possible code that is good enough.

Accepted. How do I get the input in the file so fast? Well, let's see what I click. Copy. I click on genie. I have a keyboard shortcut to go to terminal. I type output to the file. Enter. Control shift V. So, paste. Ctrl C to close. And now it is in this file. I created the file. Of course, alternatively, I could open the file and I could copy from sorry, copy from here, paste there, but it's easier to do it in the terminal. Uh, let me see if the tutorial mentions the inclusion exclusion. It does. Yes. So, this is second solution. You can read it there. I will move on.

Next will be D. Before I do it, uh let me show you what I'm organizing next month. I haven't published yet, but you can make a screenshot if you want. Let me see. So, if you want to read this, you can take a screenshot. I will do weekly classes. The price is around hundred euro per month if you want to join live and 50 euro per month if you want only access to recordings the problems but you don't want to join live uh it will be similar time to the stream uh today so like right now in five minutes it would start on weekdays I'm thinking Mondays Tuesdays but that's not decided yet and this thing will start like in one week plus one day something like this.

Uh yeah, if you're interested just maybe tomorrow I will put the blog on code forces where you can uh when you can register and pay this. So far this will be the cheapest thing I do in terms of teaching where you pay. My live streams are still free but usually my like one-on-one classes or groups were more expensive. We'll see how this goes. I just hope I'm not overwhelmed by the amount of organizational stuff like you know handle all the payments. We'll see. I I hope many people will register still and maybe this is a success and I will continue it for the next year or multiple years. We'll see. So take a screenshot if you want and I'm moving on

uh for ICPC. I mean if you feel like it's too wrong too long for you to rewrite then that's an issue. Uh that being said how much time does it take you? If it takes you up to 15 minutes, I think it's fine. The of course perfect answer is that you should have something short that you still understand. But yeah, it's hard to answer your question. What should you prioritize? Short code that you don't understand or long code that you understand and can modify if needed.

Yes, University of Warso prepares for CP contests. Every Thursday we have a 5-hour training contest using something some old ICPC contest and the analysis session. I'm one of the coaches in Warso. Even Chance Otis. Even Chance of this first. Ian Chen. Do I know him in any way?

2014. That's a nice result. I Isn't it unusual to see somebody with a gold medal in IMO and only one participation? Uh, okay. Is this the website for the for the thing? I will check it out later. Let me write it down so I wouldn't forget.

Okay, problem D. Uh, okay. I I can answer that first. Uh, so regarding this task, here's the thing. When you investigate divisibility by three, let's say what do you have a pattern that says divisible no divisible no divisible no right you have this maybe I will write it as one and zero and so on this is divisibility by three if you have divisibility by four it will repeat once every four elements like like So now if you compare those two divisibility by three and four the first number zero is divisible by both and then number 12 is also divisible by both right 0 and 12 have the same divisibility by three and four. They are both divisible and afterwards everything is the same just like 0 is the same as 12. 1 is the same as 13. two is the same as 14 and so on. They have those two numbers have the same property of divisibility by three and four. You can add more numbers here and the same thing

remains. There is a cycle of size product of those values more general least common multiple LCM. Okay. Now the first difficult task linear strip divided into M cells. You're given n segments four numbers cover cells in range and exist with this probability. Your task is to calculate the probability that each cell is covered by exactly one segment. Huh? Before this I was almost sure it will be some kind of DP. Now I'm not sure.

So we have ranges. I'm thinking that this will be a graph problem. No, still solvable with DP. We have a sequence and info about some ranges like this, this, and so on. And we want to collect ranges that will add up to the sum of everything. First let's say how we would even check if that's possible. If there is a range from 0 to 5, we can mark the position five or position six as as available that if something starts there, it can be used as continuation. Then we continue and so on. We are talking about probability. So we maybe will multiply probability. I'm thinking DP of I probability that we cover prefix up to I. And there is this issue that this is easy to do transitions if we only care about the ranges that we should use. But also I need to say that all the remaining edges uh sorry ranges should not be used.

But I can then maybe at the end handle that. No, I think I need to do it as I go. So as I say that this is the range to use all the other ranges that I'm not seeing here. I should multiply by the probability that those are not happening.

Let's say as I process this I will say all the ranges that have their say end points anywhere here I want to have the product of their stuff for that I will use prefix product and I need to be able to divide. So if there is range I J then I do transition DP of DP of J + 1 plus equal DP of I multiplied by probability of this range multiplied by probability that other ranges that have end points here do not happen. probability not of end points in this range except for this range that I'm using right now. For example, if the probability of this guy is say 0.7 but there is also another range here that has probability of let's say 0.4 four when transitioning from here to there I will multiply the probability by 0.7 for this range happening and 0.6 six for this range not happening and I think that's the way to do it.

It should be also possible to do this problem without the uh modular inverse if you use segment but I'm going to use something simpler I think which is prefix product uh let's read the input there is L R and the probability oh there is probability P over Q so we need to use modular inverse I guess there's no way to avoid

And in this task, if you don't know modular inverse, you need to just ignore that part of the statement. Just think that there is no module and you're using real values. Kazakhstan championship. I mean there are many contests happening. I think I will prioritize code code forces where thousands of people tried it. I don't doubt that you also have some interesting problems but it's a niche contest. I'm from Poland so from time to time during streams I might cover Polish Olymps. I even have this idea that maybe I should during streams cover the past problems from the first stage of Polish Olymp. So the home stage

okay inverse This is boring stuff. Mostly you should just copy paste it during contest. Will you solve II problems that will be available soon? Maybe. I think I will do live commentary. Maybe I will think about problems if the statements are available, but I will not code it live. I think cuz then I need to really focus on it and I prefer just want to talk. Maybe I will invite some guests. We'll see.

Okay, I have the modular inverse stuff. So here the probability is the division between P and Q. This is the actual probability of the range. The range goes from L to R. And I will say this starting at L there is a range that ends at R and has this probability M cells. I will rename M as the uppercase L for the length. Maybe let's call this len and this will be n count. It's just too easy to mistake those two variables. We have this vector of per int double not not double int. This is starting of size length + one.

What do you want? Division is uh is it a keyword ambiguous? Yeah, it's a my division. Okay, I need to also have the prefix product. I want product of all the stuff that ends up to somewhere. So, prefix product of R multiply by P not by 1 minus P. This is 1 minus P because I want probability for something not happening. This is prefix product things that don't happen. Then I need by default values one are there and I need to propagate it like always in prefix sum.

product of I is multiplication with the previous element. Okay. Now for the transitions we have DP by default we are starting from position one. The answer will be position length + one. And for every i for every range that starts there, how do I do it? Uh, tie anti out auto, I don't remember. So for every end point and the probability among starting of I, does this compile? I'm trying to use modern C++ set but not used. Okay, so we have range I to J and it happens with probability P. The transition is DP of J + one.

I need to add by something DP of J + 1 uh plus TMP module mode. Now that this transition is DP of I, we need to multiply with the probability of this range and we need to multiply this with probability that other stuff here are not happening and that's the division of prefix product up to J minus or divide prefix product up to J sorry I minus one this will be product of the range from I to J additionally you need to divide it uh by the probability that this range is not happening because in the range from I to J you would want to say everything else except for me is not happening.

So you divide by both I will at the end summarize all the formulas. So we have P and you have Nope. There's like Now there's a 20% chance that this works first time. Yep. Uh something has too small of a size.

Line 40, starting of L, no test cases. Okay, I'm trying to read the first the number of test cases. Okay, that was relatively small mistake compared to everything else that could go wrong. But you see, there are a lot of small things that can go wrong. And this is why that 20% estimate still was very reasonable.

watching you live feel so so slow. I usually watch you at uh 1.5. It makes a lot of sense. Uh I also watch stuff on YouTube usually with increased speed and live you cannot really do that. Now what you can do is you can pause the stream and then watch a little bit. That's the beauty of live streams.

I mean there is my general advice on how to practice. You will find it on on Twitch. If you type exclamation mark practice, you will get the link. How did you figure out the line where it fails so quickly? Uh I mean with proper flags, C++ will show you where it fails. So what I did was it was important how I compile it first of all. So there is this I will copy This is my compilation command. Uh like I think here minus G and the minus D gip cxx are important stuff. Then what I did is I run the program called GDB using my program A and then I run on this input.

Uh, I didn't need that. Uh, it will also check some extra stuff like the memory leaks. Then let me hide. And then VT for B tracking. Yeah, I messed something up. This run run on this input. Oh yeah, because sorry now the the program doesn't fail. Uh but normally it will show me a lot of information about what happened. It's just some tool

the university I'll go prep there is high quality. I think it's very high quality. I think that's hard for me to compare it to Warso because I don't I didn't attend Yagilonian but yeah they have achievements so there is nothing wrong with the univers the Yagilonian university DP of zero probability of zero in selected and then the DP parak I don't see I don't fully understand what you're suggesting but Sure. Okay. Uh solution summary maybe uh kind of using examples. There is this sequence that I want. This is task D. There is this sequence that I want to cover and every probability has some probability of every range has some probability of happening. Let's say 0.7.

Maybe this has a probability 0.9. And there are some other ranges. like this one 0.2 and this one 0.2 I always start here and I want to investigate I want to find the probability of covering everything without intersections in this case the only probability for that is that those two ranges happen I do the transitions whenever I see a range I just do a transition so if I start here with probability 1.0 zero. I will transition there and I'm here at with this probability 0.7. Now I cannot simply transition to from here to there with probability 0.9. So I cannot here just say 0.63 and be done because I need to additionally guarantee that those things are not happening.

So the probability of this transition from here to there that's 0.9 multiplied by nope in my code and that's product of probabilities of other things in between not happening that is this thing has probability 0.8 of not happening this thing has probability 0.8 eight of not happening. And in this range, I want probability probability of all the red values. The product of values one minus P. I use prefix product for that. If I know the prefix product up to the end, I divide it by prefix product up to here. Then I will get the product of this range.

In order to divide, I need modular inverse. So I need divide module. Additionally, I need the product of everything up to the end, including possibly some ranges that end here. There are just not the range that I'm using already. So I will include all the stuff that ends exactly here. But I don't want to include this. I don't care that the probability of this not happening is 0.1. I don't care. I I want to exclude it. So this product of a range, I divide by 0.1 because it's unnecessarily used. I'm not interested in it in it. I want the product of red values for the other ranges inside of this range.

So this is the transition. I say dp of j plus equal dp of i times this where n comes from the prefix product. Instead what you could use is for example segmentry that could also give you product of a range. Maybe there are some tricks not to include this single element. For example, if the task said that at every position there is at most one range ending there, then it would be easier to code this because I would take product range up to position J minus one and I wouldn't need to divide. Excluding future segments is wrong.

Yeah. Yeah, Pollock, you're right. Uh we don't want to exclude other things because we can still use them. I want to make sure that every range that I'm not using should be I should uh count its probability of not happening only once. So best way to do it is when you see it as you go from left to right when you encounter it but you're not using

parag. Now I see what you're saying. Actually, I had this idea in my head, but I thought that it's incorrect. I thought that maybe we should focus on multiplying stuff that we're using. And but then the issue I saw is that we have the sum of a lot of things. Let me see.

If I for example here have 0.63 the product of those two values I guess I can also multiply it by 0.3 to say that I'm kind of cancelelling it. Can I do this? So I do transitions by just multiplying this at the end. This value I divide by the product of all nopes. That seems correct because this will be divided. No wait. The divide is stupid. Wait, wait wait wait. I want to at the end multiply. So I think I need to transition with this divide by 0.3. At the end if I multiply by all the nopes 0.8 0.3 0.1 those values will cancel.

I think that should work. And I had this thought I decided it's not correct. So that was in that that was bad. Let's see. So now my ther is we don't actually need this the prefix product when doing the transition I also don't need nope I will just multiply by p divided I have a deja vi uh divided by sorry p divided by the 1 minus

Okay, at the end I multiply this with the product of all nopes. Does it work? I got some negative values. Um, how can it be? Oh, yeah. More move more. Okay. I think it's it's correct. So I over complicated. I mean mod plus is needed because 1 minus p itself would be a negative value. So when you subtract modulo you usually need to add something to make it positive. Okay that's an better solution. I and I'm guessing the editorial should describe that

they have prefix sums products. Here they don't. Yeah, that they start with the product of all the node values. So this is the second solution in the tutorial is my my also second solution. By the way, this it's looks scary. I think.

Um, have I solved the Manhattan pair question? Manhattan pair question. I remember one Manhattan pair question from one of the past few contests. Oh yeah, it was from the division one contest recently, but I did not make a stream on it. Do you mean that contest? Yeah, let's go. E indeed. Okay, last problem for today.

set of integers complimentary sums. If you can do this, choose an array. Calculate the sum s of everything. S minus the value add to the set. Values in the array can be repeated. Count distinct sets of complimentary sums with values up to x. Okay. Uh so not additia. I solved that problem because I was a tester. I have not discussed it during a stream. Maybe one of the next few days I will do it. I will go through the problems all the problems except for the last one. Okay. What can we do here? Um so there is this A1 A2 A3 A4 they have the sum.

Then I'm considering the set of values sum minus a1 sum minus a2 sum minus a3 sum minus a4. If I add all of those so sum of set values is equal four * sum. So n * sum minus a sum because if you subtract a1 a2 a3 a4 you have this. So that's equal to that. Well, unless repetitions the task said that the in set we remove repetitions. For example, this area of size four gives you only those three values.

If not for repetitions, let's see is this set of is if this set valid I will just do something random. 203 what ara would give me that set assuming that n is equal to three. So I guess I can sum this up. The sum of the set is 50 + 23. So 73 that's not divisible by n minus one. So let's modify to this 74. Uh sum of set values is equal to that. So apparently sum of a is equal to 37 and then this is 37 - 7. This is 37 - 13. This is 37 - 17. The sum of those is 37 indeed. Now so 37 - 7 is 30 minus 13 is this - 17 is okay.

So from the set I could get the array because the sum of values was divisible by n minus one. But it's also possible that the set hides repetitions. For example, if this was the case, it seemed that there is no solution. But maybe this actually hides a set that looks like this. And then I care if the sum of all of those is divisible by three. If not, maybe this sum is divisible by four. Maybe this is divisible by five. Maybe this is divisible by six and so on. It seems like almost every possible starting sequence if we expand it like that eventually it will be divisible by n minus one.

Unless maybe those values are very special. If the set of values is simply a value one. Wait, can it be one value? Can n be equal to one? If a is a single element, then the set will contain a zero. Can we have zero?

Okay. If the a array is 1 comma 1 then sum is two minus every element is one. So you will get this. If a is 2 comma 2 then the sum is four minus every element is two and so on. So that resolves this situation. For the second test, you have this. So for some reason the here everything is possible. Here also everything is possible. And here I'm guessing it's not the case. This is just seven choose one. This is just five choose two. And is this 10 choose three?

That's uh 5 * 3 * 8. So 120. No, that's too much. Uh 120. So among 120 possible triples of values, only 34 of them are good. Zero is not allowed by this. Oh, I see that that condition. Yeah, this says that we cannot have zero in the set. Sure. H. Okay. Say that the set of values is one, two, three. Okay. Okay. What if the set of values is like 2 4 6? Maybe that will be difficult for some reason. We want this to be divisible the sum divisible by two. So that's easy. What if instead

Okay, up to this n equal to two everything is divisible by n minus one. So it's easy here it might be not divisible by that but when I have this 24 seven the sum is not divisible by two but if I add another something the sum will sometimes get divisible by three in particular six plus this that's not divisible but then maybe this is divisible by five Sorry. By four. No, it's not. But I can add something else. And now it's divisible by four, right? 10 + 14 24. Yes. So sum is 24. So the a could be 17 17 20 and 22. How could those values be so big?

Something's wrong. Oh no the sum I need to now divide by n minus one. So the sum is 24 over n minus one. So 2 to six. Oh I see. And now things become negative. So the a would need to be elements -212 sorry two 2 4. For those things we have the sum equal to six and six minus those elements will give you that. Okay.

So what's the issue here? After multiplying you want the sum divided by n minus one to be greater than max element or in other words sum needs to be greater than max * n minus one. That seems to be a very strict condition.

sum greater than that is it true right now the sum is 13 is it greater than 7 * 2 no so if I try to already do something with that sum here is equal to 13 / 2 that's 6.5 then indeed I would have the a with negative value So that's uh minus half 2.5 4.5. The sum should indeed be this. It doesn't work.

I'm not participating in the division round today. What I'm going to do just after this uh after this stream is I'm going to watch volleyball because there are today there are finals of VNL the final for in volleyball women edition and in few weeks there should be also finals for Poland plays against Japan and then Brazil with with Italy.

Maybe this condition is very important and it's enough. By the way, when I get to problems of this difficulty at this point, it starts um well affecting my performance. The fact that it's during a stream because here without the stream and without explanations, I could faster go through some examples experiment breaking quant what does it even mean?

Okay. Um, this this thing means that the sum isn't too far away from it. So the maximum versus other numbers there is a small difference. When I repeat the maximum, nothing much changes. But is it true that eventually we'll have this? What about that? I know here the answer for 310. I can implement this check and see what happens. So what if we maybe just this condition is enough. I have no idea.

Iterate triples of elements K is the maximum and I want to check that sum where is it sum greater than this the sum greater than n minus one so two times Max. Most likely this is not enough because it's just a condition that needs to be satisfied. But there maybe there are more uh no inputs 50. By any chance if I make this into a stronger condition, will it fit? Oh, 34. Uh, can I check this here? No, I cannot. Huh? So, is the condition that sum needs to be greater than n minus one * max? And now I hear addit plus one but I'm guessing that maybe this is slightly different like it's actually n minus one or something like that but this happens to work here. What does it uh what this thing becomes when n is two sum greater than max plus one? I don't think it's true. So maybe this is something like n minus two the upper bound x but the elements from the set need to be up to x. The elements uh a can be

anything. My theory right now got gamer. My theory is that I need to count values up to x such that this will be satisfied and I think we will aim at time complexity 200,000 times logarithm. Uh but for now it's difficult for me to explain why. Uh but I have something in my mind. like it will be primes if like time complexity whether we iterate multiples of something about duplicates I have a theory so in Q in the sets that we are investigating there are no duplicates and with some experimentation I saw that for this or maybe that if when we make duplicates this either this condition will not change or it will get worse if I keep repeating ing the biggest value this condition stays the same. So it remains true or remains false.

So maybe just by repeating the biggest value we can always make the proper divisibility. If so we just want values to be non- negative. Actually the values should be greater or equal one right. Uh a values consisting of positive integers. Okay let's let's think about that. Uh

sum of the set values is equal to this. So the sum of a values is equal sum of set values divided by n minus one. And I want every value in a to be at least one in particular the maximum the maximum is this sorry the minimum. So this thing which is sum of a

Let's see. This is equal one of the elements sum a minus a4 is equal one of the elements in the set. So element a4 is equal sum of a minus set 4 for this being the maximum. This is the most dangerous. So then sum a minus maximum inside of the set that still needs to be at least one. If I now plug this here, I get this. So some set uh is greater equal than max * n minus one plus n minus one. I have this. Does it match what I checked here this greater equal the maximum times this plus n minus one which is two I think it's okay yeah let's And

okay, still works. All right, then I'm going to assume that this is correct. Uh, so it's enough for me that I create such a set that what gets calculated as the smallest element in A is at least value one. That's the lower bound. It's absolutely not trivial and not obvious why this is enough and why other elements will not get messed up. Why by repeating the maximum in the set I eventually get divisibility so that those numbers would be integers. I don't care. I just sometimes in the contest you want to assume that the problem is solvable and that your ideas after some time are good enough. Maybe nothing else is needed.

This is that point for me. Uh okay. Now there is it's not a random inequality. This in some way represents uh how far we are. Let me maybe think about an example. If we have few elements and the maximum among them is 10. We want here the sum of maybe 100. We want here the sum of values to be greater or equal than 100 * 4 plus n minus one. So plus 4. So the sum needs to be at least 4004. In other words, all of this all needs to be a sequence of 100s with at most 96 units lost. So we can think that this is by default 100 100 100 100 decrease the elements by at most 96 in total.

Uh and this still needs to be a set right. So yeah the the sequence needs to be increasing. I also see a solution in pos with possible squared in time complexity. Now here comes a trick. If you can decrease by at most this in total, this element cannot be value 70 because if you want this to be increasing, then those previous elements also are smaller than 70 and you already lost too much in total. Actually, let's think about the reverse problem. I'm making a sequence of by default n zeros make an increasing sequence with ties with sum smaller equal 96 assuming that 100 was the maximum also would we iterate the maximum this will be a sequence of how much we are missing up to the maximum uh For example, this sequence, it means that there is one element equal to the maximum, one element equal to max - 3, max - 3, max - 5, max - 6.

So the sum is smaller than the maximum time n by something and it cannot exceed in our example 96. Okay. Now, no squared, forget about that. But there is this property that if you have increasing sequence increasing. If some element is five, then all elements after that need to be five at most as well. Because of that every element at index I you can limit it by the this maximum that you want to remain that you want to get. So 200,000 divided by the index counting from the end because if there are seven elements until the end you cannot exceed max over seven because there are seven elements that are at least you.

Uh so maybe using a simple example if there are five values it's increasing and the sum you know cannot exceed 100 then the value here it cannot be 30 because there would be 30 plus here 30 plus here 30 plus here and the sum exceeded 100. The value here is smaller equal than 100 divided by 4. Here smaller equal 100 divided by five. Smaller equal 100 divided by three and so on. And the sum of those counts is n login. Sum of possibilities is equal n login which will appear I think in our time complexity. And we will have a dp for every position. DP is what is number of ways so far for this element or maybe instead we will think if I put a an extra plus three here actually it gets multiplied by the suffix so I actually have + 12 so it seems we have and the length is there.

Uh, that's tricky. What do we count? Number of ways. This starts as one. And then for every position or for every suffix that is possible we consider what value to put here or by how much to increase this position with this remaining suffix. So everything gets multiplied for now. Let me do quadratic DP. I'm making new DP. Actually, that's not needed, right?

Yes, this stream is supposed to end before the contest, but I don't have enough time to code this, and I don't even have a full solution yet. Also, let's see. So, this was solvable in 20 minutes, 14 minutes. I see tourists struggled with the last problem. What was the pro last problem about some kind of string task?

Okay. Among n positions for each of them you choose by how much to increase. Oh, right. There cannot be ties. You're right. Yeah. Yeah. Yeah. Uh, thanks SARS. I forgot that we are investigating the set of elements, right? So, this doesn't make sense. Uh, okay. So maybe back to the square root thing

actually I'm starting to think that n can only be up to square root because the sum of distinct values something something it will never satisfy this condition. Uh yeah, I think I'm quite confident about that. So n is up to square root

2 seconds. I'm thinking if it's enough here to just in proper order do transitions that look like this. Just do it increasingly I guess. So if there is suffix of size five you can increase it by five. But no, we then don't have any information about increasing. Yes, we do. And we need to increase by at least one unit.

If you see let's say suffix of five elements, you need to do at least plus five here and sorry plus one here and that increases the sum for everything. I'm very close to a solution but I cannot do it in five minutes. Uh that's a pity. Okay, I will open the tutorial uh but only because the contest is upcoming also. Please register for it if you want to. Such a long tutorial.

something something. Okay, I think this is what what I've just done. Yes, prefix sum. I don't know why we use that. And square root of x Okay. So that that's basically my solution. You just need to spend some extra time thinking about the details. Okay. Well, that's a hard problem. Much harder than the previous one. Okay. I I will maybe I will not code anymore. I will for the last four minutes of the stream summarize what I know about the solution with this condition and you should register for the code forces round. We have this condition right? This given nx uh count sequences of n distinct elements that sum is greater equal max * n minus one time plus n minus one.

Okay, this and all the elements uh are up to x. X is the upper limit. Okay, when you have maximum in your sequence, then your sum is obviously limited by this. If maximum appears n times, then you have this and this condition it means that you need to drop only a little bit below the sum. For example, assume that maximum is 100 and is five. Then you have a condition here that sum is at least 404 which means that among your four elements sorry five elements it's increasing every element is at most 100. You need to you cannot even have a value one here because that's already dropping too much from the value 100.

You want this element to be equal to the maximum and the other elements should be nearby. You cannot have a big drop. Let's say this this should be okay. The sum is big because how far you differ from the maximum is small. Let's say by default I will say the elements are 199 98 97 96. This is the uh biggest possible sum already. It's possible that it's too small too small and then you should stop the program. In particular, that will eliminate cases where n is much greater than square root of x because then the answer should be zero because this sum even the biggest possible sum you can get will not work otherwise. So if n is very small uh this sum is okay and you will see how much this is above the required threshold.

Let's say the difference of the sums is 20. So from this sequence you can drop down by at most 20. And what does it mean to drop down? You can decrease some value. For example, you can decrease this by 20 down to 78. But automatically the previous elements also need to be decreased by 20. Maybe additionally you decrease uh both of those by seven. So this gets decreased by additional seven. This by additional seven. always you decrease a prefix by some amount so that you would still satisfy the increasing thing. So you can for example decrease two values by seven or three values by 20 for every i from 1 to n you can what you can do is decrease the sum by some multiple of i and the sum you you have some limit for what the total sum is. It's up to x. You do it for every i up to n which is square root of x and that's some kind of dp.

You start with DP of zero is one and then you investigate DP of sum it's or DP let's say of T it's uh so far like after considering I values some some I values or this number of ways to drop by T compared with compared with max possible sum And this t is limited by in our case 96. Generally it is limited by around x - n minus one. Um okay we don't know the maximum in advance by the way but we should do this without knowing the maximum. And once we know the sum we will know what maximum is possible. So how much leeway we have and I think that's it.

Uh for for each of indices we will iterate from zero to x. Well hard problem but a nice one. Uh well I don't like the statement. It was very difficult to understand and the problem is obviously difficult to solve. So yeah I'm not surprised by this decrease. So like 20 times less people solve this because well this is solvable and this is just a hard problem. Okay. Uh there should be code forces around starting in 30 seconds. Good luck with that. Today or tomorrow I will announce my group classes starting from next month on code forces€ 100 per month 50 per month if you only want recordings and the access and good luck. Contest has started. Oh maybe there's a delay. No, the contest has not started still. Uh, good luck.

See you. Good luck in the contest.

Questions about this episode

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

In order: 0:00 Huawei II camp, Rakkesh, Walerus; 10:00 Jane Street; 20:00 University of Warsaw.

What is mentioned in this Errichto Hard Algorithms episode?

9 people, works and ideas are mentioned, including Walerus, Rakkesh, Huawei II camp, Jane Street, University of Warsaw, ICPC. Each one on this page links to its own page with every episode that mentions it.

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

The episode runs 1 h 32 min; the transcript is about 9,150 words in 94 timestamped sections.

More from Errichto Hard Algorithms

About this transcript: the episode's spoken words as captioned on YouTube, split into timestamped sections. Reclip.Me locates every person, work and idea in the text, keeps the time it is first named, and quotes the words around it verbatim. Last updated January 12, 2026.