Observation skills from Codeforces Underground

Hinzugefügt: 2026-05-25

[00:00:00]In this video, we will look at a problem that requires very sharp observation skills. This problem recently appeared in a code forces round. And this is the kind of the problem where if you're not paying close attention to the details, then no matter what algorithm or data structure you have studied so far, you will not be able to solve it in an optimal time complexity. Because usually what happens is that whenever you learn a new data structure or algorithm, you try to enforce that data structure or algorithm into any new problem that you see. So you try to see okay can I solve it with interval DP? Can I solve it with DP on trees? But this approach can usually backfire and if you are somebody who takes this approach then you will not see fast growth on food forces. In fact, I would say that the current meta on code forces is highly inclined towards more observation based problems and I kind of agree with it like it should not be just bashing known algorithm or data structures that other people might not know. So this is one of these problems that kind of levels the playing field by making sure that you actually understand all the intricate details about the problem instead of just applying some patterns or tricks that you have seen before.

[00:01:30]So let's talk about the description of the problem. It says that you are given two arrays A and B. These are arrays A and B. It can contain inteious positive integers let's say from 0 to 10 ^ 9 or any upper limit value and you are allowed to do a series of operations on it the order of which you can decide and in one operation you have to select two adjacent elements. So you pick these adjacent elements. So you pick this is the index I and this is the index I + 1.

[00:02:07]So since you have this array A and B then of course they will have some values written over there A, B, C and D.

[00:02:13]I have labeled them as such. Then you pick these four values and sort them. So once you sort them, this is the sorted order that you might get. This is just arbitrary sorted order. Then you have to delete these four elements and then add just these two elements. So in a way if the original array contained n elements now it will contain n minus one elements. If you look at the individual arrays, basically what you do is you delete A and B from here and you replace it with the second smallest element and you delete C and D from here and you replace it with the third smallest element which is Y. So after this reduction of course the array length will be reduced by one for both A and B and of course A and B will always have equal length after this reduction.

[00:03:21]So given this A B C D the idea is simple. You sort all these values and then you remove the minima and the maxima and you place this second smallest on top and the third smallest at the bottom.

[00:03:39]So now you can see that there are multiple ways to do this operation because you can freely pick whether you want to merge these two because essentially what you're doing is you are picking these two I and index I + 1 and you are merging them collapsing them together and four elements these four elements collapse to just two elements.

[00:04:00]So since you have multiple choices to do this collapse then there could be multiple final result remaining. Now you can see that this set of operation it will terminate after n minus one rounds. Why? Because in every round you decrease the size of each array by one. So at the end you know that you will have just one single element remaining which is x over here and y over here.

[00:04:33]So you have to maximize this value that is what is the you compute what is the minimum element out of these two and whatever the minimum element comes out to be you have to maximize that minimum.

[00:04:52]Now this is the entire problem statement and your constraints I would mention that it is up to 10 ^ 5 n could be as large as 10 ^ 5. So you have to come up with an optimal solution to this problem.

[00:05:11]So how do you solve this problem? So take a minute to pause this video and think about different approaches that you could try to solve this problem. So in this video we will focus on some key observations and some thought process behind how to solve these kind of problems.

[00:05:33]Now one thing that you can observe that you are asked to maximize the minimum element of certain quantity and usually in these kind of problems one thing that works usually is binary searching on the answer which doesn't always work but this is something that you could explore Right. So of course binary search on answer would be a prerequisite to this video but that is just about it. That is the only prerequisite. Interval DP or any other advanced con concepts is not a prerequisite to this video.

[00:06:22]Now let's start with the first observation. So you know that in one operation you are taking this a b c and d and you are sorting them over here and replacing it with x and y. So one thing that you can be sure that the final answer the final answer is in your array because you are not introducing any elements from the outside world. So this is the first observation that might not be obvious to a lot of you that since this is just a sort operation then your answer has to be one out of the 2n elements that are present in your array.

