Transcript

Token Removing & CF 1036 (Div. 1 + 2) | algo problem-solving

From Errichto Hard Algorithms · Episode page · Watch on YouTube

· 2 h 4 min · 12,429 words · 117 timestamped sections

This is the full, timestamped transcript of "Token Removing & CF 1036 (Div. 1 + 2) | algo problem-solving", an episode of Errichto Hard Algorithms published July 7, 2025 (2 h 4 min, about 12,429 words). It mentions 11 people, works and ideas, including Codeforces, Jane Street, Lead Code, Raja Zikas Shabu, Jet Brains.

What is discussed, and when

  1. – 15:00: Jane Street, Jet Brains, Lead Code, Raja Zikas Shabu
  2. – 1:45:00: Huawei
  3. – 2:03:51: Lead Code

Notable quotes from "Token Removing & CF 1036 (Div. 1 + 2) | algo problem-solving"

  • And there will be Sunday evening lead code classes. So that's some update about that. Like every stream I'm mentioning a little bit about it.
    about Lead Code · at
  • Nothings so far or equivalently number of tokens we ate your Jane Street t-shirt I love. Do I have it?
    about Jane Street · at
  • If you say so. But I'm not sure if maybe it's from Jet Brains.
    about Jet Brains · at
  • And yes, I part-time work at Huawei.
    about Huawei · at

Who and what is mentioned in this episode?

People

Books & papers

Companies & orgs

Concepts & topics

  • CND — Concept · 1 mention

Full transcript with timestamps

Sound test. One, two, three, and four. stream will start soon. Why doesn't it load in code forces? Hi Sheab. Strange. Maybe link is incorrect. No, it's correct. H. Right. Uh, we're doing harder problems today. Division one problems. Starting with this one. Token removing. Hi. Just Just give up. I'm not going to read your full full nickname. Hi, Akash. So, still nothing. Strange.

Raja Zikas Shabu. Welcome. Please solve some 2,000 traded problems today. I think I'm going to. Or do you mean that you want at least that difficulty or at most that difficulty or exactly 2,00 start time? Oh, in UTC. Strange. We also yesterday's contest, not the full contest, but if you think there are some particularly nice problems.

Yeah, I don't know what is up with this. Okay, so the token removing problem. Why is it not saved? At least 2,000. I see. CND were nice. Okay. Still, uh I promise to first solve this. We'll see. We'll see. Also, I have some small update. I decided what classes I will do next month. If you're interested in that, you might consider it. It's not published yet but uh in August there I want to do two groups of paid classes both about dynamic programming. One will be easy group about problem solving. So that you would be able to solve every easy problem and the this is a group for people who only know how to solve few of easy problems uh already and they struggle with them and second group will be about harder techniques like broken profile, divide and conquer DP stuff like that.

Um yeah so this is the plan I think. And there will be Sunday evening lead code classes. So that's some update about that. Like every stream I'm mentioning a little bit about it. Uh because every stream I have decided something new about it. Okay. The token removing the task said that there is a sequence we consider a sequence with numbers that satisfy some inequality and there is a process described. At the end we care about the number of remaining tokens. We want to sum up the that value over all the possible sequences of length n.

And what what was m module. Okay. And what else is there? Yeah, I will just draw it. Is it a free class? No, it will be this. This thing will be a paid class. 200 something euro €250 for that month of uh classes twice a week.

Okay. Just making sure everything works. number of ways to remove tokens. Yeah. Yeah. Yeah. Z, you're right. I I would This is how I remember that. So, this is what I would explain in the drawing. Anyway, do you plan to start doing code first contest regularly? Not regularly, but I hope to do it from time to time. Uh, no. A drawing.

So this is what we have. Uh we think about a sequence of numbers from 0 to n or actually from one to n. At every number there is a token. Maybe let's do it from one at every number from one to n there is a green token initially and in order from one to n what happens is we're given some range this range is from ai to i. So the range always ends at every new position position three position four five six 7 and so on and we are given its start as element of the sequence. We can eat or kill some token inside of this range.

At the end we care about the number of ways to remove tokens. So in if we start with let's say this blue range we have three ways to eat a token then we have the yellow range we have one or two ways depending on whether the blue token already ate a token or blue range whether it ate this one or not the third token uh the question is given a sequence how many ways there are to do a sequence of moves and then we want to sum this up over all sequences. Can I start combinative programming at 32? Yes, of course you can. But if you're not already good at math and programming, you will have a hard time.

But if you treat it as a hobby just like you would do know u I don't know sudaku then sure just treat it as a hobby not as something where you need to excel at and be the best in the world. Okay. Given a sequence can we compute the answer? No. I'm not vegetarian. Why don't I use X over Y sale? Why should I use what you're saying? To be honest, I don't even know what that is. Tyling WM.

Okay. Also numbers can be zero but let's say they are not. If a of one is one then we always eat token one. If a of two is one then we eat token two. If a of two is two we also eat token two because that's the only one available. Something else happens. If a of one is zero then eat nothing. Then a of two is one then we would eat one or two. If a of two is two then we eat two depending on also a of two can be zero depending on which of those two options happen happens then for a3 for example equal one then that's always two ways so what this means is I want to eat a token from range of one to three there are always two ways because always some token is eaten.

But if we have this, so we eat something among tokens two or three, then it depends. It depends on what happened in the previous step. And it seems to me that it's very important how many times we ate nothing so far. So I'm guessing that in some way this will be DP of position and number of nothings so far or equivalently number of tokens we ate your Jane Street t-shirt I love. Do I have it? This is an ICPC t-shirt and I don't see Jane Street logo. Maybe I just don't see it. Or are we talking about a different one?

Quan finance via competitive programming. I think so. I think you can do it. But I'm not an expert there. So this this thing it can always eat a three. It can sometimes eat a two. It can sometimes eat a one

after this problem. I will you were looking that wearing that yesterday. Oh the yellow one. Uh, is it from Jane Street? If you say so. But I'm not sure if maybe it's from Jet Brains. I'm not sure. Okay. From Jane Street. Got it. So the yellow one actually I most almost wear u I almost wear it again today. Every morning I go for a walk with my dog and I actually wear a t-shirt from yesterday. After that I get a shower. I didn't have much time today in the morning. So you would almost see me twice in a row in the same t-shirt.

