CF 1035 (Div. 2) C, E, F | algorithms problem-solving

What is discussed, and when

1. 1:15:00 – 1:30:00: Google Meet

Notable quotes from "CF 1035 (Div. 2) C, E, F | algorithms problem-solving"

• Work already. Since the last stream, I also did some other work like I used Google Meet or something similar to talk with people, to talk with a student of mine with some…

  about Google Meet · at 1:16:49

Who and what is mentioned in this episode?

Companies & orgs

• Codeforces — Company · 2 mentions

Products & tech

• Google Meet — Product · 1 mention · first at 1:16:54

Concepts & topics

• ICPC — Concept · 2 mentions

Full transcript with timestamps

0:00 test. One, two, three, four. Welcome everybody. We'll do harder problems today. We should be live on YouTube and Twitch. We should be live on YouTube and Twitch. I will solve I will finish solving the cut forces round 1035 mainly those two problems. This will be a quick warm up. Hi. Hello and pj PKG gamer. Hi. I will finish solving the cut for YouTube should be muted otherwise there is echo. I look old. I guess I'm not that young anymore.

1:53 Tomorrow, same time, there will be easier stream. So, today we're doing hard problems and tomorrow something easy. I don't know yet what exactly. I'm from Poland. Hi Nathan. I I still didn't upload the CSS tasks to GitHub. Let me write it down in the calendar. But I want to do it today.

2:44 Okay. noted. I'm losing yubuntu. A video on game theory. Maybe one day. As always, today I will talk a little bit about what I currently think about my streams and just how I should spend time on doing this educational stuff.

3:19 Okay, so this will be a warm up. I actually already have read this problem in the next one, so I know how to solve it. I will not spend too much time on it. Uh, you're given four positive integers. You Oh, here's the problem link.

3:51 link after this one we have E and F remaining videos on algorithms I mean I'm covering algorithms. Uh, not usually recently during streams, not videos. Can you become GM one day on code forces? I have no idea, but it's unlikely. Not many people become grandmasters uh CP course update. Uh, what I have is classes on dynamic programming next week. So, it should be somewhere here. Yeah, if you're interested in classes on dynamic programming, there is one easy group one heart. Then this is the link you can read about it. 250 per a month of classes.

4:56 Yeah. Uh good problem. You're given uh NLA RK. You need to find the lexographically smallest. Uh so we minimize the first element then second element and so on array such that the length is n every value ai is from L to R and bitwise end is equal to bitwise exor which in particular the parity here is very important. If no such array exists output negative one uh in particular if well let's read the stuff there is n can be up to 10 to 18th but we need we don't output the full array we only output the k element the array may be too large output ak only so we are not constructing the full array we are focusing on one element k element but in particular uh what's the order n l I will call this low high and k if n mod 2 is one so if length is odd then all elements can be just the same and then this will be satisfied bitways end for example seven and seven and seven is equal to 7 x or 7 x or 7 and

6:23 this is true for any element not just seven. Can you please turn on auto caption? Thank you. I don't think that's possible. At least not so easily during streams. I wonder if there are some tools where you as a viewer can turn auto caption on your own like some kind of browser extension. Okay, if this then simply we can output low because all the elements will be equal to that and otherwise when n is even and you want to satisfy this this is a little bit more tricky every bit so that this would be true every bit needs to appear exactly odd number of times let's see an example maybe let's say that bitwise end uh end is equal to something like this.

7:24 And now for X or to be this, you can have few elements equal to that. In general, this is the smallest that the that you can use. And then and then what? Well, if I use here a one right now, the exor of those values of those uh bits at this position is indeed one. Here I need to use a zero because otherwise the extra would be one right now. Uh unless I had another element. If I had here another element maybe like this then here I could use one. So what do I do with that? Let's let's first observe that we need to find like graphically smallest sequence and for that as many elements as possible should be equal to that lower bound the L.

8:22 So in particular if this is let's say uh the low or L then we try to make a lot of elements equal to that and with just the last few elements we will try to uh fix the exor value and now I will basically experiment on that n is even so for example right now n is four uh I cannot just by modifying the last element I cannot achieve that for example if n is Or if those are the three elements, then the last element would need to be zero for those to exor back to the same value and then well then the bitways end will be messed up.

9:11 Yeah, but if anywhere there is a one then again XR and bitways end will not agree. So yeah, there is no way to just modify one element. That being said, I claim that n minus first n minus2 values should be equal to low to the value l from the statement stack on 12 rated problems. What should I do? Solve 1100 rated problems. I think money and here let's see one of those values should be one of those two elements should be one the other zero. Uh no but then the bitways end will not agree. So both should be zero but that's impossible.

10:03 So maybe it should look like this. Uh the last two elements should have a one on some big position. Then on this position we want bitwise end to be equal to bitwise exor. How can we achieve that? If I do this then xor is zero of those four ones. If you have four ones bitwise xor is zero bitwise end is uh one. So doesn't work. If I do this then end is zero xor is one. If I do this then it works. So if there is one one then I can have zero zero uh then it seems zeros zeros and so on. So this seems reasonable now is it enough?

11:00 I'm not sure. I said that I've read this problem before but I don't know a full solution. So my current idea is that n minus two values must be equal to low and then the remaining two values should be equal to the next power of two. Unless that doesn't exist then the answer is negative one.

11:44 Let's let's create some uh power variable call it e. I want to say that this is greater than low. Well, this 2 power e is smaller equal than low. E++ if this is this power of two find next power of two if this is smaller equal high then this is good and if it's greater than high then it doesn't fit in the allowed range so I output negative one otherwise if k the index that I'm interested in is up to this then it means that it's one of those values is equal to low. So we output low. Else we output that power of two.

12:48 We'll see if it works on the sample test. Oops. I here incorrectly do something. Uh so just this one test doesn't work. It's this one. I think it should be negative one. So here n is two. Oh n is two might be a special case also. N can be one. That also might be a special case because here I assume that those values exist. Does it change anything? Okay, let's think. N= 1 is easily handled by that. So I think it's just about n equal to two. N= two. Bitwise end needs to be equal to Xor. If those elements are the same then this is equal to then this is zero. So that doesn't work. If those elements are different then at some position they differ and this will end down to zero. This will end up to one X or up to one. So I think that we should output negative one.

14:21 I think it's always negative one. If n equals 2 or this I don't think that n equals 2 is solvable works for the sample test is what is it a good problem I see some long comments. in the chat with definition of bitwise exor

