Codeforces Round 1100 (Div. 1 + Div. 2) | Solutions by Arpa

追加: 2026-05-24

[00:00:01]Hey folks.

[00:00:02]I'm going to up solve Codeforces round 1100 today for you.

[00:00:09]Up solving all problems from A to E. I was unable to solve problem F actually.

[00:00:17]Um I think I was very close. My time complexity was not good enough.

[00:00:24]Let's see uh how I performed in this contest. I solved problem A 2 minutes, B in 5 minutes, C1 in 3 minutes, C2 in 20 minutes.

[00:00:37]Just so you know that those are wrong answer on test one, which are yeah, not important at all.

[00:00:48]Then I solved C2 uh in 20 minutes. Those are wrong answer on test one, by the way.

[00:00:57]Then I solved uh problem D in almost 30 minutes, problem E in uh 50 minutes.

[00:01:09]And I was unable to solve problem F in 1 hour and 10 minutes, unfortunately. I tried.

[00:01:16]I think I was close, but yeah.

[00:01:20]Finally not able to do that. Great. Uh let's go over the problems one by one.

[00:01:27]Let's just start from problem A. Problem A says that uh at each operation you can get numbers closer to X by one.

[00:01:38]And what is the minimum number of uh operations?

[00:01:41]The clear thing here is the difference between minimum and maximum uh differs change by two every time unless it's the last operation, which maybe changed by one.

[00:01:59]Uh so, we find the difference and we divide it by two and take seal to make sure uh we are handling that case correctly.

[00:02:10]So, max element minus min element plus one divided by two and you can see on examples like 5 minus 1 4 divided by 2 it's 2.

[00:02:20]Or let's say here 7 minus 1 it's 6 divided by 2 it's 3.

[00:02:28]Or here 5 minus 2 it's 3 3 divided by 2 but taking seal uh it's 2 so on. Great. Let's move on.

[00:02:40]Let's move to the problem B.

[00:02:43]Uh in problem B uh what we should do is uh first we're starting with trying to maximize B for sure because um B is more important. B we are doing sum over it.

[00:03:00]So, first let's try to make B as large as possible. So, if AI is larger than BI, let's swap them to make BI greater. Okay.

[00:03:13]Then we may swap one A with a B with its corresponding B to make the answer even larger. Okay?

[00:03:28]Uh in that case the answer will be the previous sum minus BI then plus BI then plus AI. How?

[00:03:46]Uh let me wait for this to load and I'll show you.

[00:03:53]Uh still waiting for this to load.

[00:04:07]Okay.

[00:04:08]Mhm still waiting. Okay, finally.

[00:04:13]Okay, so So this is my array A.

[00:04:18]This is array B.

[00:04:20]Then when I swap these two, the answer will be sum of B sum of B minus uh minus BI to remove this from here.

[00:04:43]Then plus AI because this AI will be added to this sum.

[00:04:49]And finally, plus BI because this new BI we are considering that it will be the maximum.

[00:04:58]Okay? It may be not, but um this is not a problem for us.

[00:05:04]This will not exceed the answer. This is one of the candidates for the answer.

[00:05:09]Okay?

[00:05:10]So we calculate the maximum over all this and that is the answer. So look at this. I get all A's then I all B's and if B is a large B is less BI is less than AI, I swap AI and BI. Then you can see a fact here. So this BI will um go outside this that BI and this is sum plus AI. So what is a best thing here?

[00:05:43]To have the maximum AI. So the answer is sum of B plus the maximum of A and that's it. So, you can see maximum of A plus sum of B.

[00:05:54]That's it.

[00:05:56]Okay, then let's go into the next problem which is C1.

[00:06:01]In this problem, what we need to do is just making all numbers negative and it's always possible. We come from right to left. We see each positive element, we flip it. Uh we then we continue to the left and every time we see a positive element, we flip it. Okay?