[00:07:13]Now let us see whether binary search would actually work on this or not. Like if you wanted to do binary search on answer uh let us see if if this problem even admits the binary search on answer solution or not. So suppose you wanted to know is the answer is answer greater than or equal to x. This is the general setting for binary search problems we have.

[00:07:49]Now if you draw this x on the number line suppose this is x over here this is 1 and let's say this is infinity.

[00:08:02]Now our goal is to maximize the final value. So if I tell you that yes there is a configuration in which the final answer which is minimum of x y right which is the minimum of x y is greater than or equal to x then since you already have a configuration in which The answer is on this side from x to infinity. Would you ever want to check for the feasibility on the left hand side?

[00:08:50]The answer is no. Because there is at least one configuration where the answer lies on this right hand side. So even if there are multiple configuration where the answer lies on the left hand side, why would you pick them instead of this one answer that was strictly greater than or equal to x and residing over here because you have to maximize the value. So first uh first check for the B binary search is correct that if the answer for greater than or equal if this is equal to yes this means that you don't actually have to check the left half. Why would you want to check the left half when you already have one configuration that achieves this value? So you can discard this left half. But then you also have to prove to me that if the answer is no then you can discard the right half.

[00:09:45]So let's say if the answer for this question is no that there is no configuration in the world where the answer is on this right half.

[00:09:59]Right. So then can you actually discard this entire right half?

[00:10:07]Yes, you can do that because suppose there is one configuration in this right half for which you shouldn't have discarded. Suppose this value was actually achievable. This value is y.

[00:10:20]But if this value is actually achievable and if our binary search algorithm logic is correct then why did this value not surface when I asked this query? Does there exist any answer which is greater than or equal to x? So if this told me that no nothing greater than or x is equal to is possible and this did not show up there it means that this right half is actually useless because if nothing greater than or equal to x is possible it means that nothing on this big range is possible. So even if you try to shorten this range by looking at this smaller range which is x plus let's say delta nothing in this range will also be uh possible. So this means that given any x if you can quickly find out if the answer is greater than or equal to x. I'm not talking about the case whether answer is exactly equal to x. I'm talking about the case where answer is greater than or equal to x. So you can safely discard the right half if this turns out to be false and you can safely discard the left half. Why you can do that? Because you have already found one candidate for your answer. So why do you want to worsen the answer by looking into the left half?

[00:11:40]So one thing is clear if we can answer this question.

[00:11:45]So let's write let's reformulate the problem that given x can you find out if the answer is greater than or equal to x because if we can do that then we can do a binary search on this x and we will get our answer.

[00:12:10]So let's see how do we solve this problem.

[00:12:15]Now how do you figure out if the answer is greater than or equal to x? So once you apply this binary search and you will remember this that in these kind of problems I have recently added a video on my YouTube channel which I will also link in the YouTube description or the comments where I talk about DP on medians where I have told you that there is no rule book to solve DP on median.

[00:12:44]There is no rule book to solve median problems. But there is a nice trick to convert median problems to just plus ones, minus1's and zeros. And with this conversion, we now go into a known territory where we can apply dynamic programming.

[00:13:05]So this binary search kind of follows that same principle that is we don't have any rule book for solving maximizing the minima or minimizing the maxima problem. But once you apply the binary search suppose you want to apply the binary search and answer trick on this part where you want to know if the answer is greater than or equal to x then you can go to each element. Suppose this element is a then you can see that if a is greater than or equal to x you replace it with a one but if a is strictly less than x you replace it with a zero. So now you see that we are already moving into a known territory which is a binary string of consisting of zeros and ones. So suppose after this conversion it could look like 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 and so on. So in this reduced version what is the final state that we want to achieve? What final states are achievable? So final states could either be 0 0 or it could be 1 1 or it could be 0 1 or it could be 1 0.

[00:14:30]Now here if you have been noticing closely you will realize another sharp observation that is actually not obvious to see is that the problem is asking you to maximize the value of this minima.