Uh probability to solve problems declined. Yes, I think so. I don't practice that much in particular. So I think that I was for example extremely good at geometry, handling precision errors, stuff like that. I would not make any bugs and now I'm way worse at geometry.

Let's say that we have a range of size one. Then size two is skipped. Size three is skipped. Then for the size four we have something like this. Let's say then for size five by size five I mean a range ending with a five we can have few possibilities. So we can have this range, we can have this range, this one, this one, this one. And actually here the one is always always eaten. So there is no difference between those two. Uh this one is most complicated because depending on our choice here something else happened.

This statement of summing up possible ways is equivalent to counting the number of sequences of pairs. Um, count sequences of pairs of the AI comma the actual token that you eat. Let's say token of I. This means in the if move which token you eat. the statement could just say could just say count the number of such sequences of n pairs. So it seems that instead maybe I will focus on in every operation which token is eaten and then I will sum up the number of ways to choose AIS. So I will not think about ranges too much.

Instead what I'm going to do is say for example maybe in the first move I'm eating this token in second move I eat nothing in third move I eat nothing. So like token zero in fourth move I can eat one of those four and for each of those like maybe this is what I eat in the fourth move. If so I multiply the answer by three because this is the number of places where the range could start. So the here because of this guy I multiply the answer by times one. This one I multiply by times three. Uh then there is tok then then for the fifth move I eat some token. Maybe it's for example this one or maybe this one.

If I go with that one I multiply the answer by time four. So the statement said among all the se sequences of ranges sum up the number of ways you can choose which tokens to eat. And instead I'm doing over all the sequences of which tokens I eat sum up the number of possible sequences of ranges. I will go back to answering questions later. Also, was code forces finally fixed in terms of this? Still nothing. Do you see my stream when you Oh, now I see it. I mean, it's loading. It's loading. Okay. Works now. Oh,

so this it seems seems that no matter when I eat this token, the answer will be multiplied by time 4. So I can alternatively say that at any moment I eat those few tokens, then there are 12 ways to choose where the corresponding ranges start. And there is another question of those tokens are assigned to what moments. So maybe we will do DP going from left to right. Uh so not by time not by so not by the index from the problem statement. Instead I will go this way and for every token the first one, second, third and so on I will decide if I ever eat it or not. Depending on that the answer will multiply by this. And additionally, I need to keep track of how many ways there are to assign this to some moment of time, which means and there are always that many ways to do it.

So I think we will go from right to left because if this token is assigned to some moment. So this is token number four it's eaten in the moment from four onward but it's eaten by one of them. Then for this token number three it's eaten at moment one of those except for the one that this one chose already. Right? So uh this one has some suffix size and we multiply it. This one has some suffix size and we multiply by it minus one because of this guy. And I need to know how many other tokens are already eaten. So I'm going to I think I'm like a little bit more than 50% sure about the correctness of what I'm doing.

uh we with DP iterate tokens from N to one. This is not the index from the statement. This is the token position on this axis. For every token, decide if it should be eaten. If so, multiply the answer the DP value by this is prefix size multiplied by suffix size minus number of previously eaten tokens. I think this is what we do. Uh this will be a DP dimension.

This is very easy to implement. So sometimes after coming up with such an idea, I would analyze the samples to figure out if it makes sense. Maybe I want to analyze uh the this n equals 2. Yeah, let's do it before I implement. But uh if the code is short enough, sometimes in a contest I would not even look at samples. I will just code it in five minutes and that's it. But here also for educational purposes, let's try to or for you to understand my idea better. Uh if there are just two tokens and I'm looking at initially DP of zero is one. This is number of ways to eat zero tokens. Then I'm looking at token token two. I assume n equals two.

I can eat it or not. If I eat it, I will multiply the answer by two. So I think this was what will happen. This is prefix size. This is suffix size. Right? So for this token prefix is of size two. Suffix is of size one. Then when I look at token token one now dp of 1 plus equal dp of 0 * 1 * 2 this is now prefix and suffix the other way around but additionally dp of 2 plus equal dp of 1 * I think 1 * 1 or this is prefix size and this is suffix minus one already eaten token. So what do I have from this? I have dp of one is two.

Uh from this I have dp of two is just increase by two and after that I'm doing this operation obviously uh dp of one it was two and plus another two it's a four. So now I have one plus two plus four. It seems that's a seven works. Let's code it.

I think it's a quite nice problem. Not very easy to explain like if you don't feel the solution, it's very hard to get to understand it. Uh after I'm done coding if I get accepted I will explain again. So we move backwards some kind of well where token is

and always I decide to eat this token or not. I iterate the number of tokens already eaten. Better do it decreasingly. And I decide to eat it or not. Een plus one plus equal DP of I will add modulo in a moment. DP of E10 times. If I decide to eat this token, I multiply by the prefix size, which is this. and the suffix size which is I think that minus the number of already eaten also sanity check uh so like a check that make sure or helps me checking if the plus minus one is okay eaten is n minus token at most so n minus token minus ethan will be zero at least so this will be at least one makes sense also dp of ethan doesn't change we can decide not to eat it. So it's just this at the end print the sum I will add model in a moment

737 273. Great. Uh now modulo This is not the most efficient way of applying modulo, but I don't care that much about the runtime. Uh, doesn't work. It worked. Wait, wait, wait, wait, wait. I'm doing something stupid. Oh, my my answers are shifted by one. Why is that? So, it seems that for one, the answer is two. I'm tempted to just do n++ or n minus minus. How many problems have I solved till today in my life 3,000

they update DP1 after updating DP2 uh because of the order they affect each other here. So this is how you I didn't explain it but I wanted to save memory. I didn't want n squ memory even though I maybe it would be okay here. Uh what happens here is when DP2 affects DP3 and DP1 affects DP2 at the same time like simultaneously you need to do them in this order. If you first did this then DP2 would already be modified. uh even though you should simultaneously consider that when you consider token n simultaneously you need to update all the DP states. So without having a second DP array or an extra dimension this is the order that you need to do it. This order does not matter if you have an extra dimension.

That being said also this is not even though the code is short this is a hard DP problem to come up with. So, it's not a good one for you to learn about tricks like this. What is the level of this problem? I don't know. 2,00. It's to avoid saving the eaten dimension. It's it's to avoid having a full DP of position and eaten. I erased this dimension and I just have DP of Ethan. Okay. Why is why is this