[00:06:21]The only thing that uh we need to take care about is um when we are going to left, we already had flipped this prefix many times. So, we need just to keep the parity of how many times I already uh inverted numbers.

[00:06:47]Uh and using that, I can calculate >> [clears throat] >> what should I do.

[00:06:55]Okay.

[00:06:57]Let's see. So, first of all, I start with reading um array A.

[00:07:06]Then first inverse the I didn't invert anything to to my right.

[00:07:11]Then I have my answer.

[00:07:14]Then there are two conditions. A I is more than zero and it's or by inverted.

[00:07:22]Why? Because for example, if I inverted uh in the right and this number is negative, it means that this number is now positive. So, I need to invert it again.

[00:07:36]Uh given that, I need to push this as I need to have this uh I in my answers. Then I will flip the inversion and go to the left, finally print the answer. This is a bit tricky to understand. Make sure you understand this before we continue to problem C2 because it's needed in C2.

[00:08:00]Okay.

[00:08:02]In problem C2, uh it was not very easy for me.

[00:08:06]Um I don't know what what I I I implemented a DP solution from scratch and it was wrong and then I started all over again. It was pain. Uh okay. Uh but but the solution is not that hard. We can handle it.

[00:08:22]Uh let's start like this.

[00:08:25]We for sure we are for sure going to do some operations. If you are not doing some operations, that's it, okay?

[00:08:34]But consider that we are doing some operations.

[00:08:39]And we have Let's let's fix the rightmost element that I do operation on that. I do an operation on that, okay?

[00:08:54]So, let's consider the leftmost element that I do operation that. For example, here uh the leftmost the leftmost is two, okay? I'm going to do operations on one and two and the left Sorry, the rightmost is uh two. Or for example, here the rightmost is seven. Where is that? 1 2 3 4 5 6 7. This is a the rightmost I'm going to do some operation over that, okay?

[00:09:25]So, let's consider that element.

[00:09:30]When I went to do that flip.

[00:09:39]I can make sure that before I do that, like here, so if if you read this example carefully, you could solve the problem. Like this is a revealing the solution.

[00:09:52]So, before I do this operation, I make sure that all numbers from its left are negative.

[00:10:02]Then, I'll invert all these numbers and those numbers will be positive and only this number will be negative.

[00:10:11]Okay?

[00:10:13]And uh yeah, this is this is pretty tricky, okay? So, how I can make all these numbers negative? Using C1, okay? And then I will invert this, too. So, just just we need a little bit of calculations.

[00:10:34]Sorry.

[00:10:35]Okay, I just start with reading the input. Then, I'll have some sum and some absolute which I'll calculate when I'm going from left to right.

[00:10:47]And I will have some answer. And I will have IND which shows that which index I want to pick.

[00:10:54]Then, [snorts] uh I iterate over I from left to right.

[00:11:03]And finally, I decrease the number from my sum and [snorts] I go over go over. So, if I this number is positive, so I can do operation on that. And this answer, which is sum abs, which comes from my left, minus AI, which is making this number negative, plus sum, which are sum of numbers to the right, This is bigger than ans, so I need to update the answer.

[00:11:36]So, I set the answer. I set the index.

[00:11:40]And I update the sum apps.

[00:11:43]Which is to the left. Finally, I define my vector. If index is not negative one, I start by Yeah, I do C1 actually and print the answer. That's it.

[00:11:56]Let's move on. Let's move on to the problem D.

[00:12:01]Yeah.

[00:12:02]>> [snorts] >> I I think there exists a an easier solution to this problem, but yeah. So, I do binary search over the answer.

[00:12:13]And now the array A and B are zeros and ones, right?

[00:12:22]>> [snorts] >> Uh let me show you how they are zeros and ones, okay?

[00:12:28]For example, let me come with some uh Let me come with this.

[00:12:43]>> [snorts] >> Okay.

[00:12:50]Okay.

[00:12:51]Um consider the ans answer is eight, right?

[00:12:57]So, this is zero zero one zero one one.

