Hard thinking and trying random problem | Leetcode | Codeforces | Atcoder

Ajouté : 2026-05-30

[00:00:17]I'm live, right?

[00:00:19]Yes, I'm live. Let me open the chat window here.

[00:00:25]Cool.

[00:00:29]So today there's no plan.

[00:00:34]We'll try a random problems.

[00:00:41]Are we able to do brainstorming or not?

[00:00:49]Let me sh Okay.

[00:00:55]Should I join or let's start? Uh let me start this L code see I tried this questions this question is pretty good I miss one edge cases like I almost think I almost come up with a solution but uh no I can't say like think is at if it is it Consider it a single cell. It's the edge then it's impossible to take a single cell.

[00:01:38]Let's try quickly.

[00:01:46]Let me try hard.

[00:01:50]Okay, this is also medium question.

[00:01:54]We try this and then I want to see like how fast I can start.

[00:02:01]Okay. You are given a string password.

[00:02:04]The strength of password is calculated based on the following rule. One point for each uh lower case, 2 for upper case, 3 point for digits, five point for special for each character at most one.

[00:02:18]For each character contribute at most one. Okay. And what is the strength?

[00:02:25]Okay. It's not uh it's Hey Rich, how are you?

[00:02:34]I'm good. I'm good. I'm good. So what we'll do here is actually I take a challenge like how fast I can solve.

[00:02:43]Let me first solve this question and we'll I will talk. Uh then fast forward if C if is lower answer + one.

[00:03:03]Else if is upper answer + two. Else if is digit answer + three else answer plus equal to 5.

[00:03:28]Okay.

[00:03:32]B is lower three * 3 is greater than equals to a and n is less than = z.

[00:03:48]Same way the first if is reaches and 0 to 9. I hope this is the solution.

[00:04:06]If okay answer I hope this is the solution. This is this is I will not why why B if it is a lower case we'll add one two for distinct oh each distinct okay it's distinct it's distinct Uh there's something there's a inbuilt function unique there's some for there's something uh there's one unique C++ unique what it will do is actually it remove all the duplicates if you know some inbuilt function then it is very good for you right like in speed run here say this is How resize the vector so that it removes.

[00:05:16]This is what I want to do. So what it does is it's created iterator.

[00:05:24]No, syntax is not user friendly. Yeah, this is what we can do.

[00:05:32]But syntax is not user friendly. Why?

[00:05:36]What we have to do? Unique start and end. What is this?

[00:05:42]No, we'll do usual method now. But I'm not getting Yeah, what I will do is let's not think much.

[00:05:57]Let's not think much.

[00:06:00]Did you guys get it what I'm trying to do here?

[00:06:08]Does anyone get to know this is this is Yay. We get nice AC.

[00:06:31]There's some message. Hi. Hi. Hi. Hi.

[00:06:36]Hi, Rich. How are you? I'm good, man.

[00:06:39]How are you?

[00:06:41]Do you guys have any question to try? I can try that question also.

[00:06:48]Any question to try?

[00:07:04]Or I should try this question.

[00:07:08]I took 4 minute actually 4 point like around 4 and a half minute right that's not pretty where you interactive I don't know why it's showing five users. I thought there are five users.

[00:07:44]Uh we are right right there. There are five content.

[00:07:49]You guys there you can chit chat in my let me try third one then minimum operation to sort a permutation. Let me start the time off.

[00:08:02]Minimum operation to sort a permutation.

[00:08:03]You are give an integer array nums of length n where the nums is the permutation of okay 0 to you can perform the following operation. Reverse the entire array. Rotate left by one. Okay.

[00:08:16]Move the left element and the left.

[00:08:19]Okay. What they're trying reverse the entire array. Okay.

[00:08:23]Rotate left by one. That what that mean?

[00:08:26]move the first element to the end. Okay, that means we can move this to this and rest element by one position. So it's like one left strip return integer denoting the minimum number of operation required to sort.

[00:08:45]Okay. Okay. Okay.

