1335C - Counting Triangles - How to be a bitch of a problem 101

 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.