[00:13:02]So, I put one when this is greater than eight, and I put zero when the number is less than eight, okay? Zero zero zero zero one one, okay?

[00:13:17]Uh >> [sighs and yawns] >> So, I can do some operations, right?

[00:13:23]>> [snorts] >> And I pick something the then I then this will be sorted and the smaller one goes to upper um greater one goes to lower. So, if I remove this, the new will be zero and one, okay?

[00:13:45]So, first of all, what I can do is removing these numbers.

[00:13:52]Like I can easily drop this because I can like pick them together and delete those two zeros.

[00:14:03]>> [snorts] >> Then also, I can remove this.

[00:14:08]Right?

[00:14:10]I pick these together and remove that.

[00:14:15]Then, I can remove this.

[00:14:19]And now, I can pick these two together and have zero one. And now I have this.

[00:14:31]Finally, I can convert this to one one.

[00:14:33]So, this is the answer.

[00:14:36]Okay. So, what I mean?

[00:14:38]What I mean is first of all, if at any moment of removing these columns or whatever you are calling it, at every moment, if number of ones is more than number of zeros, that's it. The answer is true.

[00:15:05]>> [snorts] >> Otherwise, let's try to remove some zeros as much as possible.

[00:15:11]Okay. So, consider some sub array.

[00:15:15]Sorry.

[00:15:16]Consider some sub array that you can find a lot of zeros in it like this.

[00:15:28]I [snorts] can remove all of them and replace them with two zeros.

[00:15:34]So, what I will do is exactly doing this.

[00:15:38]Trying to remove uh large segments that have a lot of zeros and converting them to to something like this.

[00:15:50]>> [snorts] >> And finally, uh trying to see if the number of ones is more than number of zeros.

[00:16:00]So, what I understand from my solution, so I implemented this and got AC, but now I'm trying to improve my solution.

[00:16:10]I think that we have some uh We have some columns with two ones.

[00:16:32]And other columns.

[00:16:36]Let's convert.

[00:16:42]No.

[00:16:42]>> [snorts] >> Okay. So, I'll I'm going to describe the solution I implemented. Let's see.

[00:16:48]So, first of all, I read see the input, then I do my binary search. Then I have my CNT.

[00:16:54]And I have some something named escape.

[00:16:58]That means that we are trying to escape the current salary or not, okay?

[00:17:04]So, if escape is true, uh and both numbers or at least one of them is less than mid, I'll keep this keeping I'll keep this and just continue from this index.

[00:17:19]Otherwise, I'll add those two numbers.

[00:17:24]And then the skip will be if both numbers are less than meet. So, both are zero.

[00:17:32]And finally, I'll check if number of ones is more than number of zeros. I I'm pretty sure you can find easier solution.

[00:17:42]There is something to make it easier.

[00:17:44]I'm not sure I I'm sure, but I don't know how to implement that.

[00:17:49]How to find that, but there is something. There is something to uh Yeah. Make it easier to understand, easier to implement a a bit. Yeah.

[00:18:03]And the the conditions can be simplified, I mean. Okay, great. Let's dive into the last problem, problem E.

[00:18:10]Oh.

[00:18:12]Oh, this was not easy.

[00:18:14]This was not easy for me.

[00:18:17]Uh Oh, and the problem F was unsolvable, right? Okay.

[00:18:23]>> [snorts] >> Uh problem E.

[00:18:29]The first thing to observe in this problem is every time we are picking a leaf, we are picking a larger leaf.

[00:18:41]Okay.

[00:18:43]So, when one by one, one by one, when we are uh going, when we are finding the next leaf, we are picking a better one. We are picking a larger one, okay?

[00:18:59]So, let's define a DP.

[00:19:02]And yeah, another note.

[00:19:05]The node N will be the last node that it remain, okay?

[00:19:12]So, let's root the tree from node A.

[00:19:16]Then, uh then let's say DP of V to be the number of ways the number of different sets I can have when for the first time I insert V to the set.