[00:08:48]So we can reverse the entire array. Okay.

[00:08:55]We can't reverse the part right the part of ar.

[00:09:03]So what my like what in this is one point like one small observation what we can do is we can build 0 1 2 3 or we can build 4 3 2 1 zero and we'll perform one if this is giving minimum then we'll perform one more operation to reverse the entire array to get 0 1 2 3 4 whichever is the minimum is this or this case that is the answer right Now uh wait I'm not still not getting rotate left by one. Move the first element to the end of the array and return the min number operation required to sort in increasing order. If it is not possible to sort the we have to return minus.

[00:09:55]Three. Now the point is it's also possible we are unable to solve to solve right.

[00:10:05]So my question is array should always in a circular uh yeah array should always in a circular man circular manner then then only we can say it is a potential potential input otherwise we have to return minus one. Now how we can check that?

[00:10:28]So you can check like say if you find out the difference 0 1.

[00:10:35]So you will see only one break point uh for example say if it is sorted array and it is a rotated also. So what you will observe is this and you will start observing this or what you can see is this and it will start. So there's only one break point. If there is only one break point that means we have our potential answer.

[00:11:06]Yes. Then we don't just we need to find this break point. Let's say we have found out that is the break point is the if index index then our answer is minimum of this or minimum of this + one that's the answer you guys get it I hope this is the solution yeah so Let's just find out the break points.

[00:11:51]What we can do is here firstly we also find out the break point and let me say n is equal to nums dot size.

[00:12:06]Right?

[00:12:09]If nums of I what if we have this array 4 3 2 1 M0. So in this case there is no uh so what we can do is by default we'll consider first element as a break point.

[00:12:39]Okay.

[00:12:47]uh I'm thinking is there in better way to p this you can take your time and think better solution instead of going for a long implementation right yes so I want to check how many break point does this input is it should be worse. Okay.

[00:13:37]And then Perform you want something in order of n and n login input is pretty use input you can't run uh I I'm thinking this right let's observe there any better Can it do something better here or not?

[00:14:28]The thinking is what if it reverse something? What if what does it change?

[00:14:37]it does not change right let's say I have this like 1 2 3 4 five then something smaller than five okay but reverse what does reverse change here Nothing seemed nice.

[00:15:12]What we check here is nums of i minus one.

[00:15:38]There's always a difference of one. See there's one more observation we can put here. There is always a difference of one. If we get difference greater than one that means it's a break point. See this is this is this can be a potential good observation. If if you have a sorted array and it is a rotated let me take example of this error. It's this if you rotate this array two times and for example if I rotate this array this uh three 4 3 0 1 2 we'll see difference is one difference is not one difference is one difference is one right that means we have one break point in this error get it F what we will do is instead of this we'll calculate difference of I - of I - 1 if difference is greater than equal to if difference is greater than equal to that means we have this uh I call as a break point so and Let's put it this index uh index is equal to I right. What I'll do here is if count is greater than one 8 minus one otherwise we have to found otherwise we have to do some work here logic.

[00:17:22]Let let me just test our dummy.

[00:17:26]Did we handle the minus one case?

[00:17:29]Yeah, see we handle this minus in case right now we need to think about how to do.

[00:17:40]Okay. So now we have index a break point uh that is this index. Now we have the break point right.

[00:17:57]See break it as one it's two right two is our break point and here 0 1 2 is our break point or what we can do we can actually make it more meaningful see right now we are unable to identify it is increasing break point or it is decreasing break point We know it's a break point, but is it increasing or decreasing? We don't know, right?

[00:18:42]For that what we have to do is uh it's a break point. That for sure we know 02 for this kind of break point we have to reverse it and then we can sort and here it's a potential good break point. See what we can rotate two time and we'll get our answer. That's fine.

[00:19:22]Okay, we have break point. Now let let me think what we can do with this break point.

[00:19:27]how we can sort uh we want 01 22 and minus one right that is what we want and we know from here we have one more information say a number is always from 0 to n minus Nice.