in particular? I analyzed what will happen for n equals 2 and my program does not agree. Am I tripping or did I see this video before? Uh did you also see your comment inside of the video? Yesterday we started solving this problem but I said after a few minutes that I'm leaving this for a division one stream. So for the harder stream AI will surprise humans in problem solving. Yes.

Okay. I mean, so during a contest, I think what I would do here is I would do this run. It's correct. Submit. But I do not understand why would I need to do it. I I want to understand before submitting. So I just see that my answers a moment ago were shifted by one compared to the correct ones. Uh I think maybe I want to print some debugs.

Maybe just around. 1 200 token one did not do anything. How is that possible? Uh the prefix size is token not token minus one. But why would this work at all? Oh, I think I see why we have one empty iteration where this is zero. Oh, so simply the token equal to one does not do anything. We only iterate from n to n uh sorry from n to two basically suffix size is not affected to the prefix size I decrease by one. Okay, the last iteration is empty. Now I understand uh for you it's not that important to understand my mistake. It's just stupid typo slash mistake. If you are at position five the prefix size up to it is five not four.

Now I can submit and I can explain again. Also a look at the editorial. Calculating the weight of a single valid sequence is difficult. This is what I thought that this might actually be easier when we sum up over everything.

Well, not obviously. Okay, this is a bad editorial. Uh, okay. Accept it. Now, let's let's talk about this. I will for a moment hide my camera. Well, not necessarily. So the full solution to the token removing the task asks us for something quite complicated slash convoluted. Uh what happens here is we have positions from one to n. So one two three four and so on and and uh we consider some sequence that defines ranges to us always every next range it ends at the next index. So first range needs to end at one second range needs to end at two third range needs to end at three. The start can be anywhere on the left. Fourth range ends at four and so on. Some ranges are skipped. For example, there might be no range ending with five or maybe no range ending at three.

But then maybe there is range ending at five. Maybe not. So for every position there is a range ending there one one range or maybe there is no such range at all. Now in order of those ranges from left to right so ending with one two and so on uh we will eat a token inside of a range and that will always be possible because initially we say that there is a token at every position from one to n. So first we look at this blue range from one to n and we eat any token inside there that must be this token. Then we look at the second range from two to two and we eat any remaining token inside that would be this one. Then the range ending with three is skipped. Then we look at a range ending with four and we see that we have actually two possibilities of which token to eat or remove. So we have two ways to do it. We remove one of them and depending on that we can have different number of ways to continue in

the future with future ranges. And the task is among all possible sequences of ranges in the statement they are defined by the sequence A which is not in the input. We consider all possible sequences A. Sum up the number of ways to eat tokens. So a sequence saying in every move which token do you eat? Now I'm going to I'm going to write this in equivalent way. Among all possible sequences of tokens to it sum up the number of possible sequences of ranges. This is well same thing in both cases like let's say one number of ways gets multiplied by the other number of ways uh so we work with this and when you know that some token is eaten so among the tokens when you know that let's say this token is eaten the token number three where could arrange start.

Well, the blue range needed to start at this position or this position or this one. If it starts in any of those, it has a chance of containing this green token at position three. Where can it end? Well, at this position, this one, this one, and so on. So, roughly the number of possible ranges that start on the left and go to the right is equal to the prefix size multiplied by suffix size. So that's token index multiplied by n + one minus token index. This is the formula roughly. But there is one more thing we the statement defined that the ranges can start anywhere on the left as long as the start point is to the left of end point or exactly at the same spot. But the end point are end points are distinct.

If there is a range ending with four, there cannot be another range ending with four. So what I'm going to do here is say well yeah if there's such a token the number of possible end points here is suffix minus maybe I will get back to this simpler format prefix time suffix it's suffix minus the number of already decided ranges that ends to the right. decided end points on the right. So here because maybe here in the suffix we already decided there are some two ranges that end there then the number of ways for me to choose the end point now is suffix minus two.

If we go now from left to right uh deciding what to do with tokens and multiplying the answer by such product. So here again minus decided outputs. If we go from left to right, we will not be able to know by what to multiply because if we know that for some token we decided the range that starts here and ends somewhere to the right. Maybe here, maybe here, maybe here, then for some token in the future like a token here, we will not know if earlier we decided that the endpoint is to the left or to the right. going from left to right, we have no way of keeping in just a single dimension of DP information about where exactly the end points ended. So that for the following tokens, we would know how many available end points are to the right.

But this is viable if we go from right to left because if for a token you have any range that contains it. So it might be this range, it might be this range, it might be this range. If you have any range, you know that for the next token, for this token, if you know that there is some blue range, then for all future tokens on the left, for example, for this one or for this one or for this one, for each of those, you know that some one endpoint on the right is excluded. So then the decided endpoints turns into just number of ranges used or number of eaten tokens.

going from right to left. So the token go iterates from n downwards to one decreasingly. That's important. It will not work the other way around. At least I don't think so. So the code is that we do DP uh and we need to know the number of eaten tokens. So this will be a DP dimension. We go from right to left and we have something like DP of position or the token and number of eaten already. We start by saying let's say DP of N or N plus one uh with zero EN is one. This there is one way to be at token N plus one or to be at token N uh with zero EN tokens. In my code, you will not see this dimension because it's very common to skip the first dimension, the one about index uh to save memory and do improve the runtime a little bit. So I just have this but I start from token n and I go decreasingly and to look at my code again the code is obviously very short like it's usually the case with DPS. We start by saying DP

of zero tokens eaten is one. There is one way iterate tokens decreasingly iterate the number of eaten tokens so far and we do it decreasingly here because the transition here is like that. So if you did this increasingly then for example DP of three would affect DP of4 and after that DP of4 would affect DP of five and so on. So DP of three would immediately affect DP of five. This would be equivalent to allowing allowing us to eat multiple tokens at the same position as affecting from this DP this DP immediately looking at a single token. It would mean that we pretend that we eat two tokens here because number of eaten jumps from three up to five. That's not allowed. Hence I do this decreasingly and this would not matter if I went with two-dimensional DP.

