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

Hinzugefügt: 2026-04-28

[00:00:00]Hey folks, let's upsolve another quick versus contest, but this time uh div one plus div 2 combined round 1094.

[00:00:10]I'm going to solve all problems from A to E. And I'll show you my implementation and notes on problems and we'll see more.

[00:00:25]Let's start from my times in solving problems. I solved the problem A in 3 minutes then B in 16 minutes. A and B were pretty hard for me in comparison with normal rounds.

[00:00:41]Also see it was hard for me. I solved problem C in 30 minutes then D in around 20 minutes to be exact. 21 22 and problem E in 35 minutes. Uh I was almost close I think to solve problem F. I need to attempt that after recording but yeah why not to start from problem A.

[00:01:07]Uh yeah this problem starts with somehow complicated statement and uh image scar right but some people like as you see some people solved it in zero minutes and I think the formula for that was just reading the samples and finding some pattern. The pattern is if 100 is there answer is yes otherwise answer is no. But uh how to prove that? To prove that let's consider you don't have 100.

[00:01:43]How you can make one? I mean how you can make uh k equals 1 and when you have 100 sure you can make um some multiple of 100 this other uh problems and use these 100 to make the last two digits of k and so you can uh find any you can make any k that's why the problem is simply just printing uh if 100 is there that's it. So you read n you read integers and yeah you read you check if 100 is there and that's it that's all about problem A. Great. Let's move on to problem B.

[00:02:38]In this problem, what you should consider first is what is this um reversing the interval? I mean what does this swapping elements I mean u minus i and u + one actually doing?

[00:03:00]Can we swap some index? I mean can I move some number from some part of my array to wherever I want like let's move here can I move one to every position no I can move it to here I mean three can move it to here I can move it to here but I can't move it to here or here or here if you consider carefully you will find out that odd positions are always in odd positions. But you can swap every two odd every two numbers in odd positions.

[00:03:41]Yes. And even positions are there and you can swap them inside themselves. But you can't swap them with odd numbers.

[00:03:49]So leave that for for some time and consider our operation was you can swap every number with every number you want.

[00:03:58]Okay? You can rearrange as you want. If that was the case, what you will do was simply sorting the array. Good.

[00:04:12]And as much as M allows you, you try to um remove um big numbers. Good. So if I was able to swap whatever I want, I just sorted the array and while M is there, I tried to remove the largest element from array A if it was positive. If it was negative, I'll do nothing. But just a note that I always need to remove at least one number. Good. So that's what happens when you have you can just swap even numbers with each other and odd numbers with each other. In that case um what we need to do is just uh yeah dividing the problem into two problems for evens for odds. We solve each of them separately as I said and we combine them together. Let's dive into code and I'll show you how to do that. Okay. So what I do is making two groups, two arrays, one for odd numbers, one for even numbers. And I'll make array P. T 0 means how many X's are even. T1 means how many indexes are odd.

[00:05:42]Then I have my answer and I go over both parities zero and one. Then I sort the the array the numbers I have. And first I need to make sure that if P of parity is not zero uh and I need to remove at least one number from here I need to make sure I do it once because consider you need to remove three numbers from this array and all of them are negative. You can't just say I never remove any number. You can't do that. You should remove the biggest one three times. I mean should mark it three times. Then so this boolean is for that. Then while p of parity is there and uh either I have to remove or uh the largest element is positive. I deduct one from the numbers I need to remove. I pop back and I turn ones to false. And finally I add all the remaining numbers to answer that's it.

[00:06:44]Let's move on to problem C in which I had a difficult time solving it. H I I was doing some I was doing wrong in this problem actually. Okay. So this problem first of all you know if I want to set the median of okay if I have two arrays it's the same median if I merge them the median is still that number so the median that I want to set all subarrays median to it is median of the whole the whole array the entire array Good. So, first of all, I'm going to find the median to see what I want to find. So, the problem is now uh a bit more uh a a bit easier. Good. So, I have some array.

[00:07:42]I want to partition it into maximum number of segments each having uh median.

[00:07:51]Let's name it m. Okay. Let's find the median of the array. Name it m and I'm going to divide it as much as possible to uh yeah I'm going to divide it as to into as much as possible sub arrays each of them should be n great um for doing that what I should do is using dp dpi is the maximum number of subarrays I can divide zero to i. this subarray and that's it for calculating DPI I go over all DP of J's J is less than I I'll check if subarray from J to I median is M and then DPI will be maximum of these J's DP J + one that's it that's it okay the only problem remains is how I'm going to calculate the median of sum solver that's where I made mistake at the beginning and use ordered set in which uh my time complexity was n² log which got time exit but for doing that what you should do is uh simple let's turn every number which is larger than m to + one and every number which is less than m to minus one and change all m to zero.