15:04 I don't need those long copy pasted long copy pasted information about exor if somebody doesn't know what exor or bitco end is then they will not solve this problem or understand the solution in five minutes okay warm up done now we move to two real problems and constraint and then after that it will be volcanic eruptions. Uh so again some bit wise operations do we have test cases? Yes we do. Oh, one more thing. If you ever later watch recording of my stream and you want to see my code, you want to maybe copy paste it use in some way. What you should do to the to to achieve that. So I don't need to actually upload anything to GitHub repository if we're talking about code forces submissions because you can go to my profile, hit submissions. I think it's also visible from incognito mode.

16:17 Uh let me make sure. Yes. And you should scroll to the date for of the stream in particular the date very often you will see at the top of my screen like today is July 15. Uh and if you if you for example need something from 28th of June, you scroll down to 28th of June and here apparently I solved this problem gel efficient something. And if you click here at the ID of the submission. Hello, you cannot see it. Only people with some special access can see codes of others. What? If you're not a trusted user or you're not logged in, you cannot open it. But it it's a blue.

17:12 number. I mean, it's a link. It doesn't work if you haven't participated in a contest. Interesting. Oops. Okay. Well, then at least you need an account. Not sure. Well, let me open somebody else's account to see how that works for me. I also cannot click that really status. Maybe something is broken.

18:13 not allowed to view the requested page. Yeah, that that cannot be right. Maybe you can paste the code into something like paste to uh I I wanted to say that I don't need to do it. Oh, I'm still in incognito. Okay, sorry. I'm stupid now. I want to see if I I thought that's I closed it and now I'm in my normal browser. No, I want to see somebody's submission. Okay, it opens normally in Jim. Do I have special rights right now? Uh disable coach mode. So now I should be a normal user just like any user. And it still opens. Okay, good.

19:10 Uh, then I stand by what I said. Usually if you want to get my code, my submission in code forces, you should scroll to the date of the stream and then find the submission. Okay, end constraint. You're given a sequence A of length N minus one and the sequence B of length N. uh you can increment element of B by one. Use the minimum number of operations and you are given bitwise end between two consecutive values for every two values. We need to output the number of operations. Uh I don't know if I have already pasted the problem link but here it is.

20:00 So we might be given information that B of one and B of wait B of zero and B of one is equal to something is equal to let's say this then B of one and B of two also is equal something let's say this and what do we do with that uh from that I think we and roughly get the value of B1 because this means both B1 and B2 have those bits on this means the same uh well let's think about it this way for the the information that this is bitwise end it means at least that those bits are on in both numbers so B1 needs to have those bits bit one also needs to have those bits so if I compute bitwise or of those two.

21:00 Oops. This is I think a of zero or a of one. If I compute that, so put a one whenever there is at least one one. So this this is information about necessary bits of B1. Now this position can be a one but we need to be careful. We cannot uh break those conditions. The zeros mean that at least one of the two numbers need to have a zero. So preferably we should use a zero somewhere. One is only used when needed. We are given some initial values of B. We need to increase it by one as many times as needed. So if those bits are needed in B1 and initial B value of B1 is something let's say this is initial B1 then at least what we need to do is raise this up to that value and then maybe do something extra this is greater than that so I just increase until uh it's equal So at least increase to the required value.

22:28 I also have an idea that for safety we will assume that just at the beginning and at the end of the sequence B there is an extra zero and also then its bitwise end with neighbors is zero. Maybe that will help. Yeah, Arc, I'm timing you out. Stop repeating stuff. I don't know how you imagine answer to your question. Anyway,

23:08 so we increase to the required value. What if this is already greater than the required value? Then I think we will add an extra bit one at the beginning. Uh right. So if this is required and let's say this is what we have. No then we actually do nothing. This one is already here. Okay. But then we cannot have too many ones because it might break a condition where every zero in the input in bitwise ends between two neighbors. It means that at least one of the two values B I B I + 1 cannot have a bit here.

24:09 I don't think that's true. Maybe maybe it's true that every bi is either its initial value or the required value exactly that I think it's incorrect but maybe so from the required bits we have something maybe we need to increase bi to this or maybe bi stays as it is Actually it might be a combination of that. For example, if let's see this is required and this is initial value. Now we increase the initial value up. So it would include those. Then we will have this uh initial value increased to contain the necessary bits and that should be easy to do to increase the initial value as needed.

25:19 It might lose some bits of course like if this is required and this is what we have initial then by increasing this to contain those bits we will get rid of this this will become zero. Now after we increase the initial value to what is required I think we should forget about the initial value we just have something current that has the necessary bits on and I have such a sequence bi now I need to turn off some of the bits still preserving the bits that are required so let's Say that somebody tells me that here in this position I need to turn this bit off.

26:16 For example, here maybe somebody tells me uh maybe somebody tells me this bit needs to be off but I can only increase. So if I want this off then I need to increase. In this case it means I will put an extra one here. it's unnecessary one. So also it can cause some harm by bitwise ending with the next value. Generally I prefer zeros unless one is needed and then in the remaining part I can have whatever I want. So for that I will put only the required bits.

27:07 Let's also make a drawing. Maybe it will help. I increased BI a little bit and after that it is equal to something where some of the ones might be required. Then this this one the remaining ones they are not required. So I will say whatever though zero preferred because if one is not required then you between two consecutive values bi you need at least one of them to have a zero. So it's always nicer to already satisfy this here, not count on your neighbor. And you can say the same thing about the remaining elements.

28:17 Plus you can get information that maybe after you already are done with the previous element BI minus one here, you might need to turn off some elements. Maybe this needs to be off. Maybe this needs to be off. How do you achieve that? The next thing that can be on you turn on. So among this is also a zero here, zero here, infinite number of zeros on the left. So I'm going from those required of positions the next zero on the left which is in this case here. this one turn into a one and then on the right all the because already this makes sense uh or guarantees that I'm here increasing the value so all the unnecessary ones I can turn immediately into a zero so this changes into zero this well it was zero but it again changes into zero from that I would say that always what we will have is the value b I where somewhere I make a decision to change zero into one.

29:39 Then after that this suffix is easy because uh in the suffix wherever there are necessary ones the ones that I said they they are required I said that in green earlier required and everything else is a zero non-required ones become zero because thanks to me increasing that I can afford whatever I want here and zeros are preferred because they made it make it easier to satisfy the zero. zero conditions with neighbors regarding the prefix here is uh it's whatever the initial value implied whatever the initial value implied by that I mean we are given bi and we first increase it like I described in the editor here that there are some information that this needs to be one this needs to be one so we raise up to that amount we will change and now we it's not that we go from left to right and we do things greedily at least I don't see why it would work because it's hard to make a decision about the first element if