[00:14:47]But if you look at this algorithm that we are applying that is we are sorting and then we want to place the smallest the second smallest over here and the third smallest over here. This means that even though the problem tells you to minimize x y if you have been noticing carefully minimum of x y is actually equal to x.

[00:15:15]Why is that? because we placed the second smallest element over here and the third smallest over here. This means that y will always be greater than or equal to x. This means that if you want to find out if the answer is greater than or equal to x, it means that you have to have a one at this position. And then if you are having a one at this position, you will want to have a one at this position also because this 1 zero is not an acceptable answer because this means that this element did not actually participate in any of the rounds. So this is actually not a feasible final state because looking at this you might think that okay either I can achieve this state or I can achieve this state. But actually if you play if you pay close attention only this state is achievable because this this will always be the minimum value. But if one is the minimum value and your array consist of just zeros and ones, then this second value always has to be one. So this means that you have now transformed this problem to a binary string problem where you are given two binary strings A and B and you have to achieve you have to tell me whether there is a way to achieve this final state which is 1 comma 1.

[00:16:43]This is the modified version of the problem that we would like to solve.

[00:16:49]Now you can see that all of this we have done so that we can get into a known territory and we can apply some data structures and algorithms to simplify it further. But can we do some more simplifications on this? So then you will notice that dealing with two arrays you don't actually know a lot of algorithms that actually deal with two arrays at the same time. So our brains are well equipped to handle one single array. We we know a lot of tricks to do this right some greedy algorithms some DP algorithms and what not. So can we actually do some more simplification so that maybe tracking two arrays is not really needed. So let's see if we can do that. Now you will notice that the possible merges that can happen whenever you merge this whenever you merge two elements.

[00:17:48]So every time you have to merge a block right uh let's say you are merging this block.

[00:17:54]So this time you will only be sorting a string containing zeros and ones. So you you only want to sort four integers 0. So how many possibilities there could be? So there could be 2 into 2 into 2 into 2 which is 16 possibilities. Right? Now you can notice that some of them are actually equivalent because let's consider this.

[00:18:23]Let's consider any index 0 and one. And let's suppose it is being merged with this 1 comma 0. Now you know that all the operations that you are doing is taking two boxes together and you are merging them. And how are you merging them? You are sorting this A, B, C and D and then replacing it with the second smallest and the third smallest. Then the one thing immediately that you can conclude and of course this is not also obvious this also requires some observation skills that the ordering of the zeros and ones they actually do not matter.

[00:19:06]What matters is can you encode this information into just one bit.

[00:19:15]So if I told you that you have one box like let's let's look at at a different slide. If I told you that you have one box at index i which looks like this and another box that looks like this.

[00:19:31]There are only possible four possible ways that it could look like. Right?

[00:19:36]Right. So you know that whenever you merge two boxes from left whenever you merge two adjacent boxes you just take the elements from here and you just sort them. So you just need to keep track of the count of zeros and ones and whatever is the ordering because this box is actually identical to to this box. Why?

[00:20:00]Because you will eventually sort these elements. So this gives us another hint and this is the next sharp observation that you can define a new array let's say s and this s of i would denote Let's say you define this s of i is equal to a of i plus b of i.

[00:20:26]This means that s of i basically tracks.

[00:20:30]So this s of i basically tracks what is the sum of these two values. And when we talk about sums in the binary worlds, sum is nothing but the frequency of one.

[00:20:42]Right? So frequency of one.

[00:20:48]So this means this this can get converted to just one single integer that encodes this entire information because ordering does not matter. This also gets converted to one integer which is one. This also this gets converted to zero because there is no one and this gets converted to two. So now you see that we have transformed it finally to a world that we are most familiar with.

[00:21:14]And what is that world? The transformed problem you can see is that this is the transformed problem.

[00:21:33]Let's pick this.

[00:21:36]So you started from here and let's say it had 0 0 and this had 1. This had 0 1 and this had 1 0. Then you take this A and you take this B and you say that okay this is 0 0 so you add their sum 0 this is 1 1 so you add their sum as two this is 0 1 so you add their sum as one and this is 1 0 you add their sum as 1.