[00:09:25]In that case, the the median of uh some solar array is its sum uh the median is m if its sum absolute value of its sum is less than the number of zeros in it. Let's see for example if there is two pluses one minus and one zero the median of this is not m but two zeros yes because sum is one and it's less than sorry it's less than two okay uh that is a fact about finding median if you see some number less than m minus one more than m plus one if it's m just zero and median is m if and only if absolute value of sum is less than number of zeros. Let me show you. Let me show you my code. Okay. So for every test case, first I'm going to calculate the median as you see. Then I'll change all the numbers to minus one, + one, and zero. Then I'm going to use DP. First I change all DPS to negative infinity.

[00:10:34]Then I'll have some sum and CNT. Let's start from I. Just a note that DPI is DP for the first I elements which are 0 1 2 3 to I minus one not I itself that's why you see DP I + 1 and you see DP N here for sure DP0 is zero um then I go over indexes from right to left sum plus equals AJ CNT plus equals AJ is zero and if the length is odd and also absolute value of sum is less than cnt. DPI + 1 is maximum of DPI + 1 and DPJ + 1.

[00:11:16]That's it about problem C. Let's move on. Let's move on to problem D.

[00:11:23]Ah this problem great.

[00:11:30]Um in this problem uh you should first convert this sigma this sum to something else.

[00:11:43]Okay consider I have some inversion in my permutation. Here is I here is J and this is array A. Good. Okay. So what the problem asks me is summing up this range right so why not to use partial sum and this is actually partial sum of J minus partial sum of I so let's now the problem is converted to you are given array partial sum PS and for every inversion you will gain PSJ minus PSI and you want to maximize the speed. Great.

[00:12:30]Uh, where should I put one?

[00:12:36]Um, I want put I want to if I put one somewhere.

[00:12:50]uh look if I put one somewhere I'm going to gain partial sum of this index let's say I for all numbers to its right right so partial sum of I times I this is my gain right so where should I put it this is a very good game H I'll put one at the maximum index of partial sum h to gain as much as possible yeah the pattern follows I'll put two at the second maximum three third maximum fourth maximum and so so on let's solve uh some example like for this one two three.

[00:13:49]Okay.

[00:13:51]1 - 1 2 3 2 1.

[00:13:55]So let's write the partial sum array.

[00:13:57]You start from zero because you shouldn't include one in that then one then zero.

[00:14:04]Uh this is my test case or no this this is better. Sorry. So 01 then sorry 1 then -2 then zero. The last one is not important but it's neative one. This is not important because I'm not going to put any number here. So I'll put one at the greatest here then two then three then four then five.

[00:14:37]You see ah three and two they are not important because both are zero. I think the problems that are trick to us by swapping two and three um and yeah so that's it. This is the solution in that in this solution larger partial sums will get smaller numbers which results in more coefficient in uh in partial sum when you are multiplying them. So let me show my code.

[00:15:11]Great. Okay. So what I'm going to do is first making partial sum then finding indes. I mean sorting the array a somehow but sorting indes and then setting the answers and then printing the answer. That's it. That's it. Okay.

[00:15:31]Let's move on to problem E.

[00:15:34]In this problem, uh if K was given, uh this was some easy task, right? K was given how consider let's start from K equals 3. Consider we know that K is three.

[00:15:58]Um I'm going to insert some zero and then it will insert C itself and then easily using binary search I can find C. That's it. If K is two again I'm going to insert zero and it's going to insert C and that's it. If K is one, I'm going to I'm going to insert one one one I mean to the power of N minus one and it's it going to insert C and again binary search. That's it. But yeah, the problem is not that easy.

[00:16:34]So what I'm going to do is first guessing K if it's one or it's two or three like two and three we have a similar solution and for one it's different. So how can I disting distinguish between uh k1 and 2 three?

[00:16:53]I start with a to be zero.

[00:16:59]Then I will insert zero.

[00:17:11]When I insert zero, if K is one, size of array will remain one. But if K is two or three, size of it will be two because C will be inserted. Note that C can't be zero ever.

[00:17:27]Okay, good.

[00:17:30]So I start with inserting some zero. A is zero and I'll also insert some zero.

[00:17:36]This inserting zero, I'll detect if K is one or it's two or three. If k is one then I'll insert 2 to the power of n minus one. Now zero is inside the set and also c is inside the set regardless of what is k. Then I insert my binary search to find c. When I found c if k is one that's it otherwise I need to distinguish between two and three.

