DISTCON - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Srikkanth R
Tester: Harris Leung
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy

PREREQUISITES:

Observation

PROBLEM:

The manhattan distance between two points P_1(x_1, y_1) and P_2(x_2, y_2) is given by d(P_1, P_2) = |x_2 - x_1| + |y_2 - y_1|.

In other words, manhattan distance is the minimum number of moves required to reach P_2 from P_1 if, in each move, you are allowed to travel one unit along the X-axis or one unit along the Y-axis.

You are given an integer D. Find four points (P_1, P_2, P_3, P_4) with integer coordinates, such that:

  • The absolute value of both X and Y coordinates of all points is at most 10^9.
  • The manhattan distance between any pair of points is D .

EXPLANATION:

There are two cases:

  • When D is odd.

In this case, there doesn’t exist any solution which satisfies all the given conditions.

  • When D is even.

Suppose we say there are two points P(x_1, y_1) and P_2(x_2,y_2) whose manhattan distance is D.

Now what can be the third point P_3(x_3,y_3) such that the distance of this point from both the points P_1 and P_2 is D. One way of doing so is intercahnge the x and y coordinates to form a new point. Let’s say P_3(x_3,y_3) = P_2(y_2,x_2).

Now in order to satisfy the conditions of the given problem the distance between |x_1-x_2| needs to be the same as that of |y_1-y_2|. Then only when we interchange x and y coordinates of P_2 to form a point P_3.

Hence the distance D = |x_1-x_2| + |y_1-y_2| needed to be even.

Hence the distance between point P_1 and P_3 is again D. What about the distance between P_2 and P_3. How can we make sure that this distance is also D?

Let’s look, the distance between P_3 and P_2 is just the twice the distance between there x and y coordinates i.e

2*|x_2-y_2|

Hence we can say that |x_2 - y_2| = D/2. In this way, we can ensure that distance between P_3 and P_2 is also D.

What about point P_4. Just do the same interchange the x and y coordinates of point P_1. Hence in this way, we can get our four points, where the distance between any pair is D.

In simple terms the points can be written as:

(x, x+d/2) \\ (x+d/2, x+d) \\ (x+d, x+d/2) \\ (x+d/2, x)

TIME COMPLEXITY:

O(1) per case

SOLUTIONS:

Author
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<set>
#include<utility>
#include<algorithm>
#include<queue>
#include<cstdlib>
using namespace std;

// - - - - - - Data Types - - - - - - //

#define SF1(A)              scanf("%d", &A)
#define SF2(A,B)            scanf("%d %d", &A, &B)
#define SF3(A,B,C)          scanf("%d %d %d", &A, &B, &C)

typedef long long int LLI;
typedef unsigned long long int ULL;
#define SL1(A)              scanf("%lld", &A)
#define SL2(A,B)            scanf("%lld %lld", &A, &B)
#define SL3(A,B,C)          scanf("%lld %lld %lld", &A, &B, &C)

#define SD1(A)              scanf("%lf", &A)
#define SD2(A,B)            scanf("%lf %lf", &A, &B)
#define SD3(A,B,C)          scanf("%lf %lf %lf", &A, &B, &C)

// - - - - - - Vectors - - - - - - //
typedef vector<int> VI;
typedef vector<LLI> VLLI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VS> VVS;

#define scanVI(V, N)        for(int I=0; I<N; I++){ int X; SF1(X); V.PB(X); }
#define scanVLLI(V, N)      for(int I=0; I<N; I++){ LLI X; SL1(X); V.PB(X); }
#define scanVS(V, N)        for(int I=0; I<N; I++){ string X; cin >> X; V.PB(X); }
#define scanVD(V, N)        for(int I=0; I<N; I++){ double X; SD1(X); V.PB(X); }

// - - - - - - Maps - - - - - - //
typedef map<int, int> MII;
typedef map<int, string> MIS;
typedef map<int, char> MIC;
typedef map<string, int> MSI;
typedef map<char, int> MCI;
typedef map<int, VI> MIVI;

// - - - - - - Pairs - - - - - - //
typedef pair<int, int> PII;
typedef pair<string, string> PSS;
typedef pair<char, char> PCC;
typedef pair<int, string> PIS;
typedef pair<int, char> PIC;
typedef pair<string, char> PSC;
typedef pair<LLI, LLI> PLL;

// - - - - - - Sets - - - - - - //
typedef set<int> SI;
typedef set<LLI> SLLI;
typedef set<string> SS;
typedef set<char> SC;
// - - - - - - - - - - - - - - - - - - //

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

clock_t Start;
inline void runTime(){
	#ifdef gHost
	fprintf(stderr, "\n>>Runtime: %.10f sec\n", (double) (clock() - Start) / CLOCKS_PER_SEC);
	#endif
}

