1355C - Counting Triangles
Problem:
So here is this 1800 rating question acting like it's not that hard by being a Div2 C. No, fuck you 1355C, we know your truth.
The problem can be found here.
What does it say?
Well you have to make a triangle. You're given four values $A,B,C \text{ and } D$, such that $A \leq B \leq C \leq D$. Now you have two create a triangle, such that the sides of the triangle are of lengths $x,y,z$ such that, $A \leq x \leq B \leq y \leq C \leq z \leq D$.
Initial thoughts
A triangle can be created when $ x + y \geq z $, $y + z \geq x$ and $x+z \geq y$. Since we have to have only those triangles which have a positive are, thus the equal to sign is removed. Thus $$ x+y > z \\ y + z > x \\ x+z > y $$.
But since $z$ is already greater than $x$ and $y$, you only need to consider $ x+y > z$.
Delving deeper
So, since the differences between A,B,C and D can go upto $5 \times 10^5$, forget brute force. If you have something $O(n^2)$, forget it too. We need something better here.
We have three areas (A to B for x, B to C for y and C to D for z) to cover. So, we might lean into pointers or something, I don't know I'm illiterate.
Since, I know the answer now (which I definitely knew after reading the editorial only), I don't have any other option than to delve straight into the solution.
The Solution
We take two pointers, $xp$ for $x$ and $zp$ for $z$. Now we can calculate minimum $y$, that satisfies our condition by $yp = zp-xp+1$ (remember that we had removed the equals sign).
We can check whether this $yp$ value is sane or not, by checking if it's between B and C only, but more on this later.
Now we know that a triangle can be formed by $xp$, $yp$ and $zp$. Notice that if we increase $yp$, the condition would still hold. That is, $$xp+yp > zp \\ xp+yp+1>zp$$.
Glad to know that. So, that means if we keep $xp$ and $zp$ constant, all eligible y's, from $yp$ all the way to $C$ are eligible triangles.
We can get their number as $C-yp+1$
Noice.
Now, what if we increased $xp$ by one?
So if $$xp+yp>zp \\ xp+1+(-1)+yp>zp \\ xp + 1 + yp -1 > zp $$
What does it mean? It means that if we increase $xp$, then we can still satisfy the same condition by decreasing the value of $yp$. So, notice that in this case, our eligible triangles would increase by one from the previous case.
To be precise, it would be $C-yp+2$.
Do we see a pattern here?
Yes. As we increase $xp$, we can decrease $yp$ and increase the number of eligible triangles.
But there should be some limit right. Yes. So you can only decrease $yp$ until $B$. Anything less is not acceptable.
So we increase the value of eligible triangles till then, which would be $C-B+1$, in the end.
But what if we still have some x's left? That is, we traversed by increasing $xp$ and decreasing $yp$. Our value of $yp$ could not be reduced anymore because it had reached it's limit $B$, but $xp$ still had not reached it's upper limit $B$. So since the current value of $xp$ satisfies the condition $xp+yp>z$, we know that if we increase $xp$, then the constraint would still be satisfied.
Notice, that in that case, the total number of eligible triangles would be limited to $C-B+1$ for each such "extra" $xp$.
Now you're getting a hang at it don't you.
Now coming back at the sanity of $yp$ initially. you should know that if intially $yp$ is greater than $C$, then no valid $y$ value satisfies that. So in that case, your $x$ was not good enough to create something greater than $z$, so you increase $xp$.
If in some case $yp$ is less than B, then voila! For all the remaining x's, you can take whole range of $y$. That is $C-B+1$.
I think this should be enough to make the core concept of the problem clear.
Anyhow, if you don't get something or something is wrong here, please leave a comment.
Here is my submission.
No comments:
Post a Comment