[00:19:45]Okay? So, the number of different ways of set S when V is being inserted to S itself.

[00:19:55]This is This is the definition for uh This is the definition for S.

[00:20:07]This is the definition for DP.

[00:20:11]So, let's try to calculate DP, okay?

[00:20:18]So, to calculate DPV, you can see So, this is root of my tree.

[00:20:27]These are vertices. This is V. This has a subtree.

[00:20:32]So, consider the last element before V in S. So, S is something like this, then U, and then V. I want to iterate over U.

[00:20:46]Okay?

[00:20:47]U is for sure less than V.

[00:20:51]For sure, there should be no vertex here larger than U.

[00:21:00]>> [snorts] >> It means that let's calculate MX of V to be maximum index of a vertex in subtree of V is strict sub subtree not V not including V itself.

[00:21:18]So, U should be strictly more than max of V.

[00:21:27]It means that U can So, so, so, DP V is sum of >> [snorts] >> max mxv plus one to DPV DPU.

[00:21:54]Okay.

[00:21:57]This is the sum.

[00:21:58]This is DPV.

[00:22:02]This way you can calculate DP but this is of n squared.

[00:22:09]We can fix that using partial sum over DP. We can fix that.

[00:22:18]But there is a still a problem here.

[00:22:22]Problem is this doesn't work for root itself.

[00:22:27]For root we need to do something else.

[00:22:31]So, root has some root has some subtree that the second maximum is here.

[00:22:45]The only DPs that can contribute to root's DP are here. Who are they?

[00:22:54]Consider the maximum here.

[00:22:59]The maximum vertex here.

[00:23:03]Let's name it X or let's name it T.

[00:23:07]All vertices here that are larger than T can contribute to the answer.

[00:23:14]The answer is sum of DPs in this subtree that are larger than T.

[00:23:26]Yeah.

[00:23:27]Let me show you the code.

[00:23:30]So, I started with implementing my mint struct.

[00:23:35]Then >> [sighs] >> and then I receive the input. I do DFS to find the MX for every vertex.

[00:23:47]Now, I'll have my max leaf.

[00:23:49]The max leaf will be the leaf which is maximum. The The first leaf that we asserted is that.

[00:23:59]Then I have my partial sum, then DP total, which is total DP so far.

[00:24:05]Sum of all DPs so far. DP sum, maximum leaf, and DP of maximum leaf. This is one. Others are zero.

[00:24:14]Then I start from max leaf plus one and I go to N minus two.

[00:24:21]If MX of V is larger than V, yeah, for sure DP of V is zero. Otherwise DP will be DP DP total minus DP sum of max V.

[00:24:36]Uh great.

[00:24:41]So, this this is this is probably using partial sum.

[00:24:45]Then I update DP sum and also DP total.

[00:24:49]Then I change the definition for maximum to include the numbers themselves.

[00:24:56]Then I sort all adjacents of a vertex n - 1 and move uh the I I need the first two, right? So, I sort them.

[00:25:10]Uh then then mhm if maximum leaf is n - 1, that's it.

[00:25:20]Otherwise, I go calculate answer. I go in this child.

[00:25:25]This is my parent.

[00:25:27]And this is how Oh, this is not needed.

[00:25:35]This is not needed.

[00:25:37]Because size will be If size is one, it's leaf already.

[00:25:42]That's it. Okay. So uh the answer will So So, I want to find the vertices in subtree of these children which are which their index is better is larger than this.

[00:26:03]The second minimum.

[00:26:05]Then I go into calculate answer is v if v is more than t, dpv can contribute to the answer, otherwise zero.

[00:26:14]Then I go over all vertices and calculate recursively. Thank you.

[00:26:25]Thank you for watching, guys.

[00:26:27]Um we have a few hours before this contest, so I hope for you good ratings.

[00:26:36]Uh see you tomorrow morning in Lead Code up-solving session. Thank you. Uh Bye-bye.