Transcript

CF 1034 (Div. 3) | algorithms problem-solving

From Errichto Hard Algorithms · Episode page · Watch on YouTube

· 1 h 25 min · 7,887 words · 78 timestamped sections

This is the full, timestamped transcript of "CF 1034 (Div. 3) | algorithms problem-solving", an episode of Errichto Hard Algorithms published July 9, 2025 (1 h 25 min, about 7,887 words). It mentions 7 people, works and ideas, including Huawei II camp, Discord, top coder, Elite Code, Ahmed El Ahmed.

What is discussed, and when

  1. – 10:00: Discord, Huawei II camp
  2. – 30:00: Elite Code, top coder

Notable quotes from "CF 1034 (Div. 3) | algorithms problem-solving"

  • Also, I already announced the Huawei II camp. So, if you're an IOI participant or coach this year, check it out. It's free.
    about Huawei II camp · at
  • What I did actually in university is just to earn money. I used to problem set a lot for top coder for example. But top coder really they paid a lot.
    about top coder · at
  • Please try solving Elite Code contest once. what I'm going to do is starting from next month I will do that as part of paid group classes. So it will not be public stream for free.
    about Elite Code · at

Who and what is mentioned in this episode?

People

Companies & orgs

  • Discord — Company · 1 mention · first at
    It's not open for everybody otherwise there would be very big range of levels also on discord I cannot make a call with arbitrary number of people stream every day not every…
  • top coder — Company · 1 mention · first at
  • Codeforces — Company · 1 mention

Concepts & topics

Full transcript with timestamps

Test sound. One and two and three. Hi Ahmed. I think we are live on Twitch, on YouTube. Uh, so let's solve some problems. Long time I'm streaming for the past few days. Also, I already announced the Huawei II camp. So, if you're an IOI participant or coach this year, check it out. It's free. And for others well there will be recordings later so you cannot then you can eventually watch that but nonioi participants cannot participate it's it's not open for everybody otherwise there would be very big range of levels also on discord I cannot make a call with arbitrary number of people stream every day not every Okay. But when I have time, when I have time, it will be few times a week. In particular, I think I have time this week.

Uh the IY camp will start on 17th of July. So a week starting from that day, I will not have that much time. In August also, I will do s some paid classes. So I will not have that much time. When I do code first solid code, do you know solutions or how to do it instantly or is it because of patterns? And you can see me solving problems. So you see how quickly I come up with it and I try to say my thoughts out loud. So just you can uh take from that whatever you want. Okay. Uh did I those problems? No, this seems complicated.

So maybe not. What else we have this round? I solved some problems. Skipped one because it seemed ugly. Uh what about this? What is this round? Division three. I guess I skipped those, right? Actually, that one doesn't seem so bad in terms of the statement. Let me read. So, maybe this task. I'm not sure yet. Any suggestions for doing DSA in Java? No. Why I'm don't post on code forces? Uh when I have stuff to post, I do it. We want we have a binary string two players. Alice wants to turn everything into zeros. If Alice cannot achieve that in finite number of moves, then Bob wins instead.

Uh in Alice turn, she chooses subsequence of length K and changes all characters to zero. in Bob chooses substring of length K and sets all to one. So after Bob's turn there is always substring of length K that is all one and Alice what she wants to achieve is that only that thing is that I think intuitively Alice wants to take zeros from the sides. So if there is a string that looks like that and now it's Bob's turn. No for big enough K no matter what he will do he will include this one. So what I will Alice will get is just this thing where there is a substring of length K with only ones and Alice will turn everything into a zero.

Okay, Met Anim streams. Will this problem be on YouTube as a video? Uh, well, not this problem particularly, but the whole stream is also on YouTube. Yes, I am married. Alice starts right. Yes. So I think that we should do something like this. Alice might win in the first move and we need to check that separately. And then a second thing for short enough string. For short enough string, it seems that Alice will take things from the sides because what if for example string length is nine, k equals five and we have this situation where only the very middle character is one and now it's Bob's turn.