Uh and the transition is that from DP of Ethan I transition to DP of EN plus one and I multiply by the prefix size times the suffix size minus EN already. I mentioned something about the modular operations not being efficient here. Actually I do here three modular operations. Well, you could do it with two, maybe even one, which would be a little bit faster. Does not matter. In some problems where you really optimize for runtime, you should avoid many model operations because they are slow. Hello, Ronaldo. Okay. And I think that the editorial in this task is bad. So, I now understand why people yesterday suggested this problem and said that they do not understand it. Maybe I will cut this part of the stream and put it separately on YouTube and link in the editorial or something. We'll see. Any questions?

New person in competitive programming. Uh made an account four days ago. I was wondering what are the best tips you could give uh so it can get better. Uh I have two tips for you. One is search for YouTube Eric how to start uh this thing watch that maybe you have done this already. And second is read the competitive programmers handbook at least the first chapters which is possibly mentioned in the video. I'm not sure if that's the case. So, this is the video and oh yeah, it links here the book. So, there is a free PDF where you should at least read the first few chapters legacy problem from code forces. Is it the one about portals?

Yeah, it's a nice problem. I taught it multiple times during some camps. Maybe one of them was recorded and published to YouTube. I don't remember. But I agree it's a nice problem. In particular, it's possible to do in single logarithm uh and where there are portals from range to range. So some hard follow-ups and there are multiple solutions. Yeah, you're welcome. Uh toot shoes. So what now? We should continue with the contest from yesterday. I saw a mention of CN D. And now regarding this, so to finish with this problem, I think I I would enjoy solving this problem in a contest. I'm not sure if it's a good problem to be covered during a stream because the statement is so complicated that you need more than one one minute to explain it. And if somebody is joining a stream, they will have basically no chance of following up quickly, following along quickly.

I'm from Poland. Future of CP, I don't know. Online competitions will not matter too much. Yeah, Tahassin. Uh maybe one day I will cover legacy. I will okay skip let's see what this is. Subset multiplication the kind of division one a problem. Alice has an array with n positive integers. A i divides a i + one. So most of the numbers will be equal to each other and sometimes there is an increase already. So without reading the rest of the statement I can tell you that this might be important property because if you have a sequence where every next number is a multiple of the previous one maybe with equalities then every time when there is an increase it increases at least twice.

So there will be at most logarithmic number of increases. So and other than that it will be sequences or ranges blocks of equal values. So property of something like that will be you will have at most logarithmic number of blocks of equal values and between them big increases. Uh of course during a contest you shouldn't stop and make such observations just after the first paragraph. You should know the full problem. But I'm already tell I'm already betting that this will be important. Bob sees uh the beautiful array and is jealous to sabotage.

Uh he creates array of size n. So the same one bi equals ai. Then he chooses a positive integer x and multiplies some elements by x. Uh so some elements he multiplies by the same value x. You're given an array B. You don't know AR A and the chosen number X. Please output any integer X that Bob could choose. uh so that multiplying some subset elements and so okay you're given an array elements that is not necessarily of that property that every next multiplication of the previous one and you need to multiply some no you need to divide some elements back by x to get back to the property.

Well, either this is already a good array or you can see at least one drop not drop one not satisfied property where there is no divisibility and here you will have limited number of candidates of how we divide the previous number so that uh there would be this sequence would be good. That's one possibility. The other I'm tempted to say that we should do it greedily. Uh going maybe from left to right seems stupid because this is good and then you look at that and you cannot drop it because this is 42 already. Maybe we should go from right to left and every following number drop just a little bit if needed. So going from the end let's say at the end I see a number of 100 before that I see 50 this is okay but before that I see 70 versus 50 is not good so I should divide 70 I want to divide by seven so 10 now 5000 I divide by divide by x= 7 I can modify the future but then let's say I see 10

I see then here let's say 140 this will not work but 140 if I divide it by seven it's not enough to fix I need to divide at least by 14 but that means retroactively I need to do some modifications on the right I spent 90 minutes on the first problem just to realize that my solution that I made in five minutes was correct That happens.

Yeah. So that's my idea. Iterate backwards and keep expanding this number x that you divide by. uh when you see that something is bad, you need to increase x to something bigger and this will happen again only logarithmic number of times because every time I change x into its multiplica into its multiple I can go decreasingly again from the right and this time use this value of x

and I easily apply the division if it's needed. We're multiplying the bop multiplied. The task here I think is that we are given a sequence that is already multiplied. some elements are and we need to divide it back and for such a problem especially because it's relatively easy if you look at the full contest right among the how many eight nine problems it is it is the third one usually ideas that I have initially like intu intuitively work so I'm not going to analyze this further this is not also during a contest I would now code I'm going to uh read the values. X is initially one and while true iterate from n minus 2 down to zero.

If ai and what do we output? We output the value of x. If a i + one modulo ai is not zero then ai + one sorry ai I want to divide by x unless it's not divisible. If ai modulo x is not zero then this is game over. I think assert false I think that shouldn't happen. If I see runtime error, I know that my this piece of my logic is incorrect. Otherwise, we divide by x. And if still this is not the case, then I need to divide ai some more. But by what? And this will not happen too many times because this increases the value of x. Also every time I want to restart a so every time I remember the initial sequence and every start I every time I start from that initial sequence.

Now if this is still something then I will do stuff finally if I equals zero. If I equals zero then output the current x and return. What do we do here? We see for example that there is 70 and after that 50 I need to divide this by something extra by a divisor of this of AI that is not a divisor of 50. So I think we will hear iterate like that. If a i modulo d is zero and a of i + 1 mod d is not zero then multiply x by that and break finally it's possible that

it's possible that I don't find anything because here I only find uh divisor that are not equal to AI. Maybe I need to consider AI already. Uh finally if not done assert not assert I want to do this and just break down that I hope that this will not overflow but if I don't have mistakes it cannot overflow and do I need to consider other divisor like those form ai over d. I think that always here we will multiply by some prime and primes will be found this way. Well, let let's check what happens. Does it even work for the samples?

Assertion failed. Also in the first task we print one that is correct. In the second we print 512. That's very suspicious. How many zeros are here? This is half a billion. This is 1 billion. Why do we go up to 512? A I divide by GCD of two consecutive values. I don't know maybe just remember that I do not want its time limit exceeded. Why? I claim that what I typed is of log of values multiplied by n. This is how many times I can iterate and also every such iteration might end with square root of ai. Unless there are multiple test cases, each of them has a small n and I try to factoriize something. Oh, that I think kills me. I focused on solving a single test case fast enough, but there can be multiple test cases each with a huge value.