30:53 you don't know the final state of the second element but if the state can be described by which bit you turn unnecessarily from zero to one and then it implies everything else this will be the DP Eight. I will have DP of N by 30 or 60. 30 is enough. DP of N by 30 in or long long or what is DP of I by K. Uh minimum in total increase so far. So far if we change BI into value where K cave bit is unnecessarily on. Yep. Everything after that is as required. Everything before that is as implied by the input. So that uh we uh greedily increased from the input value bi to satisfy the conditions about ones with neighbors.

32:11 So for every value in the input you have only 30 possible candidates for what it will become. I think that's nice way to put it. And this will be um minimum score so far or total number of increases if the if element we change into its k possibility. So we will do maybe two separate phases. In first phase for every element I will find 30 or 31 candidates for what it becomes. Uh for every candidate it's trivial to know how much I should increase up to it. And then as I do the DP from left to right always if I know what the previous element became then and I iterate what the next element will become I can easily check with bitwise end if the needed condition is satisfied.

33:07 So I'm aiming at n * log squar where this is logarithm of uh 10 to the^ 9. Can we quickly recap everything before the DP? Yeah, I think now I will recap before I code maybe using the example. I'm not sure if first example is strong. Maybe I should use this. A first example has four. That's fine. Okay, let's explain again using the first example. Those are values between neighbors. Now for every element like this element two, I know that I have some requirements about its value between neighbors. If there is a one here, it means that in particular this value needs to have a one. Uh if there is a four here then this value needs to have a four. So at least what this element needs to become is a five because it needs to have all the bits of this guy and all the bits of that one.

34:25 Otherwise those values wouldn't possibly become one and four when you compute bitwise end between neighbors. By the way, bitwise end is similar to minimum operation just in multiple dimensions because binary string is kind of like a point in multiple dimensions by the way is this and what I'm doing is if I get information that minimum of B2 and B3 is equal to five minimum of B3 and B4 is equal to 7 then this implies something about B3. B3 here would be would need to be increased at least to a three and sorry at least to a five and at least to a seven. So here at least to a seven. So I would say B3 becomes maximum of its original value the one in the input and also well a of two A of three.

35:27 In our code here, I will say that B of I becomes maximum of itself and A of I minus one or A of I. This R is like maximum here because it says I need bits from here and from there. That's the implied value of BI. At least I need to raise to this level. And then I need I can modify this a little bit because there are extra conditions about two consecutive values having enough zeros in the bitwise end. And for that I figure that in BI I it's enough for me to find some position that I will turn from zero into one. Everything after that is trivial to determine because we will put a one only where it's really necessary because it was in bitwise or of a i a minus one. In this prefix I leave whatever I found is implied.

36:31 Yes, you can say that thing about sub submasks. And we have integers only in I mean now I wonder should I add extra zeros? No, the zero would hurt, right? Maybe not. I think we will do this now. B of Z. I I have a condition now that a of i is equal b of i minus one and b of i. This changes the indexing a little bit compared to that. But I think now so b of i is or maybe affects values a of i and a of i + one. I just uh imagine that there is an extra zero at the beginning and at the end. I think it should work. First treat values a

38:15 values a of zero and a of n are both equal to zero. Then read BIS now that more people are uh viewing the the stream, let me ask you uh for a problem like this one where it's not trivial uh and I cannot solve solve it. I cannot fully come up with a solution in like two minutes. Would you prefer? Yes, my name is Camil. Uh would you prefer that I know a solution in advance and explain it well and not struggle? So what do you prefer during a stream? Option one, I know a solution to a hard problem in advance. Let's say I explain and code And option two, I do not know a solution. I try to solve it. Possibly I spent one plus hour. It happened in the past like recently in some hard at coder problem not very hard where I implemented DF BFS thought that it doesn't work implemented dystra it was too slow I needed to optimize for half an hour and then it turned out that the BFS would work just a little bit simpler

39:52 BFS Most people prefer the two. I mean, it's easier for me. The one version one requires some preparation, but it is also the the option to that you guys prefer apparently. It means that sometimes I will solve like one or two problems during a stream, especially if I'm doing hard problems. For example, yesterday so before the stream today I did read the problems E and F and for both because of that already before a stream I had some idea for a solution not a complete one also I didn't implement anything for F I also took a look at the editorial but my solution is slightly different and I'm not going to exactly follow the editorial But yeah, it's I just wonder what is in some way better.

41:20 The thing is that you make your solution work with complicated code implementation. Never seen code optimizations. Uh Chandu, can you explain more what you mean? So are you saying my code is complicated? So it's good. It's bad or good? Am I immediately implementing something fast or slow and then doing strange changes? There are just too many ways I can interpret your message. I agree with Mav 08. It's hard to get epiphanies when you're not 100% focused. Obviously, outside of stream, I'm better at problem solving than during a stream.

42:11 Of course, it's easier if you have prepared. I mean, easier is a tricky word. If I have prepared, then I spend time in advance. So, I had the hard job earlier. I'm just wondering what you prefer. Part of the freent learning for us is your thinking process and why would you thinks about some solutions how they turned out wrong? Oh, actually if I think about something before a stream and it's incorrect, I can also talk about it during a stream that's not a huge issue. And do you really need a frill during such a stream or do you want to learn?

42:57 When I do lectures, when I cover some hard problems, I often go through an incorrect solution, especially if I think that it's reasonable to come up with it and try it. Why does the following greedy fail? Uh there but I I see that you like this thing I think. Then what I'm going to do is only if I want to maybe let's say if I want to do a division two round fully during a stream possibly then I will in advance read the hardest problem.

43:43 Uh why does the following greedy strategy fail? Increase BI until BI has all the bits in this uh because possibly two consecutive BIS will have some unnecessary bits. Uh right. So let's say what about this?

44:10 Let me create an example. AI. I want to answer this thing. So I'm worried about the case where AI has only few bits on AI + one has only few bits on and all the values B let's say this is A1 this is A2 B of 1 is equal B of 2= B of three is equal to a series of ones.

45:15 Yep. I think this this works. Okay. This is your counter. This is counter example for this question. Why is it not enough to just increase BI until it has all the bits necessary? because this is an example where BI immediately has all the bits necessary. So that first part of uh making sure that the necessary bits are on, it might do nothing also. It might do something but it will still have a lot of unnecessary ones. So right now my B1 is equal to this, my B2 is equal to this, B3 is equal to this. Uh, but I want the first two to only have this fourth bit from the right. Oh, how do I stop?

46:10 Okay. Um, so what we should do is here uh we should modify the the values. I should change this. Maybe I will add an extra zero here. I'm going to change this into a one. So I'm increasing this a little bit. Then a lot of zeros, but fourth from the end needs to be a one like this. Then second value and third value. Uh this needs to have fifth from the right on. No. Yes. Let's do it like that. Like two more zeros skip and then this like that. I think now we're getting somewhere. Uh so for those values B indeed the bitwise end of those two at least will include this. For those two it will include that but not correctly we have the extra one at the beginning and we can fix that by doing something like this.