One more zero. Now it's Bob turn. Bob's turn. He will include this one. So for sure he will leave only five characters as a one. Uh so this seems to be an important condition. Alice will usually take stuff from the sides and turn to zero. Bob will do it in the middle but without including existing ones. So maybe it's important whether there is a one that is far away from the sides. So okay I have the following uh following lema. If there is at least one one that is far away from the beginning or the end. So for example this this is of length k.

This is of length k and this is a one that is further away. Bob can turn all of that into once and then Alice will turn turn all of this off. Or maybe Alice will turn everything here off. Alice will change this one into this one. Will there be II camp? Yes, I already posted on code forces. Maybe in the chat I will place the link with information. I camp for II participants.

I'm sure that the code for this task will be very very simple. Just few checks. So it seems that it's not very important that this is the one because Alice will take care of it anyway. So maybe it's just a comparison of lengths.

Maybe we need to simulate this game kind of. We need to maybe figure out the exact optimal move for every player and simulate for of end turns. Interesting. I see that the coding tech earlier asked, can we use stacks here? Well, stack is a tool. So, when you see a problem and you don't know a solution, it's usually not a good idea to first think about data structures that you can use. Unless you're speeding up something particular, you already have a working solution, now you want to do it faster. Then there might be a data structure that can do some operation fast instead of doing it linearly with a brute force. But so far I don't have any solution. Maybe I could come up with something exponential but that will not be very useful here.

Uh red I think I saw your message on my phone. I mean on via email or something like that. I will reply to you later, but I'm guessing not. I'm guessing that I don't want to do problem setting for a competition different than big code forces around that I would organize myself.

Well, if the string is very long and there is a single one at least one uh then Bob will do something like this somewhere in the middle there will be k + one once oh actually this is very important can Bob always make a move that such that there is a one that was already existing and it's not included right And if this is the case then it's always possible because we can look if the string length is 10 or maybe let's say six versus three. If you have a string of length six, there is a one somewhere. There is for sure a possible move a range of length three such that we will now have four ones. So there will be a subrange of length three that doesn't include this single one.

Uh Mhm. And now if this is the case, there might be a one here and but after we make a move here, Alice will turn off uh let's see the stuff on the sides. So Alice will leave this guy. Maybe this is turned on. This is turned on. Then Bob will turn this on. Then Alice will turn this off. This off. And no, no, no. Alice wants the middle stuff to stay. I will Alice will turn off this, this, and that. Okay. I'm guessing that it's only now important if string length is greater than twice K. And if so, Bob wins. else Alice wins.

Now, I'm not sure about it, but it's simple to code. So, let's see if it works for the sample test. Maybe it does. And if not, I will not have a counter test, which is also helpful. First, we check if Alice can win immediately. For every character in S, if this is a one, then count plus+. And if the number of ones is at most K, then Alice can turn them off immediately in the first move. So we return Alice. Else we do it based on this n smaller than twice K. else print Bob

maybe I should have guessed the the condition earlier because it's so simple I think very quickly I had some idea to look into this 9 versus five size that this is something special where the middle character matters

twice the number of ones really if what free demon says then my solution is incorrect we'll see no accept okay then very simple logic the the number of ones needs to be at most K or the the size needs to be less than twice K and the reason for that explained as I went through my thoughts but I don't really have a full proof so I think we can leave this I don't I didn't find this problem very interesting should we maybe do this one just to be done with the first with prefix of this contest. But do I want to do that?

Blackboard game. Uh there are numbers from 0 to n minus one. Uh please explain that. Okay. Well, the reason I uh the reason to compare this at all was that if we have string of length six and there is a one somewhere anywhere and now it's Bob's turn. Bob chooses range of size three. K equals 3. Let's say n= 6, k= 3. Then there is this very simple lema or observation that Bob always can choose something that is disjointed with the existing one. So if there is at least one one then Bob can choose a range of k new ones.

So Alice gets k at least k plus one's uh k + one once. So cannot win and leaves at least one one and the process continues because Alice turns off only k digit ones digits equal to one. Uh so this was the logic and this logic doesn't really work if there is a range of size five for example and k equals 3 because if the remaining one is here in the middle then Bob will cover it. So Bob choosing range of size three kind of wastes this opportunity of having a one there. So Bob will leave only the range of size K filled with ones and Alice will be able to turn it off.