[00:22:00]So the transformed problem is that given just one single array. See this time you don't actually have to deal with the hassle of two arrays. Our brains are not actually that equipped to handle multiple things at once. So we have done some simplification and then we are saying that given a single array that contains integers between 0 1 and two the final state that you want to achieve is 1 comma 1 which is in this transformed state two. So this means that you are given an array consisting of a consists of 0 1's and two. Can you achieve the final state of two when you are allowed to merge some elements? So all we have to do is we have to figure out what happens when 0 merges with one, one merges with two, two merges with zero and so on.

[00:22:55]So there could there will be a 3 + 3 transition matrix for the merge. And let's look at all the transitions matrix. Now let's talk about the merge.

[00:23:07]So how do we do the merge?

[00:23:12]And before we do that, before we do that, in case you are watching the video, uh just so that uh just so that you don't lose track of what we are discussing, let me actually write down the simplified version of the problem that is given an array consisting of 0 1 2.

[00:23:41]Can you collapse them together to achieve a final value of two, right? And the collapsing rule we are going to tell you right now like what happens when two elements collapse together. Now let's say that you have this zero.

[00:24:06]If you have zero now what happens when 0 merges with zero this means that when 0 merges with zero then 0 means that first box had 0 0 and this means that the second box had 0 0. So if you sort them together the end result that you would get would still be zero.

[00:24:32]So 0 and 0 merges to create zero. Now what about 0 and 1?

[00:24:42]So this means that the first box was 0 0 and the second box the sum is one. It means it is 0 and 1.

[00:24:52]So when you sort them together you will get 0 0 0 1 and one will cancel out and you would get zero over here.

[00:25:03]And what happens when you merge 0 with two?

[00:25:12]So when you merge 0 with two, first box will have 0 0 and the second box must have contain 1 1 and you when you sort them you will get 0 0 1 1. And then you have to take the second smallest third smallest which is 0 + 1. Then this means that when 0 merges with two it produces 1.

[00:25:39]Okay. Now what about the case when one what what is the merging strategy for one? So again when one merges with zero this part we have already discussed in the previous slide. When one merges with zero it reduces zero. So we write down zero over here.

[00:26:00]When one merges with one we write down. Okay. So we have to talk about this case. So when one means you will first box will contain 0 1 and the second box might have also contained 1 0. When you actually sort them it will produce 0 0 1 1. And then second smallest is this. Third smallest is this. And their sum is one. So one merging with one produces one.

[00:26:27]and one merging with two. Let's talk about this.

[00:26:34]So this means first box contains 0's and two means second box contains 1 one and when you sort them so you will get 0 1 1. So this means that second smallest is one third smallest is one. So one merging with two produces two.

[00:26:53]Now finally let's talk about the case when two merges with anything.

[00:27:00]So when two merges with zero this part we have already discussed let's check two merges with zero produces one and two merges with one produces two.

[00:27:21]Finally, the only thing that we have to discuss is what happens when two merges with two. So the first box will contain 1 comma 1 and the second box must have contained 1 comma 1. So when you sort them you'll get 1 one one and then it will produce two. So you have the transition matrix that is given this problem statement that given an array consisting of zeros ones and two you have to collapse them together and in one operation what you have to do is in one operation you have to select two index and merge them and how do you merge them? You check what is the first index. If it is zero and the second index is two, you look from your table what to do. 0 and two goes to where and one and one goes to where etc. So you know that you can do this operations in any order and you might get several final result and your goal is to achieve the final result of two.

[00:28:18]So how do you solve this problem?

[00:28:22]So you can notice that this is the classic interval DP and in interval DP because the order of the merges that you are doing that will influence what is the final element that is remaining right so if you define something like this you say that DP of L R or let's say DP of I J I J K or J S means can you merge the substring str substring a i to j or let's say can you merge the subarray a i to j to a state s and s mean s could be in 0 1 and two of course right or instead of merge Let me say can you collapse the subarray into this state.