47:24 where also among those first few bits they they are not all the same in all the numbers also it I'm not sure if maybe this is an example showing that uh we are operating in the input with 29 bits but here I'm using two extra bits before that so if the numbers in the input are 2^ 29 minus one maybe we need all 31 bits

47:58 I think I will use 31. Uh, okay. So, we have this. How do we increase until we have the necessary bits? Phase one, increase BI to include bits from this Of course, I don't want to increase BI one by one. It's not as simple as doing that either because I can turn off some of the bits for free when when increasing like that. For example, if BEI uh is let's say this and the also value is this then I need to have a one here and there and this automatically turns off those guys. So starting from the first bit that I'm increasing everything after that I can just copy from also starting from the big bits

49:31 wait uh here 28 let's use 29 if also contains this it but bi doesn't so I need to turn it on this remaining suffix I should just copy from also because the bits that are inbi are unnecessary so from here on copy the also let's See, get rid of the last that many bits plus one because also this guy you want to get rid of. Uh then move it back this change the last that many bits into zeros. And now I want to take those bits from also But I only want to extract the last part of it.

50:51 Uh copy the last J + one bits from also to BI. I think this is what I did. What I need to do then break because you found that uh this find first bit. So largest uh bit where they differ as in zero and versus one because if this is one then and this zero I ignore. Okay. So I see where I need to increase. Let's also make an assert uh memoi. This is the initial value. Wait, I I shouldn't do this, right? Yeah, I shouldn't. At the end, I need to assert that B of I is greater equal than the initial value because if I created something smaller than that's very suspicious and answer gets increased by the difference.

51:55 No wait. Yes. This was just the first face. Uh well I hope that I never overshoot. Yeah I never produce answer bigger than what the correct answer should be. So that's good because it would be strange if already in FA phase one I did all operations more operations than what is necessary in total. Next uh phase two. What is phase two? It's a DP or maybe find roughly 30 candidates for every BI. That is for every BI. I know the necessary bits. It's still this. I know the necessary bits and I wonder which of the remaining bits I need to turn from zero to one unnecessarily.

53:32 Maybe it should be combined somehow here because it's very similar code. Let's make it separate though. it is similar and I'm sure that the code can be made way simpler. So you see this is the case where if in advance I prepared I would be able to explain a simpler solution but I think I'm going into something too complicated where I think that the two phases can be done at once uh with almost the same code. While doing DP of J, do we say that every bit smaller than J is zero except the necessary bits? Yes. Yes. Mhm.

54:32 Candidates for N. I'm going to do the following for every BI. This still applies. Those are the necessary bits. And in BI those are on already. I can assert that BI and also is equal to also not sure if brackets necessary. Now for every position and not sure about it but from my example from before I'm guessing that maybe 31 positions are necessary. I'm saying if BI right now doesn't have this bit. Can I even compute that for 30? I can. Okay. I wondered if we overflow. Maybe if this bit is off then maybe I turn it on.

55:35 I have BI. This bit gets on and then for all the following bits I just copy them from also which is what I did here. And I want to Does it matter if this bit is in also? Oh, this means it cannot be in also. Assert not also and this because B is overset of also. Okay. So, this is the candidate and let let me copy though not I'm not the fan of what I'm doing. Uh, we have this. I copied the bits, but also I want this this extra guy. Uh, B of I or equal no candidate. Candidate.

56:56 candidate is B of maybe let's say here we add this extra element and then only the last J bits uh we move like that and candidates of I push back candidate I think those are candidates for what BI can become it in particular it can also become itself 12. So let's add that possibility. So now we will have 32 cans of I phase two. Does I get streamed? Only the leaderboard. Many times in the past I did an official stream on II just some commentary. No, I will not go to IO. Isn't the Twitch stream name wrong? Let me see. What is it?

58:01 Yes, it's very wrong. Sorry. And thank you. Thank you for noticing. Also, I fixed my microphone. Let me tell you how stupid I was. Well, no, Windows is stupid, not me. Uh, this is code forces algorithms problem solv. So, I had that issue for the past several streams that people were saying the sound is too low and indeed it was quite low. I already in OBS set it to max plus I even increased it artificially even more with some filter which means that I decreased the quality of the sound. But yesterday I was playing around with the sound settings on uh in Windows. I scrolled down to the What?

59:10 When did that change? How does that change? I'm so annoyed right now. Uh, so yesterday I was surprised that this volume input, this volume setting is set to eight and I increased it up to 80. Then I could remove the filter in OBS and everything was anyway loud enough. Since yesterday I did something that caused it to move down to 20. But how? What? Why does it change when I restart the system? Is there some Because there is output volume which is here. Whatever that that affects my speakers. I'm not using them much during the stream. And then there's this.

1:00:03 So I claim it's still low. Yeah, because some it changed automatically from 80. So what I tested yesterday is that this will work well. I'm now speaking constantly. I'm speaking constantly in my normal volume. I'm not trying to shout. And now I think now it's actually it's too high because I see it going into red in OBS. though if I'm not close to the microphone still still like this is I don't not sure if this is distorted uh yeah good too high I can maybe let's move it down a little bit no I did not change microphone I didn't unplug it Crazy

1:00:58 stupid windows, but I do not understand. Let's Let's do 70. Yeah. After two hours of streaming, it matters a lot how loud I I need it to be. It's hard to talk for 3 hours. It's a lot. I'm so annoyed. And yesterday I was so proud of myself for find finding that setting and angry at Windows at why I have a new system from like 3 months ago. This PC is from 3 months ago. I installed fresh Windows and I never changed the input volume setting so much down. So annoying. Ah, okay. I need to remember to test I don't know after restart of the system why don't you use Linux Linux has its own disadvantages like for example I couldn't draw like this in one note okay now we have uh phase three will be some easier DP P I will say easy DP because for every number we choose one of the at most 32 candidates and we just check if between neighbors we have we satisfy the condition from the statement the DP value should be how much we

1:02:40 increased in total so I We'll say initially for all the candidates let's look at B 0. Look at B 0. For every candidate of B 0 DP push back candidate minus BI. This is by how much you need to increase. Also assert that candidate is greater equal bi. Uh yep. Then for every following element I create new DP array. Also I have two sizes. The previous candidate size to also DP size. Maybe let's use can of I minus one. This is not really necessary. New DP of size B. Uh we minimize, right? Yeah. So by default it needs to be set to some kind of infinity. Let's use long long max.

