ENDGAME22 - Editorial

editorial
, ,
1

PROBLEM LINK:

It is an End Game

Author: mr_cchef
Tester: agarwal_keshav
Editorialist: mr_cchef

DIFFICULTY:

EASY-MEDIUM

PROBLEM:

Given a co-ordinate (X, Y) in a 2-D infinite grid, we need to calculate the number of rectangles that could be formed such that the endpoints of diagonal lies on the straight line joining the co-ordinates (0,0) and (X,Y) and the endpoints of diagonals are integer coordinates as well.
You have to perform the above task for Q queries.
A query can be of two types:

  • ‘+’ a b : will add a and b units to X and Y co-ordinates respectively.
  • ‘-’ a b : will subtract a and b units to X and Y co-ordinates respectively.

Prerequisites:

  • Basic knowledge of geometry.
  • Basic understanding of GCD.
  • A little amount of brain to be applied while solving or understanding the editorial :wink:

QUICK EXPLANATION:

The number of integer coordinates that lie on a straight line joining coordinates (0,0) and (X,Y) is given by gcd(X, Y).
Let,
g=gcd(X,Y)
We can calculate the number of good rectangles as gC2.

EXPLANATION:

The main crux of the problem is to understand the properties of good rectangles.
By analyzing the three conditions we can conclude that the good rectangle must have the below-mentioned traits.

  • The diagonal coordinates of a good rectangle must lie on the straight line joining (0,0) and (X, Y).
  • The diagonal coordinates of a good rectangle must be integers.
  • The diagonal coordinates of a good rectangle needs to be positive.

Step 1: Calculate the number of integer coordinates that lie on the straight line (0,0) and (X,Y).
In order to calculate, we define x' and y'.

x' and y' are the minimum value of x coordinate and y coordinate such that it lies on the required straight line and x' and y' both remains an integer value.

Then we can write (x'*gcd(X,Y))/(y'*gcd(X,Y)) = X/Y

This means total number of integer coordinates that lies on the straight line will be gcd(x,y).

Step 2: Calculate the number of rectangles with the such that the end diagonals points lines are integer and lies on the straight line joining (0,0) and (X,Y).
Now, we know the number of integer coodinates are noting but g=gcd(X,Y). Then we can simply choose any two points as an end points of the rectangle and create a rectangle around that diagonal.

This is nothing but the number of ways of picking 2 points out of g points and this value can be given as gC2.

Step 3: For each query, we simply need to update the coordinates accordingly and then repeat the steps 1 and 2.

I hope, I was able to make things clear. If not, feel free to comment down your queries. I would love to solve them!!!

SOLUTIONS:

Setter's Solution 
//LinkedIn:https://www.linkedin.com/in/abhijeettamrakar/

#include <bits/stdc++.h>

using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);

#define ll long long

ll getAns(ll n)

{

   return (n*(n-1))/2;

}

void solve()

{

   ll x,y;

   cin>>x>>y;

   ll q;

   cin>>q;

   assert(x>=1 && x<=1e9);

   assert(y>=1 && y<=1e9);

   assert(q>=1 && q<=1e5);

  

   while(q--)

   {

       char t;

       ll a,b;

       cin>>t>>a>>b;

       assert(t=='-' || t=='+');

       assert(a>=0 && a<=1e4);

       assert(b>=0 && b<=1e4);

       if(t=='+')

       {

           x+=a;

           y+=b;

       }

       else

       {

           x-=a;

           y-=b;

       }

       assert(x>=1 && x<=1e9);

       assert(y>=1 && y<=1e9);

  

       ll gcd=__gcd(x,y);

       ll ans=getAns(gcd);

       cout<<ans<<endl;

   }

}

int main()

{

   fastio

   solve();  

   return 0;

}