So it seems that this one is actually useless. We can treat it as a zero kind of for remaining bits one by one Alice will be able to turn them off because Bob chooses some range of size K and Alice will then turn off those K minus one uh digits. Alice will not care about this one. So actually only K minus one digits and one more digit something from here. So eventually she always will negate the move of Bob. Ignore the middle digit and instead of that turn something off elsewhere eventually we will be left with this single one here. It's Bob's turn. Uh he will paint something. There will be K digits one. Alice will turn them off and win. That's the explanation.

If K is greater than N / two, maybe you wanted to say smaller. Yeah. Uh yeah, Red, as I said, I will reply to you later, but I don't think I'm interested. There are many contests out there, and organizing any contest, creating problems, it's very time consuming process. I do it like once a year or something like that for some big Polish competitions and that's enough for me. Uh what I did actually in university is just to earn money. I used to problem set a lot for top coder for example. But top coder really they they paid a lot.

It was close to $1,000 for creating a full round and it was just a few problems. It wasn't that difficult. Wait. So, oh uh we have not solved this problem yet. Let let's look at it. Blackboard game numbers from 0 to n minus one. Alice chooses an integer a on the blackboard and erases. Bob chooses integer such that the sum module 4 is free. So like zero can be paired up with three, one with two, two with one, three with zero. Determine who wins. I'm not fan of these kind of problems because they are just about math analysis.

But if n is divisible by four or actually n yeah n divisible by four then numbers will create perfect pairs and Bob can always respond for example zero they will he will respond with three three he would respond with zero one respond with two two respond with one so then Bob can always respond and eventually Alice loses so Bob wins And otherwise I believe that Bob will run out of responses. Does it work for samples? Uh Bob wins for four and 100. Yes, that works. So int n read. If n model of four is non zero print alice else pop what I'm using here is called turnary operator if this is non zero then do that otherwise this okay

topic required in beginning to increase rating. Solve problems at your level and see what topics you encounter. Yes, if n model of four is zero then Bob wins. That's exactly the solution. Okay. And just to get this those five problems all of them. What is this?

Yeah. Short red. Given array of distinct integers, you can choose prefix and replace everything into the minimum value of that prefix. I guess and choose suffix and change into sorry and change everything into the maximum you can choose the entire the entire array for each element. Check if Oh, you don't change everything. you you erase. So you erase everything except for the minimum or everything except for the maximum. For every element check if you can do series of operations to get only this single element.

I'm guessing from those answers that the answer is monotonic. So it's true for some prefix and then it's true for some suffix. That's my guess based on that. I'm not sure about it. I think so. Please try solving Elite Code contest once. Uh what I'm going to do is starting from next month I will do that as part of paid group classes. So it will not be public stream for free. Maybe I will get back to streaming some stuff about D code problems. Not in the next week. Stop repeating your questions. I told you solve problems at your level and you will see what topics are there.

Okay. How do we achieve stuff? So the minimum in the full string or sequence can be achieved because you just choose everything. You say I'm changing that into the minimum. This is the maximum. Okay, here's my guess. I I I'm too lazy to analyze stuff, but I think minimum and maximum are possible and maybe just everything after maximum and everything before the minimum. I think it works for those samples. So, I'm not going to think because guessing properly and using intuition is also part of contests. I'm just going to code this idea of mine.

There can be ties. No, it's distinct integers. We need to find the minimum. Uh let's call this m. If minimum is sorry if a of i is smaller than minimum then this is minimum. If greater than maximum then this is maximum. And I wonder what happens if minimum is to the right of maximum. But I'm guessing that then everything will be possible. If index is smaller equal than minimum or greater equal maximum then print a one. Actually you can just print this. It will print a zero or one.

So I think here it's worth even in a contest I think it would be worth submitting this without thinking because there is a chance that it works and you save a few minutes of thinking time. It doesn't work. So I think it's time to start thinking yes they can overlap then my solution I think will just print only once one test case n equals five for uh let's say three five four 2 one yeah only once okay I did something wrong so So I think we need to analyze that.