1:04:07 Don't know about those characters. Divided by two. I'm not a fan of using infinity equal to the max type of uh some of long long or int because if you add plus one to it you already overflow. So I prefer this or billion + 5 or 10 to 18 + 5. Now the interaction for every possible element of the previous so every possible previous candidate let's make this into a variable infinity 10 to 18 + 5 should be enough

1:04:55 those are candidates for B I and B I minus one. So if candidates of I minus one J bitwise and candidates of I K if this is equal to A of what? A of I think I right because I wrote it here. I I minus one and I interact into I. Yeah. If this then this is good. So we do the transition new DP of K minimize DP of J plus cost of transition is this candidate cave candidate minus the current value BI then DP becomes new DP and answer plus equal the minimum element right yeah we minimize DP begin DP end if it's at least infinity and you see here already if I used infinities I would overflow uh if this then negative one else I not declared P of zero Parenthesis suggested

1:06:37 4 - one 2 - 1 0 5 3 something 1 6 works time complexity n log log so n log squared now After I get accepted, I will try to decrease this by one and to see if it still works. I'm curious. Yeah, I'm using a pen tablet. It's some very basic, cheapest possible Wacom drawing tablet. It's so it doesn't even had a screen. It's like a mouse. Okay, accepted with time of 1 second. So, not so good, but not so bad either. I'm guessing that collecting the candidates. No, that's not bottleneck. This must be bottleneck. Well, and will it work if I do this?

1:07:40 No, it already doesn't work for the sample test. So, I don't even need to submit. Okay, problem solved with three phases. I will take a look at the tutorial now. tutorial first try. I mean if the sample test is good then you know does it is it unlikely to get accepted first try. Uh consider AI equals zero first. I kind of consider that. Okay. uh BI must include the bits from two consecutive values A. There are 31 possible effective values for B. Well, that wasn't easy for me to observe.

1:08:35 I think I feel like there should be few extra sentences between those two. Uh like this is trivial and then this is not trivial. only 31 possible values for BI. I actually have 32, but whatever. Uh, increase BI to above at par 29.

1:09:06 So let's this this here they prove that they don't need more than 31 bits. They are saying that every second element if you look at uh things of length 31 then and your the state the input uses 29 bits. What you can do is every second element can start like this versus like that. So every even element starts with one zero others with 01 and then those remaining 29 bits you fill exactly with the value of ai minus one or ai. Though instead of typing this in such a mysterious way the editorial could just say that uh that we can start with this solution and try to improve it. Now we might consider which BI are more likely to be the answer.

1:10:03 Uh we should try to avoid having ones in each binary bit as much as possible. I agree. Uh this will be BI exhibit a stepped pattern. The preceding bits are the same as BI. Next bit is set to one and all subsequent to zero.

1:10:43 Oh, and they also have look squirt. I mean the code is simpler so maybe I should investigate how the code can be simplified. I'm not a fan of this editorial but it seems that they are describing exactly the same thing. Uh what is the rating of this problem? Does it have a rating?

1:11:15 No rating yet. Okay, now to look at the code. Where do they start DP? F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F is the DP swap FG. Okay, F and G are DP functions. So they don't have three separate phases. They do everything at once, which is perfectly fine. I just necessarily three times go through the same array. Uh so that's it's clear that I could simplify like that. But what else is there?

1:12:04 They go bit. Oh, I see. As they go through the bits, they keep collecting the the big bits and they already have it as x the prefix and they or it with the needed values. So they don't need to do so such binary tricks. I for every j I independently investigated what if this bit I change from zero to one. The left part I take from here the right part I I take from there. Also additionally I think they observe that I copied the last J bits from also to BI can say that I take everything from also to be it needs to be there. So it's okay to this uh sorry you don't see it well where I here have the candidate I take some bits from also no I can take everything from also because this is requirement this needs to be fully there same here I think so now I simplify it a little bit and does it still work.

1:13:18 I think so. Let's let me submit again. Other than that, uh yeah, there isn't much else that I will change. I like the question from Ramsey. Let me try to answer that. If someone is for example solving division three contests and can solve almost every contest till E. Uh is it better to just solve the challenging problems EF or the whole contest? Uh you're practicing a different skill when solving easy problems. you're practicing your speed and very simple tricks and techniques, which is fine if you feel like you need it. For example, for me, for me, I'm very good at easy problems. When there is an important competition and it has some easy problems at the start, I'm one of the best. So, at the beginning of the contest, sometimes I am winning because I'm faster than others on easy problems.

1:14:36 I can read fast. I can just get few lines of code fast. Uh so for me if I want to practice more and become better those problems are useless. If I wanted to now practice efficiently I shouldn't even touch the easy problems those that where I spent one minute on it. On the other hand the way I got here and the way I'm fast on easy problems is that I solved a lot of them apparently. Right? So if I skipped always if I skipped easy problems I wouldn't be so good at them. Though generally I think if you can if for you you struggle only with fifth and sixth problem of the contest then maybe you shouldn't prioritize division three so much.

1:15:21 Shouldn't division two be better for you where A and B are easy for you and then C and D are a challenge. Basically the answer to this question is uh you're practicing different skill going through the easy problems and whoever you want to do it or not that doesn't matter too much. Uh if you want to be better at problem solving you can jump immediately to EF. If want to be fast and you want to implement practice implementation you can try the easy problems. I don't know what you prioritize. For example, in ICPC, the team competition implementation speed is important. So for that, you need to be good at easy problems also. So you'd be faster at uh using the computer.

1:16:18 Also, I think people use virtual participation too much. I'm not a huge fan. A little bit of it is fine. I'm still so angry at that Windows uh input volume setting. How could it change from yesterday? It changed from 80 to 20. And my microphone and voice level is very important to me because this is my work already. Since the last stream, I also did some other work like I used Google Meet or something similar to talk with people, to talk with a student of mine with some one-on-one classes. And now I have no idea if I was very low for them in terms of my voice. They did not complain, but so annoying.

1:17:10 Why cannot software just work and not change? Uh when is next at color stream? I think next week for the next uh week I have II camp so I I will not do at coder within the next week that's what I can tell you ICPC problem ratings why do you need problem ratings

1:17:46 yeah connected solve C apparently you need that more. If you solve AB under 2 minutes, they are not hard for you. Uh, red and I don't even know what you're asking about. Okay, let's solve the hard problem. How many hours you need to reach red? I think you need years, not hours. You cannot just spend thousand hours straight and become red. I think around 20 years are needed including a lot of math classes in school. I don't know how to measure years. Let me ask you this question uh but something reasonable. How many hours are needed to become professional level at football?

1:18:49 And for that are you going to just count the time somebody spent practicing football or is it also you know physical development when they are young and practicing how to run. I spent way way more than 10,000 hours by the way, especially if you include math. And for me, I wouldn't be good at programming if not for math.