[00:18:07]What I'm going to do is again having two cases either C uh let me show you the code. I think now we are ready to see the code as I said I'll start this uh one uh inserting some zero then if there is just one number k is one I'll insert to the power of one to the^ of n minus one otherwise let's k to two but it may it may be three we'll detect it then I'll binary search find finding c uh this is binary search on bits right not different. So then I'll check if case two there are two cases. If C is 2 to the^ of N minus one, I'll add one.

[00:18:57]U if the size of set becomes three, K is three. Otherwise, it's two. Otherwise, I'll insert 2 to the^ of n minus one.

[00:19:08]Then I'll check if some to the power of n minus one is there. If it was there, this is not this is uh if it's not there, this is not X or sorry if it it's not if it's not there, this is X or and that's it. I'll find K and also C. Let's solve problem F.

[00:19:28]Uh for solving problem first we need to define um G I in which this is a graph including all edge but edge with bait I good.

[00:19:48]Um so the answer let let me let me come with some of somehow n squ u time complexity first let's build g0 for sure uh vertices who are connected in g0 the cost between them is zero that's it but here there are some components Right in G0 in which there are some important vertices in them. I mean there are some components without any important vertices. They are not important. But consider there are for example five five components who are which are important.

[00:20:32]Then I need to connect them and I need four eds at least. So what I'll do is adding four to the answer.

[00:20:40]Then I'll move on to G1. In G1 I uh pay attention in G1 I'll keep the vertices who were connected together in the important vertices who were connected in G0 as is but then I'll disconnect uh ed with weight one and connect with uh weight zero and what happens is uh I will these components will get merged together. So I mean some of the important vertices that were not connected together they'll connect together after we consider G1. Okay. So some new eds are made here. Now the number of components is three. So what I'm going to do is adding two to the answer. I mean for sure for connecting n different components I need n minus one x. Good.

[00:21:37]So that is what I need to do. But this is n square. For solving this problem, you need to know dynamic connectivity.

[00:21:45]So if you don't know dynamic connectivity, first go learn dynamic connectivity.

[00:21:49]And if you know dynamic connectivity, then you maybe you are maybe able to solve this problem. Actually when I saw this problem like after 10 minutes 15 minutes, I uh got the idea about uh doing dynamic connectivity.

[00:22:08]uh the rest of the problem was a bit complicated. I couldn't uh finish uh solving the problem. So that's what we do. We keep a DSU for dynamic connectivity and we keep another DSU for important vertices. We do our stuff here and when two vertices are getting merged here, I check if they contain some important vertices. If they are, I'll merge them here too. And I will make G0, G1, G2, G3 up to GM and also GM + one.

[00:22:40]And I'll simply I'll simply uh merge vertices and count the number of components and find the answer. You can check out my code I think. Uh so this is the DSU for important vertices and it contains num comps in which um kept I mean updated here. Then I I have my DSU2 uh in my DSU. So this is the DSU undo operation and what I keep here in addition to normal DSU is candidate.

[00:23:17]candidate is one of the vertices in my component in which it's um an important vertx and first when I read the input I set candidates okay uh let me insert this start here so I have some size for my dynamic connectivity I mean the whatever the size of uh time I want to check or I want to monitor. Then I'll insert every vertices every vertices weight w into zero to w and w + one to set size. Note that w is uh excluded here. Then for every query I'll go and set the candidate and um first I find the number of uh components like this and I'll go do dynamic connectivity and in my dynamic connectivity at the end it the number of components should be one if it's not there is a problem and finally yeah finally I'll print the answer so let's dive into dynamic connectivity function So I record and I undo like this and u I uh do I I go over all views in this node.

[00:24:44]If this is a leave I will add number of components minus one to my answer.

[00:24:49]Otherwise I'll go to the left and go to the right as expected. This is my insert function in which this is uh a bit different from so this style is Chinese style of segment instead of normal segmentry in which we come from top and insert things. This isn't recursive insert function isn't recursive. It just uh it just needs some uh yeah it just needs some for loop and calculations. You can search in Google easy and efficient segmentries code forces and there is a blog on code forces in which describes this type of segmentry.

[00:25:30]Then in function merge of my main DSU.

[00:25:33]If candidates are there, I merge candidates in the main in the important DSU. I mean DSU for important vertices also I keep the history. I merge them.

[00:25:45]If V doesn't have any candidate, I use candidate of U here.

[00:25:49]Yeah, that's a very good problem for training and I mean practicing uh dynamic connectivity.

[00:25:59]Thank you for watching us. Don't miss to put comment if you have a better solution for any of these problems. Shorter codes, neater codes. Uh they are uh the most welcome.

[00:26:11]Please like and subscribe and just wait for us for the next upsolving session which will happen tomorrow morning. Ah my time. Um the next lead code weekly contest. Thank you all and bye-bye.