#define TIMER				runTime();
#define PF                  printf
#define SF                  scanf
#define PB                  push_back
#define SR(N)               right<<setw(N)
#define SL(N)               left<<setw(N)
#define PREC(N)             fixed << setprecision(N)
#define RJUST(N, C)         right<<setw(N)<<setfill(C)
#define LJUST(N, C)         left<<setw(N)<<setfill(C)
#define POP                 pop_back()
#define PP                  prev_permutation
#define NP                  next_permutation
#define MP                  make_pair
#define CLRN(A)          	memset(A, -1, sizeof(A))
#define CLR(A)              memset(A, 0, sizeof(A))
#define BitCount(A)         __builtin_popcount(A)
#define ALL(A)              A.begin(), A.end()
#define ALLN(A, N)          (A, A+N)
#define BSRCN(A, N, X)      binary_search(ALLN(A, N), X)
#define BSRC(A, Z)          binary_search(ALL(A), Z)
#define UNQ(V)          	sort(ALL(V)),(V).resize(unique(ALL(V))-V.begin())
#define MAX                 100007
#define IMAX                INT_MAX
#define LMAX                2000000000000000000LL
#define MIN                 -10000007
#define PI                  acos(-1)
#define BR                  puts("")
#define FastIO              { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
#define READ()              freopen("input.txt", "r", stdin)
#define WRITE()             freopen("output.txt", "w", stdout)
#define IO                  READ(); WRITE();
#define SEED                srand((rand()-time(NULL)))
#define ran()               (((((1ULL*rand())<<31)|(1ULL*rand()))<<13)^((((1ULL*rand())<<32)|(1ULL*rand()))))
#define rran(A, B)          ((ran() % ((B) - (A) + 1)) + (A))
#define SZE(A)              (int)A.size()
#define CASES(T)            for(int TC=1; TC<=T; TC++)
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
/*----------------------Graph Moves----------------*/
int ROW[]={+1,-1,+0,+0};
int COL[]={+0,+0,+1,-1};

int X[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
int Y[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

int KX[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
int KY[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

VI basePrime={1009, 1013, 1019, 1021, 1031, 1223, 1229, 1231, 1237, 1249, 1289, 1291, 1297, 1301, 1303, 353, 359, 367, 373, 379, 859, 863, 877, 881, 883,
                1931, 1933, 1949, 1951, 1973, 401, 409, 419, 421, 431, 1709,  1721, 1723, 1733, 1741, 3499, 3511, 3517, 3527, 3529, 929, 937, 941, 947, 953};

/*----------------------------------------------------------------------------------------------------------------------------------------------*/

template<class XXX> XXX GCD(XXX a, XXX b) { return b == 0 ? a : GCD(b , a % b); }
template<class XXX> XXX LCM(XXX a, XXX b) { return a * (b/GCD(a, b)); }
template <class T> inline void fastRead(T &r){
    r=0; register int f=1; register char ch=getchar();
    while (ch<'0' or ch>'9'){f=(ch=='-'?-1:1), ch=getchar();}
    while (ch>='0' and ch<='9'){r=r*10+ch-'0', ch=getchar();}
    r*=f;
}
template<class XXX> inline XXX moduler(XXX num, XXX mod) {return (num>=mod?num-=mod:num);}

/// BITMASK
inline int Set(int pos, int N){return N=N | (1<<pos);}
inline int Reset(int pos, int N){return N= N & ~(1<<pos);}
inline bool Check(int pos, int N){return (bool)(N & (1<<pos));}

inline void OPFILE(){
    #ifdef gHost
    	Start=clock();
        freopen("D:\\OneDrive - Daffodil International University\\Programming\\CPP\\input.txt", "r", stdin);
        freopen("D:\\OneDrive - Daffodil International University\\Programming\\CPP\\output.txt", "w", stdout);
    #endif
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - END - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //

int main()
{
    OPFILE();

    int d; cin >> d;
    if(d%2)
    {
        cout << -1 << endl;
        return 0;
    }

    cout << "0 " << d/2 << endl;
    cout << d/2 << " 0" << endl;
    cout << d/2 << ' ' << d << endl;
    cout << d << ' ' << d/2 << endl;


	TIMER;
}

Tester
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=1e5+1;
int n;
ll pf[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	if(n%2==1){
		cout << "-1\n";
	}
	else{
		n/=2;
		cout << 0 << ' ' << n << '\n';
		cout << 0 << ' ' << -n << '\n';
		cout << n << ' ' << 0 << '\n';
		cout << -n << ' ' << 0 << '\n';
	}
	//solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  int d;
  cin>>d;

  if(d%2!=0) {
    cout<<-1<<"\n";
  } else {
    cout<<1<<" "<<1+d/2<<"\n";
    cout<<1+d/2<<" "<<1<<"\n";
    cout<<1+d/2<<" "<<1+d<<"\n";
    cout<<d+1<<" "<<1+d/2<<"\n";
  }
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  t=1;

  while(t--)
    solve();

return 0;
}

1 Like

hey!! we can also get the values as :-
(0,0)
(d,0)
(0,d)
(d/2,d/2)

But codechef is showing wrong answer can you tell me why this is happening as all four are equidistance from each other and it comes under constraints also.

Hello @aryan_bisht, in the question it was asked a minimum number of steps( one unit at a time) to move from one point to another point. However, while we take a pair of (d,0) and
(d/2,d/2) we can see it is two half steps. It could be the reason behind the wrong answer.

The distance between 2nd and 3rd points is 2D not D.

the points (d,0) and (0,d) will have a manhattan distance of 2d, whereas rest of them would have it as d…hence it’s showing wrong answer

1 Like