How do we achieve the two? So why is this possible? That's because for everything here we change it into the minimum. And then this guy eats that minimum. So what about this? A number is good. If we collapse everything to the left into the minimum of it, we collapse everything here into the maximum because why not? Then we want to win with X. So X

or maybe I think X needs to be greater than stuff on the right. are smaller than stuff on the left. But isn't then this equivalent? Not really. But here's the thing. If x is greater than stuff on the right, so let's say x is six and there is bigger stuff like there is eight but this is here. Then applying minimum here will eat the eight as long as there is something small here like a two. So here we will survive. Applying from the left minimum again doesn't make sense because two will eat a six. But applying max from the right we compare with this.

So I think what we want is AI to be greater than suffix max on the right and any other condition and also it needs to be greater than prefix min. If this is true then we can succeed because the minimum changes into prefix changes into the minimum. We get rid of bigger values here. And now we apply the max on everything. And we want AI to beat the suffix. And in the prefix just bit the minimum.

I think that's it. So I'm going to compute prefix and suffix minimum for that I'm going to read from one to n because using such indices is actually more convenient for prefix and suffix stuff as you go from left to right you want prefix minimum pref I minimum of pre of a i and previous pref The first pref is some kind of infinity.

And now go the other way. Soft box. That's done. And now I want to write this condition. If I is greater than both suffix max of i + one and prefix min of i minus one. If this is the case or something symmetrical, I will try to do it symmetrically. uh smaller than

I think it's simply this. So if this then print a one print a zero. Not sure, but I'm going to run it on samples out of bounds. We want to do this from one to n because that's the indices I actually use. now works for the sample test and again I would say worth submitting because if something is wrong I I cannot fix that in a minute it means that it's possibly very wrong

if you think it's incorrect it should be like that let me analyze again I want Here I will change the prefix into the minimum then what suffix into the maximum and then by doing step prefix or suffix operation I want this to win. So it needs to be extreme. It needs to be greater than both or smaller than both. And I think this is exactly what I'm doing.

There might be other ways to implement it. There is point or time penalty in the round. So does it make sense submitting sub problems without proof? I mean it makes sense submitting greater equal but there are no ties.

Yeah. Uh to answer the strategy question, uh well, almost never you want a full mathematical proof because it takes a lot of time. So it's a tradeoff of how close you want to be to a full formal proof. And here I decided to be very far away from it. And now you're saying that there is penalty and so on. Yes, but also spending more time on a problem will decrease my points for this problem and everything forward and all the following problems. So I I would argue this uh so maybe first observation Every minute extra spent on problem A costs more than a minute spent on problem E, for example.

Because spending extra time on problem A moves or increases your submission time for all the following problems. It doesn't matter what is the score of problem A versus problem E. What matters is that here you decrease your points for the problems A BCDE E FG. And here you only decrease the points of problems E and onward. So maybe EFG. And because of that usually what I do during contests is I actually take a slightly bigger risk submitting or solving easy problems. Also because since the problem is easy, it's more likely that my wild guess turns out correct.

Train to make correct observations. Solve problems. You will learn patterns this way. Learn how to make observations. The stream today, by the way, will not be very long. I will finish in 40 minutes.

Is it optimal to do something else? Wait. If AI is smaller than the prefix minimum, so like this, then we can apply the operation of applying minimum. Here we obtain a two and then we collapse this into the maximum and we have then two numbers and depending on the comparison between them we will either do the minimum of them or maximum of them. So actually if this is smaller than that then we always win always. So I will say if ai is smaller than prefix minimum or greater equivalently to suffix maximum or now is this stuff necessary?

Don't we repeat this stuff? I think maybe we need to now remove that and just go with this. Well, now during a contest I think I would think a little bit more because getting multiple penalties that starts hurting and also I spent a lot of time. Oh, but we passed test two so I think we're okay. Yeah, I over complicated the problem. So it was simply this is equivalent to saying AI is prefix minimum and this says AI is suffix maximum because if any of those is the case then such prefix or suffix you can turn into just this number. the remaining suffix or prefix you turn into something and once you have two numbers left you can choose any of them to be the final one just by applying minimum or maximum okay I think that's done and that's uh the end of code forces division 334 I will read this statement but I don't think I will do it permutation GCD of I and PI greater than one.