[00:29:31]Now this is this is of course the classical setting for uh interval DP.

[00:29:36]Now how do you perform the transitions?

[00:29:40]Then you might say that okay you have to look at the last merge because in interval DP you usually look at the first merge or the last merge. So the last merge could suppose that last merge is happening at this index. This means that if this is the last merge then all of these elements have collapsed into one single block and all of these elements have collapsed into one single block and you want to combine those blocks to create just one single element at the end.

[00:30:17]This means that if you want to figure out uh you can say that if these elements have collapsed into one block and the value of the block is let's say LHS the block value the final block value could be anything it could be 012 and similarly all the elements on the right hand side they have been collapsed to a block on RHS then you simply do the merge for LHS and RHS and you Hence you will then get the final possible value for the entire subarray.

[00:30:52]But the time complexity would of course be O of N cubed. Why? Because for each subarray you want to find out what is the optimal uh point where you want to do the last merge. So the in inter in interval DP of course you want to say that okay this is the optimal point you where you want to do the last merge but you don't know where this optimal point is. So you actually try all of these optimal points and then you check okay if this is your optimal last merge point. Then can this array be collapsed to LHS and can this array on the right hand side be collapsed to RHS and if they can then I can merge LHS and RHS together to create the final state for this entire array.

[00:31:37]And this way you can solve this problem at in O of N cube for the reduced version. And since we were doing a binary search the entire problem can be solved in n login. So how let's look at the implementation. So of course first we need the transition matrix so that we have to know when 0 merges with zero what element it produces. 0 merges with one what elements it produces and so on.

[00:32:01]So this is just the 3 +3 transition matrix that we have that we had uh discussed and that I have just not noted down like when two elements merges what happens.

[00:32:14]Then this is this is nothing but uh the same thing written down in a matrix format and then you do a binary search that is you say that your uh in this problem the highest value is 2 into n but this algorithm will still work if the highest value is infinity like let's say 10 ^ 18 that should still work and then you do a binary search and then you say okay for if you have fixed the threshold as x then all the elements that are greater than or equal to X they will be counted as one and all the elements that are smaller than X they will be counted and at zero and then you do an interval DP to see if the interval DP can give you the final state of two.

[00:32:56]If the final state of two is possible it means that there is a configuration in which you can achieve greater than or equal to X. So you strip the left half otherwise you strip the right half. So let's look at that interval DP solution.

[00:33:12]So this interval DP you can see that since this is a known territory because you only have to deals with zeros and ones and you know the merging strategy for any two elements and any two elements whenever they merge they only produce zero once and two. So then you figure out okay what is the point on the last merge. So the last merge at can be for any subar L2R the last merge can be at any position in between. Suppose this is the last merge point. Then you have to find out okay what are the possible states in which the left hand side could be collapsed to. This could be 012 and the right hand side could also be collapsed to 012. And if it is possible to collapse the left hand side to 012 and the right hand side to this value then you collapse them using your transition matrix and you say that it is possible to achieve a result of 0 1 or 2.

[00:34:07]So you can see that this solution of course works. There is no doubt at all about the proof of correctness for the solution but the time complexity is n cq login and n is up to 10 ^ 5. So how do you optimize and in fact how much actually do you optimize because first you have to go to n² login then you have to come to n login and actually going from n cq login to n square login is also not obvious from this. So you you can try multiple things. I also tried a lot of things to see if we can optimize this interval dp to n square login. I could not come up with any approach. So that's why I had to look at it from a different perspective. And that is where the sharp observation skills that we talked about earlier, right? That would come into play. So take a minute to pause this video and think about how given the information that we have that we have so far that is this is the problem that we want to solve. Forget the original problem. This is the problem that we want to solve that given a array containing zeros once and two and this is how zero transitions this is how ones transition and this is how true's transition can you achieve a final result of two. So try to think of an approach to do that and maybe don't focus too much on the interval DP optimization but look at it from a fresh perspective. So this kind of creativity is what will lead you to higher ratings on code forces. So think about some innovative ways to look at these transitions and come up with a different strategy that doesn't actually involve DP because DP is actually evaluating a lot of possibilities. But what if you are smart enough and and you can already determine the optimal strategy without any DP. So think about it for a while.

