Codeforces Round 1098 (Div. 2) E1 | Upsolving

本站添加: 2026-05-17

[00:00:12]Don't you say you love Hi guys, I'm trying to think of E2. Uh, sorry, E1, not E2.

[00:00:43]I'm trying to debug my even. So what I have done for even is I tried some combinatoral interpretation but nothing was coming even little let me go over a bit of the problem it is just you have to find sum of squares okay sum of squares of all prefix sums you have to find for an array that is f of c and then you're given an array b and some there are some holes you want to construct array c by filling the holes so that the sum will become m And there are various ways to do this.

[00:01:17]Right? You have to sum f of c over all that ways it seems. Okay. To simplify all of that I'm trying to just fix I'm just trying to see sum till here as something square. Okay. If I try to just see some till there as some square.

[00:01:37]So leave that one. If I try to say some till here as some square I can just think of till here we have x holes let's say sum bp after that let's say we have sum x and y holes we have let's say we can write this x holes will take let's say cx as sum and this y holes will take c y as sum you can say sum of this should be the remaining sum right because total is m now you will fix cx and vary you will fix cx and see its contribution Let's say if you fix cx all you want is prefix plus cx whole square right you want prefix sum square. So prefix plus cx whole square can be written as and how many such things will exist?

[00:02:21]How many such things will exist is cx going into x holes which is this because n going into k holes is this and then cy going into y holes which is this. So now what I have thought is if you expand this one see you can say one thing cx going into x and c y going into y summation is nothing but cx + c y going into x + y right if you take all the product summation that's the identity we have let's say the identity we have is this we can remove this one but the identity we have is this sum of cx plus this plus this equals to x cx going into x hole c y going into y hole. So I'm trying to write use this identity to simplify I'm I complicated it likely the solution is much simpler probably but so I want to use that identity to simplify this summation because this summation cx is varying. So if I expand this p square is constant then we know the summation already. The other terms which are cx and cx² these are irritating terms right. So I'm thinking if I can write cx square and cx in terms of cx + x and cx + x + 1 * cx + x. Then maybe we can cancel out some terms, right? Maybe we can cancel out because if you see this one cx plus x, y is cx + x. You can multiply x and divide by x and then you can cancel out and then you can write that as cx + x, x.

[00:04:02]So x is a constant and you can also cancel out* zed as x into x + 1 * cx + x + 1 x + 1.

[00:04:13]So now what happens is you can write px p + cx whole square in terms of this y z and once you write it in terms of y z you can get this constants x and x + 1 into x and then you can make this as x + y + 2 because that's what it's becoming and you can write this as so now we have a closed form but there is something wrong that's happening here I'll once verify this because I might have confused y with some other I might have confused capital Y with capital some other Y. So I'll just try to verify this for once.

[00:04:51]I'm trying to write CX² and CX in terms of Y and Z. That's the goal.

[00:04:57]Okay. Z = CX² + 2 CX * X + X² + CX + X.

[00:05:06]This is likely correct which is nothing but cx² + cx into 2x + 1 + x² + x which is also correct which is nothing but cx 2 + y - x * 2x + 1 because we are trying to write cx in terms of y and zed right + x2 + x which is nothing but we get cx² in terms of z and y which would be z minus of y - x into 2x + 1 - x square - x cx = y - x. So now I want to write p + c x square in terms of x y and constant and y and zed which will be just this which will be z - 5 - x * 2x + 1 I should have simplified here itself.

[00:06:11]2x² + x which is nothing but just x². I hope I'm right.

[00:07:19]Okay, this seems more right.

[00:07:26]P² + X² - 2 P X + Y * 2 P - 2X - 1 + Z.

[00:07:42]If this is right, then C1 will become What was my C1 before?

[00:08:13]So C1 will get simplified to this.

[00:08:22]after that.

[00:08:26]Oh, this is This is absolute I have to update this properly here. So, I have to update this properly here. C1 plus okay so it's capital y * 2p - 2x - 1 so whatever I have done here this is perfect this is capital y * 2p - 2x -1 one and this Jed is perfect. The Jed has gone and it turned into this. Okay, because Jed into we have seen here that Jed into this will get turned into X into X + 1 into CX + X + 1 comma X + 1.

[00:09:36]So now we have to update with respect to this contribution will be c1 * this is correct here 2p - 2x - 1 * x 2 p - 2x - 1 2 - x - 1 * x + this x x + y - 1 x + y x + y + 1.

[00:10:25]I hope modulo takes importance.

[00:10:29]Maybe this will work.

[00:10:37]Now it's not working.

[00:11:24]Hope no one is watching me right now.

[00:11:32]So this is 2 2 + 1 C 1 is three.

[00:11:44]So this is a big minus 8 and this is 2 into 0 - 3 times that What is C1? 0 into 1.

[00:12:39]Guys, the video has been posted. You guys correct the other video.

[00:12:45]It irritates me especially when it writes wrong things.

[00:12:51]This should be right. We can debug this.

[00:12:54]Uh let's try for some more time and then stop. Okay.

[00:13:04]See it's simple. It's I complicated it. There can be simpler solutions but this is what it is that is cx² we have minus of 2x + 1 and then we have 2 p cx which will turn into y - x so p² + cx² will be zus of y into 2x + 1 + x² + 2 p cx will be 2p y - X and then we have P ² + X² - 2 PX as constant and then we have Y into 2 P - 2X - 1 plus Jet.

[00:14:10]So here it is just x into x + 1 not x + 1 c2. Okay. Whoever has written x + 1 c2 I'll just remove it and I'll write x into x x into x + 1.