[00:20:09]That's true. Let's say let's not think much. Uh let's say we have this 1 02.

[00:20:22]Just sort it out. What? Like we want to sort what we'll do here is we want zero to come here to zero 2 and 1 right. What we can do is still this is not sorted. We'll again shift. So it is always in this cycle right?

[00:20:48]uh twos 1 zeros.

[00:20:52]Then again we'll do one then you will see here is 1 0 2 we do one more operation then we get 0 2 and one and we end up with the same foration next don't want we end up like otherwise we'll into a loop So how we can eliminate is we want like see reverse is always mandatory.

[00:21:29]Now reverse is the operation you have to perform first. If you want reverse in your answer right if you want to perform reverse the entire array you have to perform it is the first operation then only then using this operation we will sort out the array. But how will identify when we have to perform reverse. source how we can identify here is uh what I'm thinking is we want order if less than less than less than like if we have something like this then we don't need to perform the reverse say because we want increasing error right so what we'll do here is if we have something like this this order what we'll do is we'll perform one reverse operation and we'll This is this then this becomes you perform reverse and this become the first element then you'll get something like this and this is what we want right.

[00:22:30]So we'll check here what is the order.

[00:22:35]Uh let me take this example. So see 1 is greater than zero and 0 is less than two. Right? So see we have this order this right this so what we'll do here is uh with this break point we'll check here if nums of index minus one is greater than nums of i and nums of uh what I'm thinking is which is our break uh we are storing this is our break Right.

[00:23:21]Huh. So for this element you have to compare with this and this at a break point. This is the break point. Right.

[00:23:34]I just want to know the we have this order or this ordering. That's it. So for for example let me create let's say I have something like this uh four here three here then 4 3 0 1 2 so this is 4 3 0 1 2 means 4 3 0 1 2 it down 4 is greater than 3 greater than 0 is less than one less than two.

[00:24:12]Right? So here if we have something like this, do we need to perform reverse here?

[00:24:29]Uh do we need to perform reverse here?

[00:24:36]No. Right.

[00:24:51]So from this example we get one more observation before this break point every element is smaller than all the element on its right.

[00:25:04]In this case, we don't need to perform reverse operation.

[00:25:08]And let me give you one more example. Uh let's say instead of this, I have this uh 2 1 0 3 and 4. This is also 14. Right? And if you write out this expression, it also give me this.

[00:25:30]Right?

[00:25:32]The point is we always get as say we will not get this if it is a potential if it is the possible input that means we have we can convert this input to a potential fragmentation that's fine that's fine oh got it got it that's fine So in this question actually let me let me summarize what I what I'm trying to do. The question is asking what is the minimum operation you can sort the entire array operation R you can reverse the entire array or you can shift the array by one position left.

[00:26:21]So after lots of thinking I come up with an uh observation that if if if we have more than one break point and break point is I'm talking about the break point means this if we have more than one break point that means it's not a possible if we can't sort the array using this operation so we simply print the minus one for that case and I calculated the break point is in this manner Right.

[00:26:51]So, so now a point is we always have this. Right.

[00:26:59]So, what we'll do here is now I need to check uh before this break point is everything smaller than its right side.

[00:27:12]If it is, so we don't need to perform the reverse operation. That's it.

[00:27:18]Yeah, that is the answer. So what I'll do is I'll create a set in HT and what I'll do then zero as less than index index is just a break point and let me put the values into set dot insert uh nums of I.

[00:27:43]Now I'll check from i is equal to index i is less than n i ++.

[00:27:53]So now what we have to check is if let's say answer is equal to zero.

[00:28:01]If uh nums of i.

[00:28:09]Oh, we need to check this number is smaller or greater. Right?

[00:28:16]What we can do here is we'll find the smallest number.

[00:28:20]Instead of doing this, let me find the smallest number is equal to 1 9 for = 0. I is less than index I ++ mean is equal to minimum of mean comma nums of i.

[00:28:46]If nums of i is greater than mean then you simply do answer ++ and break.

[00:28:57]Right? Now our answer is how many shift we need?

