RRANK Editorial

editorial
1

PROBLEM LINK:

Contest

Author: Tejus Kaw
Tester: Rahul Sharma Tejus Kaw
Editorialist: Tejus Kaw

DIFFICULTY:

Easy

PREREQUISITES:

Math , Greedy Algorithm

PROBLEM:

Lattice points are numbered through diagonals (left top to right bottom).Find the rank of the pins given the coordinates (U,V).

QUICK EXPLANATION :

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}​

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long int t;std::cin >> t;
	while(t--){
	    long long int x,y;std::cin >> x>>y;
	    long long int answer = (x+y+1)*(x+y+2);answer/=2;
	    answer -= y;
	    cout<<answer<<"\n";
	}
	return 0;
}