So it's like some kind of matching. It's not necessarily matching itself, but we want to pair up values from one to n such that they have a common divisor, but we try to avoid pairing a number with itself. I would call that a constructive problem kind of. It's even marked as constructive, but I don't know how difficult it is. Anybody recommends it? Solve F2. It's pretty easy. How is Mman BVim Mar doing these days? Uh, he's fine. He doesn't do competitive programming though. Okay, we can try that. But I might give up.

So basically we have we have numbers from one to n. Pair them up or create pairs. Actually we have indices and the numbers have two sequences of numbers one to n create pairs between them. So basically matching every pair needs a common divisor. Minimize the number of pairs x comm x. For example, if we have those numbers, I want to pair them up. Seven needs to be combined with seven and five with five. Those are primes. So, I cannot do anything about it. Uh, one, what about one? We don't care about one. Okay. Now, two, three, four, six. I think two combine with four. four with two, three with six, six with three. So now I achieved that with just two bad places and I cannot do anything about it. And there is also a one,

one two three four five six. Here they combined everything except for the five which is the prime uh 13 13 11 7 they are impossible. Everything else is possible. Now what should be the logic? So primes at le primes greater equal n /2 are alone well greater than n /2 depends on how you round

because those they there is no second prime that is there is no second number that is divisible by this prime. For example, when n equals 100 and you look at a prime like 53, nothing else up to 100 is divisible by 53. Hide dead.

So maybe always everything else we can combine into pairs. Three four five. here. I think it's true. It's true. Well, here it's also true if we return over to as a real value. Maybe we'll start from highest primes. So iterate primes up to n /2 decreasingly for each collected multiples that are not used yet and use them. I think we will always have at least two. That's my theory because you will in particular have this prime and this prime times two because it wasn't analyzed yet and maybe some more. For example, if n is equal 100, when you get to a prime equal to say 11, at least what you will have is 11 and 22 and maybe some more.

Why do you have those two? because you did not yet get to prime equal to two which would also see this as the multiple. If P is seven then at least we will see seven 14 and so on. If P is two then at least we will see two and four and eight and so on. Now to combine them into pairs when you have for example 7 14 and 21 let's say you can say that seven matches with 14 14 with 21 with with seven like it's a cycle combine something with multiples except two I think that we don't need to do anything special for it

So yeah, I will do exactly that. Do I need prime? I might be useful. Is prime of n + one. by default filled to true for every value up to n. If is prime then iterate multiples. This is false. Okay, we have that. And now iterate primes decreasingly. In particular, automatically I will see which ones do not have anything to match with. And now I will have a visited or used array here. Collect stuff to something like that for every multiple again. No, only do that if prime for every multiple including this number itself.

If not visited yet, then visit add to the vector. Now I collected all unvisited multiples of this prime and now I'm going to merge them into a cycle. Answer of V of I equals V of I + 1. This is some kind of vector for one. The answer is one. And I think we can just print it.

And we didn't read. Two goes to four, four goes to two, three goes to six, six goes to three, five goes to five. That's reasonable. Try submitting. So the problem indeed was quite easy. I think primes if might not be necessary, but I think primes is not really harder than finding divisor in square root. So I'm fine with this. Anyway, the main piece of my logic relies on cif like logic. So as well I can earlier repeat that thing where I iterate primes and I iterate the multiples. I don't think I could have coded that in significantly shorter way so that I would code for more than one minute less.

Now in this division three, we solved everything except this. But I think the last problem in division three might be very annoying and very standard. I will read but I'm almost sure that I will not did not understand line 10. Line 10. Well, this is prime. Look look up this term prime tutorial or something. Let's read G.

Assign a single value like that. Increase something plus K model M. M is given. Check if you can make a nondereasing. I think that gcd of k and m will matter a lot. In particular, if the gcd is one, then you can do whatever

The limits are very low. 100,000 and the time limit is big. So I'm guessing already that the Oh, M is big. Uh what was M the model? I'm guessing that we might need to use square root decomposition. If you started today, how fast would you become legendary grandmaster? If I started programming, if I if I was very good at math already, maybe four years, if I trained a lot. No, I I think that's not true. If I only now started programming, it would be more than five years.