[00:29:03]this many right I - one that's a 012 answer plus = index I think this is somewhat the answer question okay let me remove this okay now the point is why we are getting three Here let's debug then we have this.

[00:29:38]Okay 1 0 and two and this is the case.

[00:29:47]So this is the case uh this is the case where we have to actually perform the reverse. So right now I'm like we track answer is one right and we perform the reverse here. Then 2011.

[00:30:01]Now wait a minute. What's the break point here is two.

[00:30:07]Uh that's the case. See here break point is two.

[00:30:13]Okay.

[00:30:14]Yeah. Yeah. We just need a little bit concrete code that it can handle break point easily.

[00:30:24]See if we perform reverse.

[00:30:31]If we perform reverse then we don't even need this.

[00:30:41]I'll let you know why why I commented out this push part.

[00:30:50]Uh no no this is not good.

[00:30:56]Race bull k= 0 = 1 answer minus = k I'm not sure what I'm doing but I'm doing Someone message that someone has sent me a telegram.

[00:31:31]Are you nihal?

[00:31:41]You can. Yeah. Yeah. There's a nihal.

[00:31:43]She runs through. Do you can if you want to if you want something to ask you can ask in my class right I can answer you.

[00:31:57]Hello I was just finished my 12th standard and also my entrance competitive exams are done. Can you please suggest me something to learn or try out in the remaining two three months which are productive which helps me in my college too. I want to know which field are you planning to do and what are your future goals.

[00:32:20]You can let me know. I will definitely help you.

[00:32:30]So where where we are?

[00:32:33]Uh yeah, right.

[00:32:38]It is one. How is this possible?

[00:32:43]0 2 1.

[00:32:46]Oh, the break point is this. Okay.

[00:32:54]Okay. Break point is this.

[00:33:01]Then we perform reverse. Okay.

[00:33:05]Uh let I got it. I got it. What is happening here? See if you perform reverse then the break point index is changing right. If it is not meter then it if you reverse then break point index is n minus i. If it is I then it become n minus i. Yeah. Yeah. I just want to confirm that is the only potential error. If I perform reverse here then it become zero.

[00:33:28]Uh it's become actually 1 2 and zero.

[00:33:32]Right.

[00:33:35]Yeah. Then I need how many shifts?

[00:33:43]One and two.

[00:33:45]Answer is two here. Right.

[00:33:48]How is this possible?

[00:33:50]We have this I reverse rotate it by one and then reverse. Oh, it is something different.

[00:34:00]I thought if we want to perform reverse, we'll always perform first reverse.

[00:34:06]Seems like that is not true here.

[00:34:13]Wait a minute. I perform reverse here.

[00:34:15]Okay, now I need two shapes. Yeah, perfect.

[00:34:21]Perfect.

[00:34:24]That's not true actually.

[00:34:27]Or it is This is how it is right. I don't know how people are able to solve in two and 3 minutes in the contest.

[00:34:42]If I have question a good question, it's need actually it's it makes you think right and that's what you and if you start thinking and you'll always feel better even though if you are unable to solve that question as quick as possible.

[00:34:58]But the dopamine you will get like yeah today I thought something that is what motivation for me list what I can do here can I perform binary search here no right it's not monotonic it's not want to say like I'm stuck now. No, I don't want to feel stuff. Wait, wait, wait.

[00:35:55]Let me take one hint here.

[00:35:58]The operation generate only rotate of the and rotation of nums and rotation of reverse num.

[00:36:07]Oh, it's a case work. The operation generates only rotations of nums and rotations of reverse of nums.

[00:36:17]Yeah, that's true.

[00:36:19]And we have to print minimum of four of them. Right? That is what we are trying to say.

[00:36:29]Oh, if we have only one break point then always possible to sort right or not.

[00:36:34]Always possible to sort.

[00:36:40]Let's say wait not 012 4 3 0 1 2 Break point is 0 1 2 this is my break point okay expected is minus one how yeah yeah yeah it should be three and Okay. But my code should give minus right. If if I handle that case correctly.