So, I cannot do it this way. I need to be smarter about it. Uh so I need to find now now I understand the comment or hint from earlier and I'm not happy about it. So again please do not give me hints while I solve problems. Yeah, I need to like for those values 70 comma 50 I need to find some part of this of the 70 that is not inside of 50. The common part is GCD so 10 and if I divide this by GCD I will have what is left. So common is gcd of a i a i + 1. And if I divide like that, this is the extra value I need in x also the code is shorter. Let's see what happens. One, two, six.

I don't know. You don't you don't get penalties for incorrect submissions on the first test. The values seem reasonable. Oh, and now this comment is obviously incorrect. It's N plus I think log from GCD. That's a big runtime. Is it because of reading the ink? No, not really. Interesting. Do you think problems have become tougher to avoid cheating during contests? No, but they became a little bit stranger to maybe avoid cheating.

Uh yep. Can you do B from yesterday? I think I will move to D. So I I will move to harder problems not easier. Every I try every second stream to do division one. So harder problems and like yesterday on Sunday I did easier problems. So yesterday I would do B. Uh, one more thing. I want to look at the standings, open some submissions in the top, and see the runtime because I'm curious if my if my 1 second is unusual.

200 200 okay I I over complicated right oh we don't need to go again then again I see so I have the unnecessary logarithm what I did is I every time I go backwards I have some current candidate for x and if it doesn't work I modify it instead you could just once go from right to left this is the bad thing. Okay. So you see how much AI needs to be divided by by how much it needs to be divided and then you update answer accordingly. You increase answer up to this value. So for example, if you see that you look at AI I + one and you see oh AI needs to be divided by 14 at least by that and if you see that answer is at already four but sorry answer the X value but you know that you need to be able to divide by 14. So this needs to increase to something that is also divisible by seven. So you modify this up to uh well 28 and the exact logic of this I think is this line where the answer gets multiplied by h divided by gcd of them

so 14 * 4 but there is a two in common so divide by that okay makes sense I over complicated the solution though after one incorrect attempt at least in my head uh also there was some logical mistake. Sorry, implementation mistake because I printed 512. Yes, that's least common multiple. I confirm. Okay, let's move on. Uh, next will be problem D. Make a poll. I'm not sure if I like it. Yes, Ukidian algorithm is how you do GCD, but you don't need to think about it if you have a function anyite. That's a nice way to put it. LCM of all required X that works though it's not trivial that it works.

That's modifying X at one position doesn't mess it up for the other. Okay. D. Um, you're given an array and an integer. What you can do is select a range of size at least K. Select an index within that range. Okay. Smallest number out of the subarray then delete it. Check if you can get a pollen. So the statement is you are given an array and an integer k maybe given a of well one to n and integer k. You can repeatedly choose any range and remove k smallest value. So the cave smallest needs to exist. So the range needs to be of size at least K.

And the question is can we obtain polling array? Well if K is one we can do whatever we want. Why a pal? How does it matter? very small values will remain. It seems also at the end you will have at least k minus one values. So in particular k minus val k k k k k k k k k k k k k k k k k k k k k minus one values smallest ones in the full array they need to remain so they will be part of the palindrome. It seems that everything else you can as well erase. So my observations are the k minus one smallest values will remain uh values tied to k minus first smallest might remain because this is not very well defined values greater than k minus first smallest I think we as well erase because they might help us create a palindrome but their positions need to be symmetrical and if we remove them then what remains also is symmetrical.

So I think those we can just erase. So make a copy of the array. Uh sort it. This way you find the k minus first smallest value. Everything that is strictly greater than it erase the values smaller than that compared to each other. They need to be symmetrical. And now you have some values equal to the k minus first smallest. And among them you can remove some of them. You want at least k minus one to remain and you want the remaining sequence to be symmetrical. I can't understand k smallest number to solve this problem.

If you say you cannot understand this definition then this is not a problem you should attempt. Okay. So there is a sequence. First step you raise the bigger values. Then you have some values smaller than that. K minus first smallest. And maybe they will look like this. Two three. Two three. If you see this situation, you can immediately stop because they are not symmetrical compared to each other. They do not create a pendum sequence. If they are like this, then there is hope. Now remaining values are all tied to that k minus first smallest.

Let's mark it as x. You want to remain remove some of them. And I think it's quite you you can erase any one of them. You just choose a range containing it and you say this is the cape smallest. I wonder if it ever makes sense to choose bigger ranges. I think in my logic in my head I always uh choose range of size exactly k and I just choose the I erase the maximum value there. Yeah, not sure but my guess my intuition is that it's good enough. Uh didn't know that C++ multi set doesn't have uh log order statistics.

Yep, it doesn't. So what we need to obtain here? Well, we have those smaller values that need to remain. So in this case between two and three, nothing is there. So those elements we would need to erase. If there was if there were extra x's here, those we need to erase. So I look at what happens between every two consecutive small values and I need to make this sequence of counts or block sizes symmetrical and this way I will get to know how many numbers will remain and I check if the at least k minus one values remain.

I think that's it. So solution Let x be k. Wait, k or k or k minus first. I think it doesn't matter. Uh k minus first. What if a one? Let's say cave and the logic will be that in particular we can erase all the values equal to it. Cave smallest value in the sequence. Erase all values greater than x. Um find values or maybe collect values smaller than x and check if they make a palindrome sequence. If not stop. Um what remains is count values equal to x between the values smaller than x and make that count sequence pindrome by removing some values equal to x. Check if at least if the number of remaining elements is at least k minus one.

I'm not sure if this is a correct solution, but it looks like a solution. Sometimes that's good enough. I'm making a copy of the sequence. I will read the k smallest element there. So position k minus one in the a sequence. I'm going to erase all the values greater than it. Uh so make temporary vector for every element in x. If it's smaller equal than every element in A, if it's not greater than X, then push to the new thing override and don't. This is a trick that you can do if you are not going to use a variable from now on. If by mistake I use this variable, for example, a print n, I will get a compilation error saying variable don't use n does not exist because I overwritten the definition of a command n because from now on the n is not up to date. Of course, what I could do is this but it's also a little bit dangerous because n is different from the initial value.

