1 00:00:00,120 --> 00:00:04,650 You are given an array of integers called a. 2 00:00:05,900 --> 00:00:12,020 And you basically have you basically get to do the following operation for how many times that you want 3 00:00:12,020 --> 00:00:12,210 to. 4 00:00:13,160 --> 00:00:21,290 You can choose a subsegment starting from position L and ending in position. 5 00:00:21,370 --> 00:00:21,720 Ah. 6 00:00:22,760 --> 00:00:31,310 And the replay replace each and every element in that sub segment with the median of these Saberi. 7 00:00:32,210 --> 00:00:33,690 This is what you can do, right. 8 00:00:34,250 --> 00:00:36,590 Big ol L and R. 9 00:00:37,160 --> 00:00:44,300 For example, if L and ah if that subarea was one four four six five its median is four. 10 00:00:44,630 --> 00:00:49,950 So after performing this operation, each and every element here is four four one seven five eight is 11 00:00:50,000 --> 00:00:51,490 five and so on and so forth. 12 00:00:51,500 --> 00:00:51,760 Right. 13 00:00:52,670 --> 00:01:05,060 So what we need to do is to tell Orac if it is possible or not, to convert all this array A into elements 14 00:01:05,060 --> 00:01:05,660 of K. 15 00:01:05,750 --> 00:01:10,820 So it consists only of elements equal to K by performing this operations. 16 00:01:11,330 --> 00:01:12,260 If it's possible. 17 00:01:12,390 --> 00:01:12,680 Print. 18 00:01:12,740 --> 00:01:13,100 Yes. 19 00:01:13,250 --> 00:01:13,940 If not print. 20 00:01:13,980 --> 00:01:14,160 No. 21 00:01:14,690 --> 00:01:15,140 That's all. 22 00:01:15,890 --> 00:01:23,150 So yeah, this problem is not like a very hard core one in which you have to optimize it. 23 00:01:23,160 --> 00:01:23,410 Right. 24 00:01:23,450 --> 00:01:30,230 So it really doesn't ask like what is the minimal number of operations needed to transform this this 25 00:01:30,230 --> 00:01:34,760 array in just to consist of values of key. 26 00:01:35,120 --> 00:01:38,920 It really cares about whether it's possible or not. 27 00:01:39,870 --> 00:01:40,350 So, yeah. 28 00:01:42,300 --> 00:01:42,750 Cool. 29 00:01:42,930 --> 00:01:43,350 All right. 30 00:01:43,440 --> 00:01:45,270 Let's go and solve this. 31 00:01:46,200 --> 00:01:53,280 So again, be prepared, because I'm gonna get you from my line of thought and how I felt about this 32 00:01:53,280 --> 00:01:53,640 problem. 33 00:01:54,420 --> 00:01:58,830 So the following thing struck to my mind. 34 00:02:00,120 --> 00:02:03,510 I have this sabari or a rape. 35 00:02:04,320 --> 00:02:05,830 I don't know why I keep seeing Savary. 36 00:02:05,850 --> 00:02:15,160 But anyways, I always think about the let's say the negative part. 37 00:02:15,420 --> 00:02:15,670 Right. 38 00:02:16,170 --> 00:02:22,950 When I get these kind of problems, either if it's a yes or no problem or you get to tell the elsewhere 39 00:02:22,960 --> 00:02:30,990 or know if there is not any answer or something like that, I always think about when there is no answer 40 00:02:30,990 --> 00:02:31,500 at all. 41 00:02:32,700 --> 00:02:38,470 So I started to think immediate the OK when there is not any answer there. 42 00:02:39,900 --> 00:02:44,640 And the first thing that struck my mind and it's in the first example to. 43 00:02:45,690 --> 00:02:49,650 Is that if you don't have any value key in that array. 44 00:02:50,220 --> 00:02:52,320 Of course, you're not gonna have any answer, right? 45 00:02:53,190 --> 00:03:01,820 If there is no value K, you won't have any Saberi that will have a median equal to K. 46 00:03:02,220 --> 00:03:05,620 So you can't have all those elements to be equal to Kay. 47 00:03:06,880 --> 00:03:10,090 So first observation, super simple. 48 00:03:10,570 --> 00:03:15,580 If in your array there is not any value of K, then you print. 49 00:03:15,870 --> 00:03:16,140 No. 50 00:03:17,140 --> 00:03:21,010 Now what happens if we do have some values of K? 51 00:03:21,640 --> 00:03:23,560 So this is code 46 for one. 52 00:03:23,950 --> 00:03:25,600 And this is D, I think. 53 00:03:25,670 --> 00:03:25,880 Right. 54 00:03:26,980 --> 00:03:28,030 This is the call. 55 00:03:32,120 --> 00:03:33,830 Let us see. 56 00:03:35,030 --> 00:03:36,010 All right, great. 57 00:03:36,560 --> 00:03:40,130 So what happens if there are some failures of. 58 00:03:41,230 --> 00:03:43,540 Let's see here we have some key. 59 00:03:44,290 --> 00:03:46,990 Great, and I started to think like this. 60 00:03:47,950 --> 00:03:56,170 I have to use these values of cake in order to expand and make all the values in my array equal to cake. 61 00:03:57,610 --> 00:03:59,320 So if this is a cake. 62 00:04:00,340 --> 00:04:01,900 Let's take a look at its neighbors. 63 00:04:02,800 --> 00:04:04,180 What are the options here? 64 00:04:04,930 --> 00:04:15,730 Well, I could have either neighbors equal to Kay or neighbors less than Kay or neighbors greater than 65 00:04:15,730 --> 00:04:16,030 Kay. 66 00:04:16,330 --> 00:04:16,630 Right. 67 00:04:17,590 --> 00:04:17,860 Right. 68 00:04:19,450 --> 00:04:22,120 What if this right neighbor is less than key? 69 00:04:22,840 --> 00:04:27,100 If I take this, too, this would be the median, right? 70 00:04:28,400 --> 00:04:35,480 Okay, okay, so this means that if this is greater than Kay. 71 00:04:36,670 --> 00:04:40,420 If I take this to Kate, is the media. 72 00:04:43,620 --> 00:04:45,330 So, bam! 73 00:04:46,320 --> 00:04:47,400 The next observation. 74 00:04:49,990 --> 00:05:01,510 If I take a value of K and one of its neighbors is greater than K, I choose the sequence of these two 75 00:05:01,540 --> 00:05:03,100 consecutive elements. 76 00:05:03,730 --> 00:05:06,700 And when I perform an operation on them, guess what? 77 00:05:07,930 --> 00:05:12,220 This is always going to be transformed into another game. 78 00:05:13,840 --> 00:05:15,220 Let's say this was greater to. 79 00:05:16,230 --> 00:05:16,920 Perfect. 80 00:05:17,190 --> 00:05:22,230 Guess what, I I'm going to apply the operation on these neighbors. 81 00:05:22,980 --> 00:05:26,000 So this is now going to be also equal to Kate. 82 00:05:27,940 --> 00:05:28,750 Perfect. 83 00:05:29,890 --> 00:05:30,820 Very nice. 84 00:05:31,510 --> 00:05:38,230 So what happens is when I have some value of K. 85 00:05:40,080 --> 00:05:43,830 As long as I have only neighbors greater than Kay. 86 00:05:45,580 --> 00:05:46,750 I just perform. 87 00:05:47,640 --> 00:05:50,550 These sequences of operations, first of all, this one. 88 00:05:50,820 --> 00:05:52,410 And this is now also okay. 89 00:05:53,100 --> 00:05:53,430 Right. 90 00:05:54,210 --> 00:05:54,960 This is a key. 91 00:05:55,410 --> 00:05:57,060 Then I perform this one. 92 00:05:57,210 --> 00:05:57,480 Yes. 93 00:05:57,480 --> 00:05:57,810 What? 94 00:05:57,840 --> 00:05:58,680 This is a key. 95 00:05:59,070 --> 00:06:00,690 Then I perform this one. 96 00:06:00,750 --> 00:06:01,590 This is a key. 97 00:06:01,950 --> 00:06:02,790 Then this one. 98 00:06:03,690 --> 00:06:04,320 This is a key. 99 00:06:04,380 --> 00:06:04,620 Right. 100 00:06:04,650 --> 00:06:05,250 This is a key. 101 00:06:05,700 --> 00:06:13,600 So all I can do is that if the key has neighbors of greater key on the right and neighbors. 102 00:06:13,680 --> 00:06:15,750 Greater than key on the left. 103 00:06:16,440 --> 00:06:19,560 I can extend and make all of those numbers equal. 104 00:06:19,650 --> 00:06:21,660 Okay, cool. 105 00:06:22,530 --> 00:06:23,850 So the real problem here. 106 00:06:23,880 --> 00:06:25,150 I almost fall there. 107 00:06:25,650 --> 00:06:30,240 The real problem here is that what happens when my neighbors are less than. 108 00:06:33,550 --> 00:06:35,410 So let's suppose. 109 00:06:37,520 --> 00:06:42,680 I have performed as many operations like this that I could. 110 00:06:43,260 --> 00:06:45,170 K and Greater Neighbor. 111 00:06:45,580 --> 00:06:45,880 Bam! 112 00:06:45,980 --> 00:06:47,810 That neighbor risque and so on and so forth. 113 00:06:48,410 --> 00:06:56,390 So what happens now is that I'm left with an array in which each neighbor of key is either a mother 114 00:06:56,390 --> 00:06:59,270 value of key or someone less than key. 115 00:07:00,440 --> 00:07:06,200 So basically there is like this k k k dad, that key. 116 00:07:07,570 --> 00:07:11,100 And less than Kate, less than Kate, less than Kate, less than Kate. 117 00:07:12,600 --> 00:07:14,410 Then again, k k that. 118 00:07:14,470 --> 00:07:14,910 That Kate. 119 00:07:16,440 --> 00:07:17,690 Less than Quiles, then, Kate. 120 00:07:19,200 --> 00:07:20,990 Keiki and so on and so forth. 121 00:07:23,130 --> 00:07:28,470 So after performing all those operations, this is what I'm left with. 122 00:07:30,570 --> 00:07:31,920 All right. 123 00:07:32,880 --> 00:07:36,090 Well, this is kind of impossible. 124 00:07:37,260 --> 00:07:38,040 That's for sure. 125 00:07:38,730 --> 00:07:42,480 I mean, it's not necessarily impossible. 126 00:07:43,050 --> 00:07:46,440 By the way, when I thought about the problem, I thought this was impossible. 127 00:07:46,440 --> 00:07:46,920 But it's not. 128 00:07:47,100 --> 00:07:48,330 So stick with me. 129 00:07:49,260 --> 00:07:51,090 I can take this to case. 130 00:07:53,280 --> 00:07:58,260 And have them taken, we have this less element. 131 00:07:59,070 --> 00:07:59,700 And guess what? 132 00:08:00,030 --> 00:08:03,180 Because they have two values equal to Kay and one less than Kay. 133 00:08:03,810 --> 00:08:05,100 The median is Kay. 134 00:08:05,940 --> 00:08:10,410 So this element less than Kay is now. 135 00:08:10,410 --> 00:08:10,650 Kay. 136 00:08:13,290 --> 00:08:15,510 Let's say this is another element less than key. 137 00:08:15,930 --> 00:08:17,250 I have read case. 138 00:08:18,350 --> 00:08:23,180 If I have free gays and only one less than Ky, I can eat him basically. 139 00:08:23,480 --> 00:08:25,860 And I want to transform him again into another cake. 140 00:08:26,930 --> 00:08:27,920 And so on and so forth. 141 00:08:29,000 --> 00:08:32,870 So what I figure now, which is really cool, is the following week. 142 00:08:34,580 --> 00:08:36,470 Either if I have a value of key. 143 00:08:37,620 --> 00:08:38,820 And something. 144 00:08:41,060 --> 00:08:42,170 Greater than Kay. 145 00:08:43,610 --> 00:08:47,060 I'm gonna convert this into K.K. 146 00:08:48,120 --> 00:08:52,460 Or if I don't have any neighbor, which is greater than Kay. 147 00:08:53,190 --> 00:08:55,290 So basically both of them are less. 148 00:08:56,150 --> 00:08:57,920 Not both of them are less or equal. 149 00:08:57,930 --> 00:08:58,310 Sorry. 150 00:08:58,650 --> 00:08:59,490 So I have a kid. 151 00:09:01,310 --> 00:09:03,050 If this was greater, I would have done this. 152 00:09:03,940 --> 00:09:04,930 If this is less. 153 00:09:06,910 --> 00:09:11,860 My only chance is to have another key here to back me up. 154 00:09:12,640 --> 00:09:17,050 If this case can back me up here when I choose this. 155 00:09:22,040 --> 00:09:26,530 So I am able to convert this into a KKK, right? 156 00:09:27,290 --> 00:09:36,740 So the final solution is if I have a key and this is less. 157 00:09:38,020 --> 00:09:38,790 And this is less. 158 00:09:40,700 --> 00:09:44,230 No, I'm basically stuck because I don't have any case to back me up here. 159 00:09:45,540 --> 00:09:52,860 If I did have a key here, that's great, because I can take this sequence right. 160 00:09:54,090 --> 00:09:59,520 Or some key here, maybe this is also great because I can take this sequence. 161 00:10:00,900 --> 00:10:02,910 But if I don't have those. 162 00:10:03,840 --> 00:10:14,460 And let's say this is all so less and this is also less for is going to be quite hard, you know. 163 00:10:15,660 --> 00:10:23,680 Right now I'm really kind of stuck because each and every Southbury that I choose from here is not gonna 164 00:10:23,700 --> 00:10:24,540 convert me 165 00:10:27,300 --> 00:10:28,520 all these values to key. 166 00:10:29,790 --> 00:10:32,370 Let's say I have someone to save me here. 167 00:10:32,370 --> 00:10:35,220 Some key here and maybe another one here. 168 00:10:36,330 --> 00:10:38,460 Then everything's fine. 169 00:10:38,970 --> 00:10:39,480 You know why? 170 00:10:39,990 --> 00:10:41,110 Because I can choose this one. 171 00:10:43,430 --> 00:10:46,880 Free case and two less, so the median is key. 172 00:10:47,390 --> 00:10:48,710 And this one's R.K. to. 173 00:10:49,710 --> 00:10:54,330 But even more important, I can choose this one. 174 00:10:56,500 --> 00:10:58,520 I because they have two consecutive case. 175 00:11:01,890 --> 00:11:08,150 But did you notice here, if I have a key and something greater than Kay, everything's fine. 176 00:11:08,390 --> 00:11:09,980 I convert that into key. 177 00:11:11,090 --> 00:11:18,920 If I have two consecutive case, everything's fine, I convert the first one just either to the right 178 00:11:18,980 --> 00:11:20,810 or to the left into another key. 179 00:11:22,850 --> 00:11:26,750 But if I have a KIA, we have two less than Kia. 180 00:11:28,050 --> 00:11:36,790 The only thing that's gonna save me is that somewhere in the future, like here on the right, I'm gonna 181 00:11:36,810 --> 00:11:44,820 have, again, two case that are that are consecutive or maybe. 182 00:11:46,310 --> 00:11:52,740 These two weren't here, so I would have had less Leskie, less, less. 183 00:11:53,240 --> 00:11:54,650 And some other lassies. 184 00:11:56,190 --> 00:11:57,240 Some key here. 185 00:11:58,840 --> 00:12:01,320 Maybe another less and some key here. 186 00:12:02,340 --> 00:12:11,700 This is also going to save me because even if these two case are not consecutive, I can take three 187 00:12:11,700 --> 00:12:13,500 consecutive positions. 188 00:12:15,130 --> 00:12:16,550 Where two of them are kids. 189 00:12:17,770 --> 00:12:18,550 And this is it. 190 00:12:19,660 --> 00:12:21,810 This is all you need to have in this string. 191 00:12:23,860 --> 00:12:28,510 If in this string, you have at least one. 192 00:12:29,960 --> 00:12:38,930 Toppled one Saberi of free consecutive positions such that at least two of them are key or greater. 193 00:12:39,440 --> 00:12:42,140 They could be greater, but not both of them. 194 00:12:42,170 --> 00:12:49,240 Because if I have greater, greater, less than the median, is this greater, which is not OK. 195 00:12:49,850 --> 00:13:00,080 I need at least one key and something greater than K, one K and something greater than K. 196 00:13:01,190 --> 00:13:01,490 Right. 197 00:13:01,910 --> 00:13:04,850 So what happens now is that. 198 00:13:06,290 --> 00:13:13,940 I need to have at least one Saberi of free consecutive elements where two of them. 199 00:13:14,960 --> 00:13:17,030 Are greater or equal than cake. 200 00:13:18,680 --> 00:13:22,970 But as I've told you, this case could be a problem. 201 00:13:24,860 --> 00:13:33,470 Well, it's not that big of a problem because even if I have this case and I choose to apply an operation 202 00:13:33,470 --> 00:13:34,070 on this sub. 203 00:13:34,070 --> 00:13:34,430 Eric. 204 00:13:36,180 --> 00:13:39,330 It's gonna look like there's no greater greater great. 205 00:13:41,350 --> 00:13:41,830 All right. 206 00:13:43,330 --> 00:13:44,470 So now they are Rayder. 207 00:13:46,050 --> 00:13:48,060 Let's say I had something less. 208 00:13:48,940 --> 00:13:53,070 Oh, I can apply this again and I'm going to make this greater. 209 00:13:54,810 --> 00:13:57,650 Then let's say I have some key here. 210 00:13:58,680 --> 00:14:01,170 Ha, that's amazing. 211 00:14:01,560 --> 00:14:02,760 I can take this, too. 212 00:14:03,090 --> 00:14:04,200 And now this is K.K. 213 00:14:04,620 --> 00:14:05,880 I can again take this, too. 214 00:14:05,910 --> 00:14:10,360 And this is K.K and this is exactly the case that we have spoken in the beginning. 215 00:14:11,010 --> 00:14:16,140 So the conclusion is the problem is a little bit tricky. 216 00:14:16,140 --> 00:14:21,600 Like you really have to use your pen and paper or in my case, my pen and my graphic tablet. 217 00:14:23,070 --> 00:14:25,080 You need to use the pen and paper. 218 00:14:27,260 --> 00:14:37,220 And draw a lot of examples in order to figure out what happens when after seven examples drawn here. 219 00:14:38,660 --> 00:14:39,560 We can't figure out. 220 00:14:42,170 --> 00:14:44,990 That this problem has a solution. 221 00:14:46,220 --> 00:14:49,910 If, first of all, there is at least. 222 00:14:54,990 --> 00:14:56,520 One key. 223 00:15:00,930 --> 00:15:05,100 There is at least so there exists some sequence. 224 00:15:05,190 --> 00:15:05,490 I. 225 00:15:06,820 --> 00:15:09,600 I plus one, I plus two. 226 00:15:12,760 --> 00:15:15,160 There are at least. 227 00:15:17,560 --> 00:15:21,830 Two elements, greater or equal than key. 228 00:15:22,420 --> 00:15:23,560 And this is it. 229 00:15:23,860 --> 00:15:25,060 You just need to check this two. 230 00:15:26,230 --> 00:15:32,220 And as I've told you, if this doesn't hold, we have seen all the examples. 231 00:15:32,290 --> 00:15:34,000 If this holds, everything's fine. 232 00:15:34,330 --> 00:15:39,250 Let's say you have found this free and at least two of them are greater or equal than key. 233 00:15:39,730 --> 00:15:40,660 Just like I've told you. 234 00:15:41,050 --> 00:15:42,670 Let's take any example that you want. 235 00:15:43,000 --> 00:15:45,360 Let's say I have two of them greater. 236 00:15:45,430 --> 00:15:46,420 And one is less. 237 00:15:46,720 --> 00:15:47,130 All right. 238 00:15:47,500 --> 00:15:49,270 I applied on this free. 239 00:15:50,320 --> 00:15:55,450 Now, this one in the middle is also greater than what I have on the right. 240 00:15:55,480 --> 00:15:58,540 What I have on the left, remember, I have at least one key. 241 00:15:58,930 --> 00:16:03,940 So if I have any less here or less here, I eat them and so on and so forth. 242 00:16:04,270 --> 00:16:10,450 If let's say I have some key, as I've shown before, I'm gonna eat this one and make it a key. 243 00:16:10,720 --> 00:16:15,050 Then I'm gonna extend here and make it a key and stand here and make this a key. 244 00:16:15,280 --> 00:16:16,270 And so on and so forth. 245 00:16:16,300 --> 00:16:17,730 I make everybody a key. 246 00:16:18,340 --> 00:16:21,280 If let's say I had case. 247 00:16:21,340 --> 00:16:21,850 Case. 248 00:16:21,880 --> 00:16:23,560 And then less than case. 249 00:16:23,920 --> 00:16:25,710 What happens is that again. 250 00:16:28,010 --> 00:16:29,170 Not that this is less. 251 00:16:29,260 --> 00:16:30,190 And this is key. 252 00:16:30,610 --> 00:16:32,890 And I have at least two case. 253 00:16:33,100 --> 00:16:34,000 Everybody's fine. 254 00:16:34,510 --> 00:16:37,810 This is why I need at least two elements, greater or equal than key. 255 00:16:38,080 --> 00:16:44,030 Because at some point I'm going to have two consecutive case which will always eat this less sign. 256 00:16:44,530 --> 00:16:44,960 And that's it.