[00:37:51]Yes, it is not able to handle minus one case also.

[00:37:55]Uh Why?

[00:38:03]Why this cola very cola very deep?

[00:38:12]How can I identify it is impossible face?

[00:38:19]Uh let me draw the pattern.

[00:38:22]I think pattern is the only reason.

[00:38:27]Someone is laughing at me. I know I'm dumb.

[00:38:32]I don't know why I'm able to get it.

[00:38:44]Pattern is also correct.

[00:38:49]That means this should be like this. 0 1 2 and it's like this uh greater than right smaller than smaller than this is the correct size right what we get here is three wait I'm out subs.

[00:39:25]Oh, this is what we're getting.

[00:39:30]Let's see if we have more element then.

[00:39:33]This is what we have, right?

[00:39:38]Oh my god. Yes, this is what it is.

[00:39:50]you want this element to clip I don't have any solution in my mind it's only based on observation if I can this is one of the valid if I reverse it out if I reverse it out that look like This this four.

[00:40:26]No, no, no. It's like one and this.

[00:40:37]Oh, it's confusing.

[00:40:40]Let me just give us right less than become greater than and greater than become less than.

[00:40:47]Yeah. So it's become greater than or greater than and one this then I think this. Okay.

[00:41:00]These are the two potential faces.

[00:41:11]We have used almost 30 seconds.

[00:41:33]No, no, this is not hard. It's a four point, right? Or it's a five point, right?

[00:41:40]Five points are pretty hard.

[00:41:47]We can do here is let me start saying the examples. Let's say we have 0 1 3 4 and five.

[00:42:01]What we do is we have this answer is zero. How is it approach?

[00:42:07]We have this question right next 5 4 3 2 1 answer is below.

[00:42:31]Can we manipulate in some manner?

[00:42:39]Yes.

[00:42:43]1 5 3 2.

[00:42:55]Okay.

[00:43:00]What will be the answer in this case?

[00:43:05]One is less than five.

[00:43:08]You need to perform one lapis. Answer is two here.

[00:43:19]text.

[00:43:25]So sorting is for solution on which number is rotated or increasing order or rotated in a decreasing order.

[00:43:35]Okay.

[00:43:36]The sorting is possible if the number is if and only if number is located increasing order or decreasing order.

[00:43:51]Okay. Now we'll identify this the number and then left time so that in reverse again take the minimum ro okay number try both possibility reverse first or rotate first and then reverse and take the minimum first. Okay.

[00:44:19]Yeah. This is what I'm thinking of as follow the in one. Each receable array can be represented as a state.

[00:44:30]Since all receable array belongs to one of two families one can compress state into type is equal to z and a rotation of original f= 1. A rotation of a reverse array. CF denote the number of left rotation applied within the rest rotation changes safe by false changing the corresponding uh this is not I need to learn this concept like I got it what they're trying to But I'm unable to identify while reading the question. Let's I have to represent it into state.

[00:45:24]Okay. Okay. That's fine. Let's try add folder right for the question.

[00:45:34]Yeah. Today I missed that folder. Right.

[00:45:38]We can try at folder BC.

[00:45:43]No, no, no, no, no big story.

[00:45:47]Something smaller. I will try query optimization. It is query optimization for sure.

[00:46:01]So if we try this if there are people waiting to see out of course then only we try otherwise we'll land the stream and we'll try a contest tomorrow a fresh contest.

[00:46:21]The cash is trying to buy an items at a supermarket. A regular price of J item is CIN that she must purchase all an item. This supermarket offer a tight discount service based on the total amount in a single check out. There are three ties I don't have energy to reach.

[00:46:47]I I will I need to is in my mind to do this anyhow.

[00:47:15]It's Wi-Fi off. I I'm back again. I first powered somewhere maybe what are the things you can see here.

[00:47:37]Okay.

[00:47:39]Yes, it is fine.

[00:47:44]That's all for today.

[00:47:48]Thank you guys for joining. Bye-bye.