Okay. So if GCD of K and M is one then we can do we can achieve everything and the answer is always yes we can do it. For example, if we do things modulo m= I don't know 10 and what we have is k equals 3. Then by increasing something by three we modulo 10 we will go through all the values out there and eventually cycle back to zero. So by adding three we can change a value into anything we want. Oh I have an idea. We will investigate all the divisors of M and for each of them we maintain something. No matter the value K does not matter that much.

The value GCD of MK matters. The exact value of K does not. The values of GCD the possible values are only very few. So for each divisor of m and only all those can be gcd we maintain a data structure. Now I think I understand why the limit is the time limit is big. The constraints here are small because number of divisor of m is relatively small. Usually we assume it's cubic root of of the number. The number of divisors of m is roughly cubic root of m. It's not actually it's not correct thing to say but for the sake of competitive programming we can say that it's good enough estimation.

But what is proof of what? The the claim is if you can increase by k mod, you can achieve everything with the same divisibility by gcd. That's let's call that basic algebra. For example, if m is 10 and k is eight or six, I achieve that starting from any number, you can reach any number of the same parity. For example, if you start from three, you will get all the values that are odd. If you keep adding eight modulo 10, I don't I guess you can analyze that using ukidian algorithm or something like that.

timed out in pi for me. Well, in non in non-trivial problems, I think code forces only officially guarantees code forces solutions to work. Other languages, you're on your own. Now what if this GCD is not one then for every element its value modul that is important and its comparison to the next one is important. So let's say that GCD equals five or 10. I think 10 is a great example. If GCD is 10 and the first number in the sequence and M is equal to something big say 130 doesn't matter. If the first number in the sequence is 27 then actually we can think about it as a number seven.

So if then in sequence A we have 27 in my data structure I will actually have a seven because that's I decreased it by 10 multiple times. Then let's say next we have 59. I decrease it to nine. Say that next what we have is in the input sequence 32. I decrease it but not to two because that would be decreasing. I increase I decrease it to 12. Uh so always it's important that here we have this drop. This had bigger value modulo 10. So for fixed GCD it's very important if AI model GCD is greater than AI + one model GCD. If I see this situation, it means that I need to uh like jump to the next multiple of 10. Like those values, they were in range from 0 to 9.

And here the values will be now from in range from 10 up to 19. And I have only 13 such ranges. If I start from values that are in range from 0 to 9, I cannot exceed 130. So later if after 32 I have something with let's say eight as a second digit I will use here 18. So I'm still at the same first digit the same multiple of GCD. But if this instead was something one some two-digit number with a one next I would need to jump up to 21 so that it would be greater than previous element. So I'm going for every GCD, so for every divisor of M, I'm going to keep track of the number of places where this happens.

I think normally during this stream I would not code it, but I will at least finish this code forces division 3, so I think I'm going to do it. Uh okay. So summary for every divisor of m uh which is possible. So this divisor is a possible value of gcd of m comma k for every divisor. What I do is maintain the count of places where this happens. And then for a query compute the GCD of MK. And for this divisor for which we maintained check the count of those places the thing that you maintained here you have access to that in constant time.

And what do we do? um we check if we have enough. So check check if this divisor multiplied by places doesn't exceed m maybe maybe smaller equal let's think uh so like let's say that m is 30 then how much I can afford I can afford one increase and second increase and no more if I have three then I lose so it needs to be smaller 10 * 2 smaller than 30 10 * 3 not smaller. Okay, that's the solution. Is any guy rated smaller than 1600 expected to solve it in the contest? Well, I I don't fully trust those difficulties, but if this is 2100, then this is significantly above your level if you are below 1600.

But also uh the if there is a contest and there is last problem they try to make it in such a way that it is a challenge for the best people for the top few who officially participate and are allowed in this contest. So you know 99.9% of people are supposed not to solve it and standings should reflect that at least the official standings if we exclude people outside the division three. So here what we have is that 30 people solved it among how many participated 15,000. So, you know, 99 uh point something% did not solve.