1:19:32 What ranges are asked in regionals? Oh, I see. Ren, you're asking about difficulty of problems in ICPC. Well, from easy to very hard. From division 2 A to division 1 F. So, from rating 800 to rating 3,500. Easy. Yeah, I did math Olympics. Uh, volcanic eruptions. Uh, there is undirected tree with root one where every vertex has a weight one. Okay, vertex, not edge. I've read this problem before, but I I didn't remember that it was a vertex. Uh, volcano volcano erupts at time zero in the root. At time t, lava fluts. Uh, how do you read it? Flats. Fluts.

1:20:24 Flat. Right. All vertices whose distance from the root is at most t. So it moves one unit at a time.

1:20:37 Floods. Floods. How can you read double O as a as a U um okay? So it move starts from the root moves one edge at a time and it kills everything. At time zero, you are at some starting vertex and uh initially oh with life value s initially you have one health point starting at time zero. The following events happen in order at each time stamp. So every minute or every second this happens. Your value increases by the weight of the current note. So you gain one health point or lose one. If your health point is zero or lava reaches you, you die. And then you need to move to adjacent vertex.

1:21:36 Find the maximum number of moves you can make before you die. So how long can you survive? Will I participate in Metah Hacker Cup? Yeah sure. Ramsey is asking how important is the strategy? How do I measure it? How can I possibly know the answer? I don't know. Strategy helps, but you shouldn't spend time on strategy and think about it for more than 10% of the time that you're practicing. I have my advice for how to practice on Twitch. The link should work. Yeah, this thing. You can go to Twitch to click the link and go follow that. And that's it.

1:22:44 Uh okay I think it's very important that the initial life is one also do is there a drawing useless drawing I think that in this problem uh so there is a tree there is lava that starts here and kills layers of the tree one by one. Okay, so there is lava. I start somewhere and my health points is equal to one. If I am in a note where uh where the weight is negative one, I lose immediately. If not then I need to be at a note where the weight is + one and then if there is neighboring node where there is also a plus one I can keep moving between them to gain a lot of health.

1:23:58 The alternative is that next to me there is a negative one where I go and then just like uh initially the logic is after that I need to go to plus one possibly this note itself but usually not. So then I go to a plus one and always I barely survive. So initially the sequence of moves will be that I will gain plus one health point in the starting node then minus one + one minus one and so on. Eventually I might reach a place where there are two neighboring plus ones that I will uh keep jumping between them to gain not infinite but almost infinite health.

1:24:45 I can do it as long as the lava doesn't reach me. And let's consider the following strategy that I find some place where two neighboring plus ones I go there. I can go there only if the path so far consists of plus one negative one. If there is if two consecutive plus ones earlier then it's enough for me to get there and I don't need to reach here to start jumping between them. If there are two consecutive minus ones then I will die here because my initial health is one. So I cannot afford this. I here always barely survive. Minus one minus one would kill me.

1:25:25 So there might be such a path of plus minus plus minus then two consecutive pluses. And consider a strategy where what I do is I start from here. I go + one minus one + one minus one and so on. Eventually you have those two notes with + one + one. Keep jumping. And you keep jumping as long as the lava doesn't reach you. Once the lava would kill you in your next step, you start running away. And your speed is the same as the speed of lava. So you keep going down and the lava keeps following you. You are always like one or maybe two steps ahead of lava.

1:26:06 H whether it's one or two depends on the parity. So your initial distance from the lava I think its parity cannot change because always lava gets down by one and you get down by one or up by one. Uh and if indeed you it's optimal for you to be here at plus one plus one and uh run away like that, you should run away to the deepest leaf below to the leaf below with uh biggest depth. But can you die earlier? What if we have some a lot of negative ones? Then instead maybe you should go somewhere else. Your distance from the root it decides how much time you had to gain a plus one + one and I wanted to say that we are iterating this place. Okay, maybe instead we will iterate the end point.

1:27:13 We will iterate where we will get before dying and that might be a node that just is a sequence of few minus ones or maybe for every note I will decide if I can get there and if so how late so how much health point I can health points I can get okay something like that but there is one more thing that I can do first before I start running from lava down. I think we can still go up a little bit and then to the side to some deep leaf. Consider a situation. So I think the general case will be that I start here. Start I go up a little bit and I go down. I find a place with two consecutive plus one + one + one. The lava starts from the root and keeps going down. It's layer by layer. Then from those and uh before that what I had is plus - plus - plus minus then after this maybe below this + one + one the tree is not very deep or maybe it has a lot of negative ones.

1:28:38 Wait, it doesn't hurt that the tree is not deep here because I could just longer go here. No, it's important when the lava gets there. So basically, it's important when the lava gets to a leaf. Maybe I will not be limited by my health points. I will be limited by just the speed of lava. So it's very likely that the answer is just the distance for lava to get to the leaf if I had enough health points for that. But what I can also do is as this last phase I can from the plus one + one go up a little bit and then to the side and down like this or even like that I can go above the previous LCA.

1:29:19 So this was first phase. Second phase let's say jumping between plus one + one and then go up a little bit then to the side and down. And then the question is how much you can survive here. I think we will never keep going back and forth between two nodes because it would be better to spend that time here and it doesn't change anything in terms of lava catching me up or not. If I could if I have here if I have spare time to do this then it means that lava is at this point at least two units above me. So it was the case for all this path. So lema I will go back and forth only for a single edge ever.

1:30:09 So there is some edge usually between two plus ones only between two plus ones otherwise health points would drop to zero. lema lema there in optimal solution there is only only one edge of + one + one where I will go back and forth

1:30:53 Yes, there might be multiple optimal plus ones. That's true. I claim this if there exists an optimal path there is exists an optimal strategy where there is only one edge that I will use. So from this the solution or idea for a solution is for every edge + one + one in the tree we need to consider this one to be uh repeatable and nothing else will be repeatable for every edge I consider that and I take the maximum among possibilities. What if there isn't any plus one plus one then then that's easy because it's just about it's then just just DFS let's say how far I can go always I know where I am where Lava is and that's it I'm so the case without two consecutive plus one is so easy that I will leave it for the end generally I prefer to handle edge cases at the end I'm thinking about the hardest case about the hardest possible strategy. So what the solution will need to include anyway and then

1:32:29 after that solution is formulated I will think if I need separate code or separate logic for more basic cases. I I'm not familiar with CTFs. I'm not really good at stuff other than algorithms inside of computer science. Okay, back to this. Also, I will type the problem name. I wonder if in OBS I would have a nice way to like take this and put it to always make it visible. I mean I tried to display the problem statement on the screen so that people who join the stream would know what's going on. They can read the statement. for a hard problem if somebody is joining then they will be lost anyway but at least to display the problem title this I think is a useful information because you see the contest contest with the letter also tells you the difficulty roughly if you know what code versus is you can search for the problem name of course I could also just put text on the screen but this seems more meaningful