So instead, I'm going to say I think I'm not needing n from now on. If I do, I will think about it. Very new problems do not have difficulty assigned. Okay. Now what was next? Uh collect equal values. No smaller. If smaller than x then equal push back this element and check if equal is a pindrome. For example, reverse equal is not equal to return false. Let's say that my test case function will return yes or no. And I will print the answer here.

Okay. Additionally, I want to count I want to count values equal to x between of them. So blocks or sizes. If element equals x then the most recent block++. If smaller then blocks push back block and the block becomes zero and at the very end I think blocks push back block. So in particular we have stuff before the first element and after the last element. If there are no values smaller than x there will be a single zero here. No, it's a single value this. Okay. So this way in blocks I counted between small elements how many elements equal to x there are for example it might look like this. So let's say there are three values of x then something small values of x something small uh single x this a lot of x's this a lot of x's then I count blocks is three then two then one then four then five and now this sequence I want to be pendroic as well so those two values need to be equal those two values

need to equal and so on. Uh so I let's maybe count how many I want to erase. Erase plus equal the difference of blocks of I blocks of this the opposite ones. So first with last, second with second last and so on. This is how many you erase. You also erased stuff that is uh greater.

Yes, I think so. Now I think that maybe we shouldn't have done that. uh if this else erase ++ and now I need to check if the original value of n actually I'm going to use it if n minus erase this is how many numbers remain if there are at least that many of them and we return yes or no I I don't think this will be fully correct too many guesses. Well, the sample worked. That's something.

I'm streaming in adventure game category. Really? I am not. I feel bamboozled. Okay, accept it. Okay, so I'm happy that I had good intuition and good guesses, but it would be hard for me to uh maybe really thoroughly explain all the steps of this intuition. I will not solve CSS problems today. My approach was iterate over the array from start to end from start to end end. If we find mismatched pair, erase the larger one. If we have at least K elements than that we find mismatched pair, erase the larger one. I don't know why, Sash, what you described works.

Okay I this sorry I wanted to show this uh I opened the link with PNG. What? I'm I'm Twitch decided that I'm streaming again. of education. What? What is this? Having done some terrible things in his youth at school do something. So it's it's some kind of video game and Twitch automatically understood that I'm streaming that. Why is this education so stupid? So I chose some category here. How what's what people do what they use for coding.

Those are I think there is no category here right. It seems it's also incorrectly assigned. Well, software and development. Can I choose that? Okay. Software and game development I think is what we want.

Okay good. Oh man. Time out. recurring with recurring villain of the stream. In some I don't know TV series about superheroes stuff like that, cartoons, movies, you will wonder why the superhero will fight the same enemy again and again instead of just killing them or something and instead they just put it they put them in jail and they they escape. So maybe I'm doing kind of the same thing with this guy. Instead of banning him already twice, I have put him in timeout for stupid comments and repeating stuff. I I seem weaker physically. What happened?

I'm not sure I was ever in better shape, at least in the past five years, than I am now. So maybe it's this t-shirt. I started CP around 15, but I did math for many years earlier. Uh so what how long is the stream already? Hour 20 minutes. I think we can try this one at least. I want to read. We'll see if I want to solve it.

by the way. Uh is the zoom in code forces enough for everybody? I have it at 125%. Sometimes I do it like that 150%. Is it significantly better for like for anybody here if I do this? I don't know how much of full screen you're using when watching me. So for me, it's anyway huge. I I I could I could put it down to like 70% and I would see everything. U 150 better. Okay, I I will keep at 150. Two people quickly said that it's better.

Make it zero. You're given an RA. You can do the following operation. Code versus is so much about those operations and I understand that this is how you can create a lot of problems but also it's it's then never a beautiful statement actually I don't like this about ad coder either they have short statements but so many times it is you're given a string or sequence and you can do operations like count the number possible target sequences I don't No, you need 130 IQ to reach specialists. Maybe you need to practice and maybe you will get there.

Select an array B of same size such that every element is limited by the element from A. So the given array is limits. There exists an index such that prefix equals suffix. Then subtract BI from AI. So you need to decrease the array A. Every element decreases a little bit and there needs to be prefix and suffix such that you decrease by the same amount.

it's possible in at most 17 operations. So they needed to specify that so that we wouldn't have doubts about the output size. So in every operation we decrease some AI values. There needs to be prefix with sum of decrements or decreases equal to the sum of in the in remaining suffix. What is the proper word here in English? Is it decrements, decreases? What word should be used here?

What if a of one is equal to something big and everything else is one in particular? What if this is the case? I think I misunderstood the statement. I don't see how to do it first this sequence. Oh, there can be the answer can be negative one. Okay, got it. Um

in particular if there is value greater than everything else or everything after that this seems impossible I think we can kind of think about it as matching where let's say that the values are 375 Five. The three from here will be matched with three from here. No, not exactly. This has bad parity. Let's go with this. It seems that uh maybe I want to visualize such a test. If I have a sequence of 376, I would think about it like this. We have three tokens or boxes balls in the first place, first index, then seven, then six.

And we do a matching that looks like this in this case. Now I I combine things into pairs. Why? Why is that? Because every time when I decrease by some stuff such that prefix equals suffix, there is this middle point and everything on the left is equal to stuff on the right. So I can combine this into pairs. So I think the answer is pos the solution is possible if and only if we can do such a matching. So it boils down to the sum of values is even and the greatest value is not greater than the sum of everything else.

I think that's enough to check in particular this is even this is even this is odd and additionally this is greater than that. So samples are weak. I think this should be broken into two separate test cases. one where both values are even but one is greater than the other and separate where it's about the parity. So like n equals 3 and the parity doesn't match. AI reach top 200 in leaderboard. Impressive. Now minimum number of operations.

I wouldn't be surprised if the S value is actually at most two. So here we need to do the split by this position and by this one. And isn't that enough? Shouldn't I? If if this task if it wasn't E, if it wasn't letter E, if instead it was like division 2 C, then I would already start coding thinking that what we need to do is we need to find what prefix of this sequence is enough to reach half of the sum of all values and then we will do one split here and one split here. So the sum of this prefix will be matched with some stuff from here and the suffix. And there also needs to be split here so that this remaining part will be matched with something on the right.