Also, some people might have their rating too low because they didn't participate in enough contests yet. For example, this person, if you look at the rating graph, most likely we can guess that he will keep climbing. So, actually his current rating is undervalued. undervalued. Okay, let's code. Let's code exactly this logic. What do we read? NMQ the array. I will use indices from 0 to n minus one. Then there are queries.

If type is one then read the index and the new value. Decrease the index by one. A of i becomes x. As the type is two. And what do we read? Okay. Okay. Uh divisor for every value from one up to M. Well, K is smaller than M. So M itself shouldn't be considered. Can M be one? No. If M model D is zero, divisor push back M. not D. Now for every divisor or maybe I want to first verify my solution for samples with a brute force. So actually what I'm going to do here is D equals um GCD of MK. Does it compile so far? Yes. Uh I'm going to verify using this. So count those places

fi modulo d greater than f_subi + 1 modulo d. If this is the case then count ++ and what divisor count times count smaller than m. Uh just in case long long I'm not sure about the overflow here. Print a yes. Else and no in just one minute I think I coded that I can verify if my logic seems okay and then how to do it fast I will do separately. Seems fine. Now sometimes in some competition it competitions like Olympiads it makes sense to submit this code because you will get uh some feedback some verdicts on small tests but in code forces usually you will get time limit exceeded on test two and you will not get much information from that.

Uh what do you think about the rating of division three problems and so on? I have no idea. I would really need to spend few hours compar comparing a lot of problems and then uh I would could tell you what you can do if you want to really analyze it and compare the difficulty of division two versus division three problems. If find people who are participating in those and like in all of those compare their solving time. Most people solve problems one by one from left to right. So for the majority you can see how much time they spent on a problem and you can check if 1600 rated problem in division 3 took the same num the same amount of time for people as uh 1600 pe uh problem in a division three or division two.

It was always enjoyable watching your stream without understanding it. Maybe one day you will start understanding them. I did math in childhood. I didn't do programming in childhood. Okay. So we passed the sample test, right? So let's now do it fast, which is I want for every divisor to maintain this information.

for every divisor. Let me maybe go full screen for a moment. count plus equal this count of that divisor or answer for that divisor. So it's premputed and now after we have a modification I need to do this. If now I I need to update how I interacts with the next uh index. If i + 1 is smaller than n, then I need to do exactly this with a minus. Before the change and after the change add it back. Additionally, if I minus one is greater or equal zero, then for every divisor, what I need to do is cancel the influence of AI minus one model D greater than this.

And after the change, I add it back. This way you basically avoid ifs for what was the comparison before versus later. I'm not saying this is the best thing out there, but it's something. Now I'm not going to here count it again and again. I'm going to just say answer of answer of the does it still work? Also, I should have copied that previous code with that so that if I get wrong answer, I can stress test. I do that during competitions. When I have a brute force, I copy it to another file because it might turn out useful later.

Missing your dog. The dog is there running on test eight. What's up, dog? Why number of divisors is roughly cubic square root? Oh, interesting. Uh ham. There is no explanation. That's not scientifically of or mathematically true. It just happens to be a good estimation for values that we use in competitive programming. for values are up to million or billion or 10 to 18 it's a good estimation but that's it no limit on sum of m then again second time during like three days I lost because I focused on the single test case okay then let's I think I'm getting time limit exceeded because of this and if that's the case what I want to do is first of all create that answer array once instead of multiple times here for every divisor answer of the set to zero initially and finally I cannot afford to do it again can I do it in square root I think I can right 10 4* square root of that uh yeah that's less than 10 to the 7.

Okay. So here I think now I now this became square root of M in time complexity not O of M. So for big M it's not that single test case is so slow. Thank you Jeron for telling me the reason for this time limit accident.

I just store all divisors globally. That's all that's actually what I wanted to do just before thinking about this. But if possible, I want to do test cases independently. I think that this is slightly safer than doing it outside. Well, it's not really significantly better. Yeah, I don't think one method is way better than the other. uh but we have accepted 1 second out of five. Instead of this I could also in main run prime save all divisor that's m log m memory which sometimes is an issue. Uh also when you push back to vectors you have twice more memory. So you know this much time log of it times two times int.

