PROBLEM LINK:
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
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.