Apparently it's not that simple. Unless let's look at standings. If maybe some people solved it in five minutes. No. Tourist 10 minutes. So it needs to be harder. Answer is equal to one only if uh there is exact split of prefix equal to suffix.

Do you believe E is easier than D? Well, if my idea is correct, then yes. But I don't believe that my idea is correct. 17 so heavily suggests logarithm of n also n is up to 50,000 they wouldn't use 50,000 if the solution was that simple here I came up with trivial linear solution there there must be something else to it

so med uh I think that the answer is -1 if the sum is odd or there is a value greater than the sum of everything else. Cute duck. I agree. So, can somebody give me a counter example to what I'm saying? My I'm 80% sure let's say that it must be incorrect because it would be too simple. My solution is find the split of the input sequence into two equal parts prefix with suffix and suffix with same sum and then just split once to the left of that value and once to the right of that value. Uh and the answer is one or two depending on whether there was a perfect split.

Do I like thinking? Yes. I think it's very correlated to living. And yes, I part-time work at Huawei. It's a small B2B cooperation. It's not even half time or anything like that. My question was more to somebody who can analyze what I said. Uh

I think I want to read the first sentence of the editorial or something like that. So hint zero Solve the n= 3 case first. I think I know how to solve it. With two operations at most observation seems wrong. Can you give me a counter example or explain why it's wrong?

Showing the dog part of it. It was correct. The answer I mean at least this part the answer is negative one. One or two. So was my solution correct? Okay. But this means that what I said is incorrect. Find the construction in three moves then optimize to two moves. 532. Well, for 532 there is a perfect split. And in such a case I would just split like that. And I would say decrease by five here and by 32 here.

My dog has a bowl of bowl of water in the kitchen, but he so much likes fresh water from the shower. And sometimes he will just come to the bathroom door and whine that he wants to get there. And what he actually wants is water from the shower. But what I said immediately gives me two moves. I don't have this. Okay, I'm going to code it, but I'm so confused.

What I have expect is wrong answer on test two. Come and visit India. I was there twice, I think. Why is N so small? Such a strange problem. If sum is odd or big is greater than everything else, print negative one.

I don't play much chess. the split logic. Well, I want to split the sequence into equal prefix and suffix. So now for every element increase by this much. If prefix times two equals the sum exactly, we have a perfect split and we will be able to do it with a single operation. What do we output the value? So just outputed the sequence

also if this is already too much then I should have just stopped. So there is prefix of 0 to i minus one. There is suffix of i + 1 to n minus one. And the element I will belong partially to one half and partially to the other half. And I need to figure out how much belongs to each half. that depends on the difference between them. So I can say maybe let's go back prefix minus equal AI. This is what is on the left suffix is sum of everything minus the prefix. So now this is suffix to the right from I. This is prefix to the left of I. There is some difference between them.

Let's make sure that I can do something like this. I will do it by doing what? Three. Three. In order to guarantee that this is equal to that, I first need to match a little bit of the middle with the right part. How much though? What I want is let's say prefix plus ai equals suffix. This is what I want to achieve. For that I can match some part of ai with some part from the suffix. Let's say

no in order to achieve this I can match those. So uh initially this is slightly greater than suffix and by assigning one unit of here with one unit of here I decrease it by two. So what I want to match first is the difference of prefix plus ai minus the suffix divided by two because by matching a single pair I decrease this value by two one from here one from there this is how much I want to do assert in particular first cannot exit this first cannot exit that now I'm going to output that So for stuff up to the current position which is I

um print minimum of First I want to decrease by that much I this is how much I use. So minimum of the value I'm looking at and how much I want to decrease by is what I use possibly zero also a of let's use a variable for that I print that the remaining I decrease by it a of J I decrease by it remaining now should be zero I print first once more and this is by how much I decrease AI itself for remaining positions I don't do anything with them right now I need to output two because I will do two operations and now I achieve that so what I F or maybe achieved is prefix plus ai equals suffix.

Let me hide the camera suffix. So now what we want is just well output everything. J Prefix. Prefix. I used pref. remaining versus A of J. Which one is an int? No. Is this enough? One, two, three, negative one. Why am I printing so much? What is the input? One, two, and two. Something is wrong with how many test cases I'm solving.

If AI is greater than prefix or AI is greater than suffix, answer negative one. Uh no. Why? Like 253 is solvable. Oh, after this I need to return. I'm solving the same test case more than once and sometimes it will be absurd what I'm printing. Okay. 1 one then it will be 4215 and we will have a match. Okay.

What is this theme in sublime in genie? This theme is called monai. Genie monokai theme monokai. this one. It's warm, colorful, and pleasing to the eyes. Well, I'm so confused by this problem because I think that it is easier than D. I mean, I would solve it in a contest, I think, easily within 10 minutes. So, I'm surprised that people in the top spent 15 minutes Strange. Of course, it happens. Maybe I just got very lucky with my idea, but I spent more time being confused than actually coming up with a solution. And the code is simple.

Well interesting. I think that uh judging by the number of accepted, the next problem is significantly harder. Also, we are nearing the two hours of a stream. So, I think we will wrap this up now. Just let it accept it. Good. I particularly like my final explanation for the first problem from today, which was token removing. Good forces. Token removing. So, this one. So in some way I will put it on code forces info about what time stamp you can watch it. I think it's significantly better than the editorial one. Please do the stream tomorrow. Uh let me see.

I will keep alternating between division two and one. I think that the next one I will do on Wednesday maybe. So, Wednesday division two stream. I think that's a good idea maybe here blocks. So Wednesday July 9, and that will be I wonder if this morning time is good or not. I feel like later is generally better, but I feel productive enough in the morning. So, I wonder actually what do you think is the best time? Maybe I will share I I will think out loud and you can tell me if you see any flaws in that logic or I'm missing something.

Best time for streams. Question mark. So I live in Poland and when I do it in today I started in the morning and that was my 9:00 am Polish time. This means in the Europe in Europe it's morning in for example India it's afternoon noon just after the noon uh more to the east like Vietnam or something like that China it will be afternoon in the US it's night in the US it's midnight uh on the west coast on the east coast it's 300 a.m. So this is Europe morning uh India noon uh far east so for example stuff like Vietnam roughly in that geographical area uh afternoon I think during summer when a lot of people will have different schedule this is fine but I would guess that during normal months it's a very bad time because those people will likely be in school or job. So I feel like in weekdays this is not a very good time.