1:33:58 because you immediately recognize oh code forces Why do they have problem tags on? Because I my work is also teaching. So I I try not to use them when solving problems. Uh to be surprised. To be honest, so far I didn't look at the problem tags. Now that you asked me, I did look at it. So I see that they're they're here. But generally I have them on because often I need to find some problems for my students and when I do that I need to like quickly consider a problem. So when doing that I will also uh often look at a problem and after one minute of thinking look at the editorial to make sure that what I'm thinking about is correct.

1:34:51 So teaching and finding problems for students, it's something else than practicing efficiently. All right. Uh so we have this. Now what should I iterate for? I can run the initial DFS only considering jumping between plus and minus one uh to consider if I'm able to get somewhere. That's the easy part. Then should I iterate this position where I will keep jumping or should I iterate the end point where I will be. So it seems that this first phase is not very important. Just one DFS will handle it. Then we need to think like this.

1:35:56 For every such + one + one edge, I know after what time I can get there. So this I know where the lava is. And from here I consider I don't know how many times I will keep going but I consider going up and then this way. Maybe I should iterate the LCA. This LCA between the edge that I keep repeating versus then the path that goes down uh to keep going away from the lava. Hopefully this is such a path that it doesn't have too many minus ones because my health points might be not enough and also its length might be important.

1:36:52 If you know where the LCA is, then you know how much time you have for this because if from the start you got here at time equal to 7 and this LCI LCA it is at depth let's say 20 and also there is this distance from LCA to this edge there is distance of let's say six then we should combine all this information at Before time 20, you need to get to LCA and start going down. This is distance of six. So before time 14, you need to be here. So at time, let's say at most 13, you need to from here start going up, which means that this edge you will keep using until time 13.

1:37:42 So in this case, you would use it most likely three times back and forth for the total of six turns. Knowing LCA level, you will know how many times to use this. Knowing LCA level and knowing this. Uh, so this seems promising. Then from this LCA, we also know our health points. We know that I will get here just before the lava gets here because it doesn't it isn't beneficial to me to get here earlier. I know that I will now just keep going down and nothing else will happen. I will never go back and forth because I could as well have done it here.

1:38:21 So it will usually be the case that I go LCA just before the lava lava and I keep going down. And I have some health points. Health points are decided by the sum on this path plus the health points excess that I got from going back and forth here. gaining plus one every time. In this case, I went here six times in total, I traversed the edge. So my health point will be increased by six plus the sum of values on this path. Then from the LCA I can I think ask the sub tree for what is the deepest note such that the sum on the path from LCA to U doesn't exceed something. my health points defined that uh I can I will write down this query given the well LCA let's call this node A and health points H find the deepest note in sub tree of a such that sum of path from a to this node is let's say at least h at least h or negative h whatever um okay now it's tricky to ask questions about sum of puff from a node to another node

1:40:05 it's better to say that it's from the root so for that you just need to add or subtract from this query the sum of values from LCA from this note a to the root so that it would turn into this and now when in a sub tree you're looking for deepest thing that has uh its value sum of the path from the root at least something then this value is just one value assigned to every note in the tree initially I can run dfs from the root to compute sum of the minus1 plus one values from the root to everything. So this becomes given note a and value h find deepest find the deepest note in sub tree of a with value at least h. Okay value that was once computed.

1:41:03 uh and this I usually solve it offline. You can sort such queries by the value h. So the sub tree is just a range. It turns into there is a sequence of values. This is flattened tree. Not sure about the spelling of this word. Uh there are queries LRX in the range LR corresponding to the sub tree find oh find what the sequence of values actually comes with second type of valuesh

1:41:53 so it's like parallel binary search. Oh, this is solvable but already too difficult. I need to do it in a different way. Uh maybe we need instead of LCA to iterate the final note. For every note, I will decide if I can get there before the lava. And if so, well, basically how late, how long I can survive or how many health points I can reach in advance. So maybe there should be this middle phase where the this edge will tell the LCA. So every note as a possible LCA will get information of how many health points I can have here just before the lava gets me.

1:42:49 And then after that oh maybe it's not separate queries it just it will be single DFS that pushes everything down no data structures necessary yeah here when when I considered this I considered oiler to plus segmentry but still that's it turned out complicated Uh, heavy light de composition works too. Well, depending for what exactly. If you're asking about sub trees, then I don't think HLD is very useful. I mean, there is some duality between paths and sub trees, but still for what I was doing here, I don't think a single simple segment tree can do it.

1:43:46 uh I wanted to do offline sort queries by this required value and in this sorted order activate the values or notes one by one so that data structure a segmentry would always have only things that have value bigger than something it's like sweep line by time creating segmentry for each depth I see why you would do Okay, but let's try to do it without that if possible, especially because it's a division two problem. I hope that maybe we will solve it with a series of DFSs and I won't be surprised if it turns out that uh actually the time complexity is linear.

1:44:41 So if for every + one + one h we are able to propagate its possible value up to all the LCAS LCAS. So for all the nodes on the path from this guy to the root they will get updated info where such LCA candidate LCA it only needs this just before lava gets me I can get here with how many health points and if we have this then we can propagate this

1:45:31 Because in the middle of this process for example here when you keep when you spend some time here you cannot say what is your current state here in the middle without knowing LCA. Okay? Because here, if you repeat it back and forth here a little bit, you have actually two parameters that you optimize. You have the current time slash distance to the lava, and you have the current health points. And you want to have still a lot of time left, but you want to have a lot of health points. And you cannot possibly do just some DFS or DP where you know here what is the state because without knowing where LCA is where LCA is you don't know how much health points are required to get there or at what time you want to be here. So it seems only from LCA down uh you need this. So I'm thinking now about three phases to the solution. Phase one will be simple DFS from the start to this way you get to all edges of type +

1:46:44 one + one. Okay. Then some magic but maybe hard for every such edge. So from such edges update LCAS above I don't know yet how to do it. and then run one DFS from the top to push LCA values down. For every LCA, I know uh I just need single information of how much health I can have being here and I push it down, it will automatically pro propagate everywhere down. And my I know that I am here before the lava, so I don't care about lava anymore. As I take a step down, the lava takes a step down. So, it will not catch me. And below, I will never go back and forth. So, I don't care about the exact distance to lava because I know that earlier it was better.