How much is that? And some people define int long long. So it will be times long. This will be 20 million times in 80 megabytes. Then that's okay. 80 megabytes doesn't exceed 250. But you know it's not far away from exceeding that. Also out of memory does consume some time. So if this was 1 second then I would worry about only this prep-processing part already taking significant amount of uh the full time. The complexity is that let's analyze the time complexity for a single test case. What I have is of n plus square root of m. I read n stuff. I in square root of m I do the divisors.

Then here I have n times the number of divisor. And then there will be q also times number of divisor. So n + q times number of divisor which roughly should be estimated like that. Uh there is gcd computed here. So q gets multiplied by logarithm but that's smaller still. Well log of something. I don't care. I often in competitive programming most of the time you shouldn't even analyze its Q of it's logarithm of what because it doesn't matter here I think it's logarithm of M that being said you're wasting time by thinking about it it's logarithm whatever maybe it's 20 maybe it's 17 and Q * cubic root of M is greater than that part so this part kind of you can skip Uh so you have this per test case and you are guaranteed something about the sum of n and q. Uh this gets multiplied by the number of test cases though.

So it's of t * roo<unk> of m plus sum n plus sum q time cubic root of m. That's the full time complexity. Shaam Mario, you're asking hard questions. I don't know. I don't know how long it would take to become expert if you're not good at math. To be honest, I don't know if maybe better question would be what percentage of people would achieve that because if you're terrible at math, if you're very bad, you're just not talented for math, then most likely the answer is never. You will never achieve expert.

Why there are few women in CP compared to men? Maybe many of them do not even attempt it. Uh I will not explain the GCD again because this is a harder problem, not a good one to practice this property of what happens with increasing by K. It's some kind of math, some kind of algebra that property with GCD. uh generally if you if you didn't know about that GCD thing then this is generally a problem that is too hard for you but what we achieved is yeah the green color that's that's nice to see I don't know when I don't long sorry I don't know how far I would need to scroll to see that I mean if I scroll very far if I get to contest where I actually practiced a lot then I'm sure we will see a lot more of that color six problems when did I practice a lot also I need to go around 500 round 400.

So this is roughly when I practiced a lot. Well, there is a lot of blue like soft three out of five. Four out of five. Four out of six. I didn't absolve enough. I would say that's bad. I expected a lot more of the green color, but it's nice to sometimes see it. Oh, I was second. I thought that I was second once contests and it wasn't after sort by rank. I was second twice. I was third three times. I was fifth four times. It's so sad that I was in the top 10 so many times and almost all of that is division one and I never won.

And and here I lost by one minute. Look at this. Uh with this guy, same time. 6 minutes. 6 minutes. 18 minutes. 18 minutes. No wrong attempts. 333. And then we attempted two different problems. Each worth the same amount of points or number of points. 129 130 I lost by one minute and because of that I will never win a code forces round because now I'm like five years after my prime I I'm too weak now my chances are very very very low I'm I'm sad about that

so close that that other contest where I was second after Omni. I don't think I was particularly close. Well, he would need to not participate. That's it. Okay. Uh I need to finish the stream because I have something at half 3. Uh sorry, at 4 p.m. So I don't start again. Uh thank you very much for attending the stream. Next one. Either tomorrow or in two days. Why you think your prime is over? I'm weaker now. I don't practice. Do you want to show your face to the stream? No, you're shy. Maybe next time. Okay. Uh see you everybody. Thank you for attending, watching. The II camp is already announced on code forces.

Questions about this episode

What is discussed in "CF 1034 (Div. 3) | algorithms problem-solving"?

In order: 0:00 Discord, Huawei II camp; 20:00 Elite Code, top coder.

What is mentioned in this Errichto Hard Algorithms episode?

7 people, works and ideas are mentioned, including Huawei II camp, Discord, top coder, Elite Code, Ahmed El Ahmed, Codeforces. Each one on this page links to its own page with every episode that mentions it.

How long is "CF 1034 (Div. 3) | algorithms problem-solving"?

The episode runs 1 h 25 min; the transcript is about 7,887 words in 78 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 24, 2026.