[00:35:56]So to do that the only thing that we can focus on is the transition matrix because this problem in general I think it should only be solvable via interval DP but if your transition matrix have something special then maybe you could optimize it. So let's look at this transitions again.

[00:36:16]So let's say that let's see how does zero transforms. So this 0 this 0 transforms from on the right hand side we have 0 0 1. So let me write it like so 0 going with zero it gives 0 it gives zero and it gives one. Now what what about the transitions for one?

[00:36:54]So for the transitions for one on the right hand side we have 0 1 2.

[00:36:59]So we write this goes to zero this goes to 1 and this goes to two. And finally, what about two?

[00:37:29]So on the right hand side we have 1 2.

[00:37:35]So we have one 2 and two.

[00:37:52]Now focus long and hard on this. And what is the first observation that jumps out?

[00:38:00]The first thing that you can notice this requires a bit of observation that look at the transition matrix for one.

[00:38:08]One produces a sequence which is nicely ordered 0 1 2. This means that one whenever merges with x always produces x.

[00:38:23]This means one is actually useless. So one is actually not doing anything because sooner or so if you consider this array and one is available over here over here over here and over here.

[00:38:34]So no matter what merges you are doing sooner or later you will have to merge with this one. But when you do merge with this one this one will just produce whatever the element that you have merged with. So in fact you can get rid of this one completely.

[00:38:52]One is not needed. one does one does not participate in the merge at all. So the first observation that you can see that one does not participate in the merge because if it does participate it produces the same value.

[00:39:11]So this is one big discovery that we have made is that one is an identity element. One is an identity element. So if one is an identity element then we don't actually have to say that okay one will participate right now or later but whenever one participates even if even if these elements have combined to form a new state which which could be 0 1 or 2 and these elements have combined to form a new state whatever element that one participates with it will always produce that element. So we can actually delete all the ones from the array and our answer will not change.

[00:39:54]This is one major discovery that you say that this one is an identity element and therefore you only have to deal with an array consisting of zeros and twos. So now let's look at what all other observations we can make.

[00:40:12]Okay. So now that we know that the array only contains three elements which only two elements which is 0 and two let us see what the transitions look like. So if you have a zero and it combines with a two we know that it produces what does it produce? It produce one.

[00:40:31]This is what we have seen in this transition matrix. 0 and two combine to produce one.

[00:40:37]And what happens when 0 combines with zero itself?

[00:40:43]It produces zero.

[00:40:48]Now what about the case for two? So when two combines with zero, we know that it produces one.

[00:40:58]And when two combines with two, it produces two.

[00:41:04]So now try to pause this video and make some more smart observations just by looking at this uh transitions.

[00:41:12]So you can notice that 0 and 0 produce a zero. Two and two produce a two. This means that zeros absorb each other.

[00:41:22]You can say that zeros absorb each other.

[00:41:27]And you can claim the same things about two. So twos also absorb each other.

[00:41:34]Now what is the next sharp observation that you can make is that when you have a zero and two they produce a one but we know that one is an identity element. So this means that 0 and two they collapse and vanish because they produce an identity element and that doesn't change the answer because you want to produce two at the end. So so you can say that zero and two collapse and vanish. In other words, see what is your most valuable asset. Your most valuable asset is two because you want to retain a two at the end. But if you see if you if a zero sees a two adjacent to it, you can say that this zero eats your two. Zero eats two.

[00:42:21]So with all of this in mind, now that we know that the array can only contain a run of zeros followed by a run of twos followed by a run of zeros followed by a run of twos followed by a run of zeros and so on. And we know that if you wanted you can actually compress this entire run down to a single zero.