1:48:01 So, this step is easy. This or this face uh maybe I will say three phases. Now, how to do this? H it seem I think this will be linear bottom Well, DP is maybe a trivial DP. I think I think that uh as we go from the bottom, we always know what is the best for us to get here. No, no, no, it's not.

1:49:13 Maybe this. So from the start if I go like this. I think if if the path should look like this and this is the LCA. From this LCA, I think what we are interested in is just the closest one + one H. If there is the + one + one here and another one here, then why would we go all the way down? Remember that before we visit the + one + one edge, the only possibility is we go plus minus plus minus plus minus and so on. So all this white puff and all this white puff they are same quality.

1:50:26 So this from here I have some information about it. The information is when I get here. Oh yes, this guy only gets information when when I get here. Uh, and then I know back and forth I can keep going. And how long I will do it, it depends on where the LCA is because I need to get up to LCA in time before the lava gets here. Now I run bottom up DP where for every node I store information about the closest + one + one edge down. Oh yeah. So that that's then easy. Always for every note you consider it children. Each stores some information about what was the closest one down there. and I grab the closest one and then for every LCA I just have that information about the closest plus one plus one where I could get there and here in constant time I'm I compute then I will be here just before the lava at with what health points okay then I think we have a an offend solution yes glump uh We the plus one plus one edge is something

1:52:00 that we can keep repeating to increase time by two and health points by two. And we will do it as long as possible, which means I still need to get to somewhere before the lava does before I start going down into some uh deep path where I can survive for a long time. Okay, I think I want to see if the editorial also has off and solution. If not then it likely means that I messed up. They do not mention. Do they have segmentry? No. Do they have segmentry here? DFS. DFS Q front is that priority Q or Q okay they also have linear so I think I have the correct solution if this is a sequence of such phases now how long will it take me to implement is another question why can't you go above the LC after doing repetitions of that I think You don't know what LCA is then I will try every LCA the path there is some optimal strategy and it looks like this go from the start to somewhere keep going back and forth between two

1:53:40 plus ones then uh either from here immediately go down to something very deep or go up a little it and then start going down. This note, the highest note where you ever was, we call LCA uh or you ever was you ever were during this blue path like this, then this is LCA in that last phase. So after doing the plus one + one, it's how high you will climb. What I don't like is this parity thing. I for me the problem would be easier to implement if they guaranteed that for example initially your distance to the lava is odd or initially your distance to the lava is empty. Empty.

1:54:38 What am I saying? Even otherwise I will sometimes need to take care of the parity. Yeah, doing the plus ones is to well to collect a lot of health. Also, we need to make sure that the solution works if there if uh we never get to the plus one plus one. This is a lot to code. I'm not sure if I want to implement it. Uh test cases here. Let me see.

1:55:42 Hm. What I wanted to do today is if I have enough time then also solve this problem variables and operations which I do by the way I think is a very nice problem. I also have read it already and I know most of the solution and it's very nice. I think it's okay to say that it's a beautiful problem but maybe I do not want to rush it. I'm thinking now if I imp want to implement this uh in by the way in my ICPC time so when I around year of 2017 2018 when I practiced the most and I cared about ICPC I wanted to we wanted to be world champions.

1:56:32 I would implement annoying problems anyway because it was important to me. I had motivation. Now my motivation is to practice a little bit to stay in shape and to have fun and to make educational streams and stay for staying in shape it is useful to sometimes implement uh an problem also where we care about parity. But for the other two factors I mentioned, I don't think implementing this is so important and beneficial.

1:57:16 We go up to LCA so that we would have other nodes deep there available. Let me draw a tree where something like this makes sense. Uh let's say that we start here. This is a plus one. Then we have a minus. Then we have a plus. Then we have a minus. Then a plus. Minus plus. And there are few things there. uh let's say and uh what else is there? There is here a plus then maybe a minus then a minus a minus then maybe plus maybe another plus maybe minus and so on and then maybe this path is very long. What might be optimal here also depending on how what is the distance to the root from this top note because I didn't draw a full tree. So there is some stuff above.

1:58:25 Starting from here, I want to get to the two consecutive pluses. Those I want to keep going back and forth to collect some health points so I could survive possibly a sequence of minus ones. Then afterwards go back here, go there. And why am I doing that? Because if I finish here, the lava will get to me in the time from the start of the process equal to the depth of this note. So if the lava starts at depth zero and this is depth 20, then I will survive at most 20 turns if I stay here. Also, it might be the case that this path is just very difficult to survive.

1:59:11 Just a lot of minus ones. Well, this puff is not so bad. But instead, after doing just a few of those steps, maybe I want to get here and then go all the way down there to maybe not the very deep deepest note, but one of the deep notes because there's also condition that I need to have enough health points for this part. And to decide how much I here collect health points for that I actually if I know where the LCA is. Uh then I know when the lava gets there. For example, I know lava would get here at time equal to say 7. Then I want to be here here at time six or earlier.

1:59:58 From that I can compute when I get here uh how much time I need for that. So how much time is left to repeat those steps. Okay, the decision the decision is made for me already uh because I'm going to eat now. I will think if I want to implement it just during next stream but I doubt it. Uh tomorrow I was going to do easier problems. We'll see about that. But one day I want to also talk about this hard problem there. So look I recommend this problem this variables and operations. you might want to solve it and I think within the next week or two I will discuss it during a stream or a video how the DP will run understand the logic but don't know how it will go up again after the repeating plus one plus one uh for that middle phase I described that I kind of proved that always for every LCA the best candidate for the previous plus one plus one is just the closest such edge down H actually that's true up to here

2:01:40 okay then that's there is something incorrect about this middle face I think there is some details remaining about this face uh yeah it's not exactly a dynamic programming problem it's DFS problem. Okay. So guys, try that variables problem. I think it's nice. It not nice. Beautiful for today. I'm done. Uh on code forces, check out my recent announcements. So there is the IOI camp for those who are participating in regional Olympiads and then my dynamic programming classes in August in the next month for the price of €250.

2:02:27 Uh problem is usually not beautiful. Well, I agree. Most problems are not but if I say so then there is something about it, right? Okay. Thank you for watching. Have a good day. See you tomorrow. Same time for the easy problems.

Questions about this episode

What is discussed in "CF 1035 (Div. 2) C, E, F | algorithms problem-solving"?

In order: 1:15:00 Google Meet.

What is mentioned in this Errichto Hard Algorithms episode?

3 people, works and ideas are mentioned, including Codeforces, ICPC, Google Meet. Each one on this page links to its own page with every episode that mentions it.

How long is "CF 1035 (Div. 2) C, E, F | algorithms problem-solving"?

The episode runs 2 h 3 min; the transcript is about 13,481 words in 119 timestamped sections.

More from Errichto Hard Algorithms

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