XENRANK - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vaibhav Tulsyan
Tester: Prateek Gupta
Editorialist: Oleksandr Kulkov

DIFFICULTY:

simple

PREREQUISITES:

None

PROBLEM:

Lattice points are numbered through diagonals (left top to right bottom). Output the numbering of point (u, v).

QUICK EXPLANATION

Output 1+u+\dfrac{(u+v)(u+v+1)}{2}.

EXPLANATION:

The number of points (u, v) such that sum of (u, v) being k is k+1. Let K be sum of the given input (u, v). The points with sum less than K will have lie below the diagonal in which (u, v) lies, i.e. their numbering are less than the numbering of (u, v). The total count of such numbers will be number of pairs with sum 0, with sum 1, till sum K-1, which will be equal to 1 + 2 + .. \dots + K = \dfrac{K \dot (K + 1)}{2} = \dfrac{(u+v)(u+v+1)}{2}.

Now we have to find the add the rank of the point (u, v) in its diagonal itself. You can see that it will be u + 1.

So, overall rank of (u, v) will be

1 + u + \dfrac{(u+v)(u+v+1)}{2}

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be updated soon.
Tester’s solution will be updated soon.
Editorialist’s solution can be found here.

RELATED PROBLEMS:

//