[00:42:42]Why? Because zeros can absorb each other, twos can also observe each other.

[00:42:47]Then you can compress it down to a single run. Then you can compress it down to a single run and the sequence would be something like this.

[00:42:56]Right? And then you can see that since 0 and two they eat each other and produce one and then one vanishes. So doesn't matter. So they will cancel out. They will cancel out. They will cancel out.

[00:43:08]They will cancel out at the end. The only thing that matters is that with this greedy strategy will a two be remaining or not?

[00:43:17]So this strategy is correct but almost like you just have to focus on just one minor thing. It's the fact that sure zeros can absorb each other like the entire run of zeros could become just just one entry one just one zero.

[00:43:39]But these twos they can also absorb each other. But you you will realize that actually it might not be a good idea to absorb all the two togethers. For example, if you have this scenario, let's say if you have this scenario, if you have a long run of twos and you have a long run of zeros and you have a long run of twos over here, then you can see that if you if you do something like this, you collapse all the twos. You collapse all the twos over here and then you retain two zeros. Then you can see that this zero could eat this two and become one and then vanish. And then this zero could eat a two and then become one and then it will vanish. So therefore it it is never a good idea to keep a long run of zeros because they can eat one two on the left hand side and one two on the right hand side. So it's actually better to collapse all the zeros. But for the twos, it's better to it's better to do it only. It's better to just retain the terminal twos. So if you have these twos over here, so it's better to retain these two and these two. But regardless of what you do, you can say that if the number of runs, if the runs of if runs of two is strictly greater than runs of zero, then your answer is always yes. You can always produce uh you can always produce a final two at the end. So why is this greedy strategy correct? because you can see that.

[00:45:25]So let's compress all the runs for now.

[00:45:28]Then what is the if you have like let's say three runs of two then it could look like two two and two and then you only have two runs of zero. So no matter where you place the runs of zero okay you will have to place it like so 2 0 2 02 then you can see that this zero will eat only this two. It will not eat this one because you can collapse all of them into just one. And then this zero will eat this two and then this two will be remaining. Otherwise if you of course if you have more runs of two like this zero and this then this will eat this this will eat this this will eat this and then this will be strictly greater.

[00:46:10]Right? All you have to check if the runs of two is strictly greater because if it is equal like if you have this 2 0 2 0 2 0 2 0 then this zero has to eat at least one entity. So it will eat this they will f they will combine to create one and then they will vanish. Then they will also eat this will also eat. This will also eat and then they will produce one and the final answer would be the identity element one. So you can see that the optimal strategy is already predetermined. You actually did not need to apply the interval DP.

[00:46:48]All you have to do is compute ignore all the zeros. Compute the runs count of zeros and twos which will of course be alternating. And if the run count of uh twos is strictly greater than zero, your answer is one. Your answer is yes.

[00:47:06]Otherwise your answer is no.

[00:47:09]So let's look at the code for that. So you iterate over this this array and if you see a one simply ignore it because it is an identity element. No matter what it merges with the answer that it produces is same. Otherwise, if you see twos, then you start a new run of twos, right? And you count the number of uh you you count the runs of twos otherwise you count the number otherwise you count the runs of ones and then if the run of twos is strictly greater than the run of zeros then your answer is yes otherwise your answer is no. So just a simple so simple code O of N just a greedy strategy works no need for that complicated interval DP thing that we were doing earlier but all of this is just in hindsight right this only was made possible when you made that observation is that one is the identity element then zero eats up two and creates the identity element one which becomes useless and then zeros and zeros absorb each two and two absorb each other. So these kind of the observation skills were needed to solve this problem. At least that is what I think.

[00:48:22]If you have any other easy approach that could be solved without these observations, do let me know in the comment sections. And if you have any other feedback, do let me know in the comment section. Thank you. So the final time complexity would be O of N login.

[00:48:35]uh because since we are just doing the binary search and uh for each binary search in O of N we are able to compute the