[00:14:34]Will that work now? Because it was - 9 - 8 6 + 6 - 8. Now it will be 6 into 2 - 8 which is 12 - 8 which is 4. Will this work? Okay, it works for this case. But will it work for all the remaining cases?

[00:14:54]Let's take the next one.

[00:14:58]We should get zero.

[00:15:01]I don't know how this translates to even though it do though.

[00:15:11]Okay, this is zero.

[00:15:14]Let's try one more. Let's try this fourth one.

[00:15:20]If this one is right then we have done it.

[00:15:27]zero.

[00:15:30]I can't debug this further.

[00:15:52]2 3 5 3 5 21.

[00:16:02]It should just be answer of this array, right? It should just be that we have x0 y 0. So what happens if x0 and y 0?

[00:16:17]What happens when x equals to 0?

[00:16:22]Let's just compare here quickly.

[00:16:26]So we have at first moment we have p = to 8 s= to 13. So we have p= to 8. We should just do 8 square here.

[00:16:40]Right?

[00:16:42]So we have 8 square here. X0 X0. So C1 should be 64.

[00:16:48]But why is contribution after C1 zero Let's write it differently. Let's write it in this way.

[00:17:36]Because this has this condition, right?

[00:17:52]I mean they can be altered, right? NCR N plus X + Y CX = to X + Y C Y, right?

[00:18:06]Even now it is the same.

[00:18:17]So this is zero. This is zero. This is zero.

[00:18:27]So zero going into zero things. Why is it why is that not one?

[00:18:36]Why is zero going into zero things not one?

[00:18:54]See assumption is you have x + y holes.

[00:18:56]Okay, this will only hold true if x + y is greater than zero. Let's say let's just put that condition. Okay, let's just put that condition.

[00:19:06]If x + y = 0 means there are no holes at all.

[00:19:14]So now hard coding the solutions, right?

[00:19:21]If P + S S= to M because the assumption here we assume there are K K divisions we have to do and then we assume there are K minus one bars right K minus one partitions so let's hope let's assume K greater than zero okay because if K equals to 0 that that might not hold true and the formula may not hold true.

[00:19:54]X + Y = to0. It's this is hardcoded now.

[00:19:58]Now this will pass but this is not a reliable test case guess. Now that's hardcoded, right? That's why it's passing. But we want to see some other one. We want to see let's say this one ninth one 12180. Maybe we are right. Maybe we are solved. Maybe we are done.

[00:20:31]So so sigma.

[00:20:34]This auto correct is so so sigma.

[00:20:37]I don't want any negatives here. I don't want any any debugging here.

[00:20:48]The it was a problem. It was about I mean maybe there are some other identities but how do how do how to convert it to E2 now? because I got a closed form expression for even but I don't think in any way this is good enough for doing updates right this is definitely not good to do updates this doesn't help I think there is definitely some other solution because the problem score is less So I think there is some other simpler solution which will also translate to E2. What I have done is a complex solution that maybe only works for even which involves varying CX brute forcing prefix. After brute forcing prefix P comma X S comma Y brute forcing number of sum this sum which would be CX and this would be C Y.

[00:21:56]Then prefix square would be P + CX whole square.

[00:22:02]And then I tried using this identity.

[00:22:05]What identity I have tried using? I have tried using this identity which says that you know this much sum going into x + y holes is this. Now we are trying to fix cx and then say into the first x holes this many number of ways and c y going into y holes this many number of ways.

[00:22:24]If you sum that you will get that. So getting this identity is so simple split you know x + y cx plus c yole going into two different souls. I mean you know cx + c y going into x + y whole you just split x comma y and then you say cx going into this c y going into this very that summation will be this. I tried using this identity and then I tried using this identity.

[00:22:48]Okay.

[00:22:50]So trying to use those two identities I tried converting this cx² into cx + x instead of that because if I can made this cx into cx + x + 1 * cx + x I can convert this as zed and then zed into this will become x into x + 1 into divide by x into x + 1 multiply by x into x + 1 then you will get cx + x + 1 comma x + 1 and then you can just try to Use the identity again because you're varying CX. See the beauty of these things sometimes is you can vary CX from 0 to infinity. You can even think of it minus infinity to plus infinity and it still works out. This identities of summations will work out because NCR when x is less than zero NC or when less than zero is zero anyway.

[00:23:49]Now, how to submit this Why don't I have any viewers?

[00:24:04]B was good. I got frustrated too. But B was good. See guys, I think I have solved I think I have solved.

[00:24:14]Sorry for that. I think I have solved uh even which is not that interesting but it had this identities work.

[00:24:25]After those identities I just tried adding them together. It's test sample test one is passing but this doesn't convert to E2. There is no way that this can convert to E2.

[00:24:40]Maybe it does, but hope with updates.

[00:25:06]So you do want to quantum. Okay. So are you ready? Are you ready? Let's go. So imagine you are facetiming your best friend after like 6 months. All right.

[00:25:18]And you did it. All right. You did that Like the thing you you have always dreamed of, you have done it after 6 months.

[00:25:26]>> Yeah. Like how audacious that is or how you know delusional that is. You did it.

[00:25:30]Dream big, you know. dream big and do it. So you did it and now imagine what kind of conversation are you having with you know your best friend in that timeline and you are actually living in that timeline like you have achieved that you have done everything and now you are telling your best friend like >> that's difficult even though she is ready it's difficult to watch further >> guys I'll end the stream then bro why are you hitting it with hammer like what do you mean DFS brute force slightly greedy right okay I'm ending the stream I saw even like like I think I solved even if it's passing the test case so maybe I'll just end the stream then bye guys there is another video check out for other things.

[00:26:33]There is another video that I already uploaded. Check that out for my solutions. I solved both BC, C1, C2 on contest. E1 is right here. Now that's it. Bye.