Yeah, starting 8 in the morning is not a big difference. So let's say 8 is equivalent to 9 or 10. Then the alternative is let's see the alternatives this Europe noon India afternoon Vietnam China stuff like that but I don't think China watches too much of YouTube or Twitch evening and it's it's a beginning of viable time for the US but not yet so on the east coast or some part of Canada. It will be 6:00 in the morning. At the end of the stream, maybe some people will join. It seems that if people work from the morning to afternoon, this might be a little bit better for maybe somebody in Europe who wants to do it first thing during a day.

But on the east, this will be better because you're more likely after the school university job. Then what we can also do is this and that's Europe afternoon for at India this plus depending on the summer versus winter it's either 3 hours and a half difference or four hours and a half but roughly let's say it's this and Vietnam China late evening then In in the US, it will be somewhere between 6:00 a.m. to 9:00 a.m. depending on the region. That seems to be superior, right? No. In the second case, India is India is three hours and a half or four hours and a half depending on the time of the year.

Uh and finally I'm aware that I could do this but uh it has disadvantages to me but let's so let's say this is Europe evening India late evening Vietnam night US morning noon uh I understand how this is convenient to a lot of people for example for those it's it's roughly okay uh that being said it's inconvenient for me for some reasons. Uh so first sometimes I will have stuff to do around that time like I will go play volleyball but also my wife is home and I want I want to spend some time with her or just seeing friends.

So I don't want to do regular streams at that time if possible. Yes, I agree. Don't master that this thing in places like Vietnam will be midnight. In China, it will be even later than that. It's at least plus six hours. So considering also my schedule, I would say that this time is superior. Yeah, I got married three years ago and but thank you. So, should we try doing this tomorrow? For me, the argument for the morning is that I'm never tired in the morning. Almost never. So, I have a lot of energy and will to do something extra. In particular, the stream is never something I need to do, right? In the afternoon, maybe I will be busy or tired after doing other stuff, usually job related, and I might not want to stream, but still this seems superior.

Maybe superior is too strong of a word, but it seems best. So, do we have the winner? If so, let's try that tomorrow. Oh, and weekends are different. Yeah, on weekends, but also on weekends I cannot do regular streams because my weekends are not that regular. Uh, okay. So, what I think we want to do is 3 p.m. Oh, I know another argument. This is closer to a possible code forces contest, but the code forces contests are not that common. Yeah, that's fine. Uh, okay. Time and date announcer. We are in war. So, I I am tomorrow division two. I usually do for 90 minutes.

Oh, I modified something else. Division two and what will be next? This is not Wednesday. This Oh, I cannot do it on Wednesday. Let's go with tomorrow. And I actually chose tomorrow. Then we'll see. So, see you tomorrow at 3 p.m. Polish time. And I will try to prioritize this time slot generally for the streams. I will stream more this week. I just don't know yet. I have some stuff on Wednesday and Thursday. I'm not sure about the time on Friday. It depends. Well, we'll see. How big is your monitor? I can barely see the text.

Uh well I wonder if this matters. So starting from couple of months ago I actually have a huge monitor 32 inch and it's 1440p but wait does that matter in terms of this? Oh yeah I I see it does matter. Okay. Well, I will usually open code forces on 150%. But I need to keep in mind that because of that I need to have the zoom in bigger. Maybe also on Genie I need to increase the font just a little bit. Though this seems already quite big. Hello Ahmed. Okay. So, it's everything. The font seems fine. Good. Ok. I I think that almost for every threshold you need to solve a lot of problems around that difficulty and in those problems you will see the topics that you encounter.

Uh okay I will start uh sorry I will finish the stream same way I started uh so talking about the classes I will have next month and that's I think here I will find it okay so this is a work in progress announcement it's not posted yet I will do dynamic programming classes in August twice. It will be twice a week and it will be in the morning Polish time I think. So I will think about it. One group will be solving easy DP problems. So if you know already how to do something very simple like computing n Fibonacci number but generally you struggle with DP this will be a class for you. In particular, we will solve a lot of even new original problems, variations of knapsack, problems with two or three dimensions. So you would get uh efficient with that a lot of solving problems. And then second group for most more advanced uh competitors will be about harder techniques and not that many problems to

solve like uh DP optimizations, divide and conquer NOF. Um maybe some hard variation of digit DP broken profile mention of some other subset naps without one is one nice technique some inequalities with digits. Uh switching dimension versus the answer. Sometimes answer needs to be part of a dimension. I think stuff like that. So, and the price I think will be around €250 euro for one month, eight classes because it's twice a week. uh the registration is not started but so every day every stream I'm for me it's this announcement evolves a little bit only yesterday slash today in the morning I decided what exactly will be the topic of those two groups and I will do Sunday lead code classes make a great website and upload your content there I think that YouTube and code forces is good enough. Uh, okay. So, the stream is ending now.

If you have thoughts about this, you can write to me for example via code forces. In particular, if you want to join, you can write to me already. And if so, you can have a little bit of influence on what will be those groups exactly in the time. So if you think you will join again the price around €250 euro uh that and the classes will be in August then write to me and tell me like what you want to be covered and which group you're interested in. Okay. Uh so the stream is over. Thank you everybody for uh for attending. We solved three the CDE problems from yesterday's division one plus two and that one token removing problem from before. I think it was a nice educational stream.

Just the last problem was strange because it was surprisingly easy. The make it zero. It was trivial to me. Well, okay. Have a good day everybody. See you tomorrow at 3 pm Polish time. Bye bye.

Questions about this episode

What is discussed in "Token Removing & CF 1036 (Div. 1 + 2) | algo problem-solving"?

In order: 0:00 Jane Street, Jet Brains, Lead Code, Raja Zikas Shabu; 1:30:00 Huawei; 2:00:00 Lead Code.

What is mentioned in this Errichto Hard Algorithms episode?

11 people, works and ideas are mentioned, including Codeforces, Jane Street, Lead Code, Raja Zikas Shabu, Jet Brains, Huawei. Each one on this page links to its own page with every episode that mentions it.

How long is "Token Removing & CF 1036 (Div. 1 + 2) | algo problem-solving"?

The episode runs 2 h 4 min; the transcript is about 12,429 words in 117 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.