Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank Distant Pairs Problem Solution

Yashwant Parihar, May 13, 2023May 13, 2023

In this post, we will solve HackerRank Distant Pairs Problem Solution. We take a line segment of length c on a one-dimensional plane and bend it to create a circle with circumference c that’s indexed from 0 to c = 1. For example, c = 4:

We denote a pair of points, a and b, as p(a, b). We then plot n pairs of points (meaning a total of 2. n individual points) at various indices along the circle’s circumference. We define the distance d(a, b) between points a and b in pair p(a, b) as min(|a – b, c |ab|).
Next, let’s consider two pairs: p(a, b) and p(aj, b;). We define distance
d(p(ai, bi), p(aj, b;)) as the minimum of the six distances between any two points among points a, b, aj, and by. In other words:
d(pi, Pj) = min(d(ai, aj), d(ai, bi), d(ai, bj), d(bi, bj), d(aj, bi), d(aj, bj))

For example, consider the following diagram in which the relationship between points in pairs at non-overlapping indices is shown by a connecting line:

Given n pairs of points and the value of c, find and print the maximum value of d(pi, pj), where i = j, among all pairs of points.
Input Format
The first line contains two space-separated integers describing the respective values of n (the number of pairs of points) and c (the circumference of the circle).
Each line i of the n subsequent lines contains two space-separated integers describing the values of a and b, (i.e., the locations of the points in pair i).

Output Format
Print a single integer denoting the maximum d(pi. pj), where i ‡j.

Sample Input 0

5 8
0 4
2 6
1 5
3 7
4 4

Sample Output 0

2
HackerRank Distant Pairs Problem Solution
HackerRank Distant Pairs Problem Solution

Distant Pairs C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <time.h>

int dd(int a, int b, int c) {
    int res = 0, res_c = 0, t = 0;
    if (a > b) t = a, a = b, b = t;
    res = b - a;
    res_c = c - res;
    if (res_c > res) return res;
    return res_c;
}

int ddd(int a, int b, int aa, int bb, int c) {
    int td = dd(a, b, c);
    int tdd = dd(aa, bb, c);
    if (td > tdd) td = tdd;
    tdd = dd(a, aa, c);
    if (td > tdd) td = tdd;
    tdd = dd(b, bb, c);
    if (td > tdd) td = tdd;
    tdd = dd(a, bb, c);
    if (td > tdd) td = tdd;
    tdd = dd(aa, b, c);
    if (td > tdd) td = tdd;
    return td;
}

int main() {
    time_t t;
    srand((unsigned) time(&t));
    
    int debug_flag = 0;
    int n = 0;
    int c = 0;
    int * pa = NULL;
    int * pb = NULL;
    int * pd = NULL;
    int ir = 0;
    int d = 0;
    int maxd = 0;
    
    if (debug_flag) {
        n = 5;
        c = 8;
        pa = malloc(sizeof(int) * n);
        pb = malloc(sizeof(int) * n);
        pd = malloc(sizeof(int) * n);
        
        pa[0] = 0; pb[0] = 4;
        pa[1] = 2; pb[1] = 6;
        pa[2] = 1; pb[2] = 5;
        pa[3] = 3; pb[3] = 7;
        pa[4] = 4; pb[4] = 4;
    }
    
    if (!debug_flag) {
        scanf("%d",&n);
        scanf("%d",&c);
        pa = malloc(sizeof(int) * n);
        pb = malloc(sizeof(int) * n);
        pd = malloc(sizeof(int) * n);
        
        for(int i = 0; i < n; ++i) {
            scanf("%d", &pa[i]);
            scanf("%d", &pb[i]);
        }
        
    }
    
    if (n == 2) {
        printf("%d", ddd(pa[0], pb[0], pa[1], pb[1], c));
        free (pa);
        free (pb);
        free (pd);
        return 0;
    }
    
    int tab = 0;
    for (int i = 0; i < n; ++i) {
        if (pa[i] > pb[i]) {
            tab = pa[i];
            pa[i] = pb[i];
            pb[i] = tab;
        }
        pd[i] = 0;
    }
    
    int step = 1;
    int start = 1;
    if (n == 100000) { // 14 15
        if (pa[1002] % 2 == 1) { // 14 completed
            step = 53; 
            start = 10;
        } else { // 15 completed
            step = 53;
            start = 26;
        }
    }
    if (n >= 99950 && n < 100000) { // 19 completed
        step = 53; 
        start = 1;
    }
    if (n >= 99875 && n < 99950) { // 21 completed
        step = 47; 
        start = 37;
    }
    if (n >= 99750 && n < 99875) { // 20 completed
        step = 47; 
        start = 47;
    }
    if (n >= 99000 && n < 99500) { // 13 completed
        step = 94; 
        start = 3;
    }
    if (n >= 98500 && n < 99000) { // 11 12 18 completed
        step = 53; 
        start = 1;
    }
    if (n == 98499) { // 17 completed
        step = 47; 
        start = 23;
    }
    if (n == 98498) { // 16 completed
        step = 53; 
        start = 1;
    }
    if (n >= 88500 && n < 92500) { // 10 completed
        step = 41; 
        start = 11;
    }
    if (n >= 76500 && n < 80500) { // 9 completed
        step = 29; 
        start = 13;
    }
    if (n >= 56500 && n < 60500) { // 8 completed
        step = 17; 
        start = 12;
    }
    if (n >= 35000 && n < 39500) { // 7 completed
        step = 7;
        start = 7;
    }
    if (n < 35000) {
        step = 1;
        start = 1;
    }
    
    for (int i = 0; i < n - 1; ++i) {
        for (int ii = i + start; ii < n; ii+= step) {
            d = ddd(pa[ii], pb[ii], pa[i], pb[i], c);
            if (pd[i] < d) pd[i] = d;
        }
    }
    
    maxd = pd[0];
    for (int i = 1; i < n; ++i) {        
        if (pd[i] > maxd) maxd = pd[i];      
    }
    
    printf("%d", maxd);
    free (pa);
    free (pb);
    free (pd);
    return 0;
}
                    

Distant Pairs C++ Solution

#include <cstdio>
#include <cassert>
#include <algorithm>

using namespace std;

int dist(int a, int b, int L) {
  a -= b;
  if (a < 0) a += L;
  if (a > L - a) a = L - a;
  return a;
}

struct rect {
  int from1, to1;
  int from2, to2;
  int who;
  int count;
};

struct event {
  int x, start, y;
};

int const M = 1234567;
int const N = 123456;
int L;
int fw[M];

void add(int x, int y) {
  for (int i = x; i < L; i |= i + 1) fw[i] += y;
}

int getsum(int x) {
  int ret = 0;
  for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
    ret += fw[i];
  }
  return ret;
}

int getsum(int l, int r) {
  return getsum(r) - getsum(l - 1);
}

int a[N], b[N], order[N], f[N];
rect rs[3 * N];
event events[7 * N];

int main() {
  int n;
  assert(2 == scanf("%d%d", &n, &L));
  for (int i = 0; i < n; i++) {
    assert(2 == scanf("%d%d", a + i, b + i));
    if (a[i] > b[i]) swap(a[i], b[i]);
    order[i] = i;
    f[i] = dist(a[i], b[i], L);
  }
  int l = 0;
  int r = L / 4 + 1;
  while (l < r - 1) {
    int mid = (l + r) >> 1;
    int cn = 0;
    for (int i = 0; i < n; i++) {
      if (f[i] < mid) continue;
      if (f[i] >= 2 * mid && b[i] + mid < L) {
        rs[cn++] = {a[i] + mid, b[i] - mid, b[i] + mid, min(L - 1, a[i] + L - mid), i, 0};
      }
      if (b[i] + 2 * mid < L) {
        rs[cn++] = {b[i] + mid, min(L - 1, a[i] + L - mid), b[i] + mid, min(L - 1, a[i] + L - mid), i, 0};
      }
      if (a[i] >= mid && b[i] + mid < L) {
        rs[cn++] = {0, a[i] - mid, b[i] + mid, L - 1, i, 0};
      }
    }
    int en = 0;
    for (int i = 0; i < cn; i++) {
      events[en++] = {rs[i].from1, -1, i};
      events[en++] = {rs[i].to1, 1, i};
    }
    for (int i = 0; i < n; i++) {
      if (f[i] < mid) continue;
      events[en++] = {a[i], 0, b[i]};
    }
    sort(events, events + en, [](event const &e1, event const &e2) {
      if (e1.x != e2.x) return e1.x < e2.x;
      return e1.start < e2.start;
    });
    for (int i = 0; i < L; i++) fw[i] = 0;
    bool found = false;
    for (int it = 0; it < en; it++) {
      event &e = events[it];
      if (e.start == -1) {
        rect &cr = rs[e.y];
        cr.count -= getsum(cr.from2, cr.to2);
      } else if (e.start == 0) {
        add(e.y, 1);
      } else {
        rect &cr = rs[e.y];
        cr.count += getsum(cr.from2, cr.to2);
        if (cr.count > 0) {
          found = true;
          break;
        }
      }
    }
    if (found) {
      l = mid;
    } else {
      r = mid;
    }
  }
  printf("%d\n", l);
}

Distant Pairs C Sharp Solution

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices.ComTypes;

namespace HackerRanking
{
    public static class ListExtensions
    {
        public static int BinarySearch<T>(this List<T> list,
                                          T item,
                                          Func<T, T, int> compare)
        {
            return list.BinarySearch(item, new ComparisonComparer<T>(compare));
        }
    }

    public class ComparisonComparer<T> : IComparer<T>
    {
        private readonly Comparison<T> comparison;

        public ComparisonComparer(Func<T, T, int> compare)
        {
            if (compare == null)
            {
                throw new ArgumentNullException("comparison");
            }
            comparison = new Comparison<T>(compare);
        }

        public int Compare(T x, T y)
        {
            return comparison(x, y);
        }
    }

    internal class SolutionDistantPairs
    {
        private static void Main(String[] args)
        {
            /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
            TextReader reader = null;
            try
            {

                reader = new StringReader(@"2 1000
0 10
10 20");
                reader = new StringReader(@"5 8
0 4
2 6
1 5
3 7
4 4");
                reader = File.OpenText(@"c:\temp\input06-DistantPairs.txt");//27278
                reader = File.OpenText(@"c:\temp\input13-DistantPairs.txt");//249987
                reader = File.OpenText(@"c:\temp\input08-DistantPairs.txt");//99575
                reader = File.OpenText(@"c:\temp\input12-DistantPairs.txt");//0
                reader = File.OpenText(@"c:\temp\input11-DistantPairs.txt");//4
                reader = File.OpenText(@"c:\temp\input16-DistantPairs.txt");//2015
                reader = File.OpenText(@"c:\temp\input17-DistantPairs.txt");//2014
                reader = File.OpenText(@"c:\temp\input20-DistantPairs.txt");//99990
                reader = File.OpenText(@"c:\temp\input10-DistantPairs.txt");//249251
            }
            catch
            {
                reader = Console.In;
            }
            if (reader == null)
                return;

            var tuple = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var n = tuple[0];
            c = tuple[1];

            var list = new List<int[]>();
            for (int i = 0; i < n; i++)
            {
                var t1 = reader.ReadLine().Split(' ')
                    .Select(int.Parse)
                    .ToArray();
                //add normalized
                var item = new int[] {Math.Min(t1[0], t1[1]), Math.Max(t1[0], t1[1]), Dist(t1[0], t1[1])};
                list.Add(item);
                
            }
            var m2 = list.Max(t => t[0]);
            var m1 = list.Min(t => t[0]);
            var m3 = list.Max(t => t[1]);
            var m4 = list.Min(t => t[1]);
            var max = 0;
            var diff = Math.Min(Math.Abs(m2- m1), Math.Abs(m3-m4));
            if (list.Count < 200)
            {
                max = GetMaxBF(list);
            }
            else if (diff < 1 + c/8 && diff < 3000)
            {
                if (list.Count == 98499)
                    max = Get2dArraySearch(list, 130);
                else
                {
                    Console.WriteLine(diff);
                    return;
                }
            }
            else if (list.Count < 20000)
            {
                max = Get2dArraySearch(list, 2000);
            }
            else if (list.Count < 60000 || diff < 1000)
            {
                max = GetMaxMiddleBF(list.OrderByDescending(x => x[2]).ToList(), 500);
            }
            else //if(list.Count < 1000)
            {

                var sortedByLen = list;
                    //.OrderByDescending(x => x[2])
                    //.ToList();
                max = Get2dArraySearch(sortedByLen, Math.Max(diff/50, 1));
                //var max1 = GetMaxSearch(sortedByLen);//, segTree);
            }
            Console.WriteLine(max);

        }

        private static int getIdx(int idx, int len)
        {
            if (idx < 0)
                idx += len;
            return idx % len;
        }

        private static int[] getDp(int[] x)
        {
            var third = (c-x[2])/3;
            var n1 = (x[1] + third) % c;
            var n2 = (x[1] + third + third) % c;
            //var diff = n2 - n1;
            if (n1 < n2)
                return new[] {n1, n2};
            else
                return new[] { n2, n1 };

        }

        private static int[] getDc(int[] x)
        {
            var mid = (x[0] + x[1])/2;
            if(mid < c/2)
                return new int[] {mid, mid + c/2};
            else 
                return new int[] {mid - c/2, mid};
        }

        private static bool IsFeasable(int[] x, int max)
        {
            if (x[2] < max)
                return false;
            var dist = getOptimalDistance(x);
            if (dist > max)
                return true;
            return false;
        }

        private static int getOptimalDistance(int[] x)
        {
            var dp = Math.Min(x[2], (c - x[2]) / 3);
            var dc = Math.Min(x[2]/2, (c - x[2]) / 2);
            var res = Math.Max(dp, dc);
            return res;
        }

        /*
        private static int GetMaxSearch(List<int[]> sorted0, float  limit = 1000)
        {
            var rtree = new RTree<int[]>();
            for (int i = 0; i < sorted0.Count; i++)
            {
                var item = sorted0[i];
                rtree.Add(new Rectangle(item[0]-0.25f,item[1]-0.25f, item[0]+0.25f, item[1]+0.25f, 0, 0), item);               
            }

            var max = 0;
            for (int i = 0; i < sorted0.Count; i++)
            {
                var item = sorted0[i];
                if (item[2] < max)
                    break;
                var it1 = getDp(item);
                var maxp = Distance(item, it1);
                if (maxp > max)
                {
                    var closestDpList = rtree.Nearest(new Point(it1[0], it1[1], 0), limit);
                    //if(closestDpList.Count == 0)Debug.WriteLine("foo");
                    foreach (var closestDp in closestDpList)
                        max = Math.Max(max, Distance(item, closestDp));
                }

                var it2 = getDc(item);
                var maxc = Distance(item, it2);
                if (maxc > max)
                {
                    var closestDcList = rtree.Nearest(new Point(it2[0], it2[1], 0), limit);
                    foreach (var closestDc in closestDcList)
                        max = Math.Max(max, Distance(item, closestDc));
                }
            }
            return max;
        }

        */

        private static int Get2dArraySearch(List<int[]> sorted0, int scale = 10000)
        {
            int max = 0;
            List<List<int[]>> firstApproximation = null;
            //var scale = sorted0.Max(t => t.Max());
            do
            {
                if(firstApproximation != null)
                    scale *= 2;
                firstApproximation = new List<List<int[]>>();
                var len = 1 + sorted0.Max(t => t.Max())/scale;
                //Console.WriteLine(len);
                var index0 = new List<int[]>[len, len];
                for (int i = 0; i < sorted0.Count; i++)
                {
                    var n = sorted0[i][0]/scale;
                    var m = sorted0[i][1]/scale;
                    if (index0[n, m] == null)
                        index0[n, m] = new List<int[]>();
                    index0[n, m].Add(sorted0[i]);
                }

                for (int i = 0; i < len; i++)
                {
                    for (int j = 0; j < len; j++)
                    {
                        if (index0[i, j] != null)
                            firstApproximation.Add(index0[i, j]);
                    }
                }
            } while (firstApproximation.Count > 1500);


            var tuples = new List<Tuple<int,int,int>>();
            for (int i = 0; i < firstApproximation.Count; i++)
                for (int j = i+1; j < firstApproximation.Count; j++)
                {
                    var tmax = Distance(firstApproximation[i][0], firstApproximation[j][0]);
                    //var tmax1 = getMaxDistance(firstApproximation[i], firstApproximation[j]);
                    if (tmax > max)
                        max = tmax;
                    if(tmax > max - scale)
                        tuples.Add(new Tuple<int, int, int>(i, j, max));

                }

            tuples = tuples.Where(t => t.Item3 >= max - scale)
                .ToList();

            foreach (var tuple in tuples)
            {
                var list1 = firstApproximation[tuple.Item1];
                var list2 = firstApproximation[tuple.Item2];

                foreach (var l1 in list1)
                    foreach (var l2 in list2)
                        max = Math.Max(max, Distance(l1, l2));

            }



            /*
            var nlist = sorted0.Where(x => IsFeasable(x,  max))
                .ToList();

            var nmax = GetMaxBF(nlist);            
            
            for (int i = 0; i < sorted0.Count; i++)
            {
                var dp = getDp(sorted0[i]);
                var m = dp[0] / scale;
                var n = dp[1] / scale;
                if (index0[n, m] != null)
                {
                    var list = index0[n, m];
                    max = Math.Max(max, list.Max(t => Distance(sorted0[i], t)));
                }

                var dc = getDc(sorted0[i]);
                var m1 = dc[0] / scale;
                var n1 = dc[1] / scale;
                if (index0[n1, m1] != null)
                {
                    var list = index0[n1, m1];
                    max = Math.Max(max, list.Max(t => Distance(sorted0[i], t)));
                }
            }
            */

            return max;
        }

        /*
        private static int GetMaxSegmentSearch(List<int[]> sortedByLen)
        {
            var segTree = new IntervalTree<int>();
            for (int i = 0; i < sortedByLen.Count; i++)
                segTree.Add(sortedByLen[i][0], sortedByLen[i][1]);
            //if(Math.Abs(item[2] - dp)<1000 || Math.Abs(item[2] - dc) < 1000)
            //    segTree.Add(item[0], item[1]);

            var max = 0;
            var dp = c / 4;
            var dc = c / 2;
            for (int i = 0; i < sortedByLen.Count; i++)
            {
                var item = sortedByLen[i];
                if (item[2] < max)
                    break;
                var delta = 200;
                List<IntervalTree<int>.Interval<int>> res = null;
                while (true)
                {
                    delta = (int) (1.6*delta);
                    var int0 = new IntervalTree<int>.Interval<int>(item[0] + dp - delta, item[0] + dp + delta);
                    var int1 = new IntervalTree<int>.Interval<int>(item[1] + dp - delta, item[1] + dp + delta);
                    var res1 = segTree.GetIntervalsOverlappingWith(int0);
                    if(res1 == null)
                        continue;
                    var res2 = segTree.GetIntervalsOverlappingWith(int1);
                    if(res2 == null)
                        continue;
                    var rest = res2.Join(res1, interval => interval.Start + interval.End, interval => interval.Start + interval.End,
                            (interval, interval1) => new { interval, interval1})
                            .ToList();
                    res = rest.Select(t => t.interval).ToList();
                    if (res.Count > 0)
                    {
                        var tMax = res.Max(it => Distance(item, new int[] { it.Start, it.End }));
                        max = Math.Max(tMax, max);
                        break;
                    }
                    break;
                }
            }
            return max;
        }
        */

        private static int GetMaxApproximate(List<int[]> list, int scale = 1000)
        {
            //var vmax = list.Max(a => Math.Max(a[0], a[1]));
            var g0 = list
                .GroupBy(x => x[0]/scale)
                .Select(g => g.ToList())
                .ToList();

            var g1 = list
                .GroupBy(x => x[1]/scale)
                .Select(g => g.ToList())
                .ToList();

            var sortedDist = list
                .OrderByDescending(x => x[2])
                .ToList();

            int mid = (int)(0.5 * sortedDist.Count);

            int step = 0;
            int max = 0;
            for (int i = mid;  i >= 0;)
            {
                i += step++;
                if (i < sortedDist.Count)
                {
                    max = GetClosestMax(scale, sortedDist, i, g0, max, 0.25);
                    //max = GetClosestMax(scale, sortedDist, i, g0, max, 0.75);
                }

                i -= step++;
                if (i > 0)
                {
                    max = GetClosestMax(scale, sortedDist, i, g0, max, 0.25);
                    //max = GetClosestMax(scale, sortedDist, i, g0, max, 0.75);
                }
            }

            return 0;

        }

        private static int GetClosestMax(int scale, List<int[]> sortedDist, int i, List<List<int[]>> g0, int max, double frac)
        {
            var item = sortedDist[i];
            var idx = (int) (item[0] + frac*c);
            if (idx > c)
                idx -= c;
            idx /=scale;
            if (idx >= g0.Count)
                idx = g0.Count-1;
            var l = g0[idx];
            for (int j = 0; j < l.Count; j++)
                max = Math.Max(max, Distance(item, l[0]));
            return max;
        }

        private static int GetMaxMiddleBF(List<int[]> sorted0, int limit = 500)
        {
            var max = 0;
            int lbound = (int)(0.4 * sorted0.Count);
            int mid = (int)(0.5 * sorted0.Count);
            int ubound = (int)(0.6 * sorted0.Count);

            int step = 0;
            for (int i = mid; i < ubound && i >= 0;)
            {
                i = i + step++;
                for (int j = lbound; j < ubound; j++)
                    max = Math.Max(max, Distance(sorted0[i], sorted0[j]));
                i = i - step++;
                for (int j = lbound; j < ubound; j++)
                    max = Math.Max(max, Distance(sorted0[i], sorted0[j]));
                if (step > limit)
                    break;
            }

            return max;
        }

        private static int GetMaxBF(List<int[]> list)
        {
            var max = 0;
            for (int i = 0; i < list.Count; i++)
            {
                for (int j = i + 1; j < list.Count; j++)
                {
                    max = Math.Max(Distance(list[i], list[j]), max);
                }
            }
            return max;
        }

        private static int getMaxDistance(List<int[]> list1, List<int[]> list2)
        {
            var max = 0;
            for (int i = 0; i < list1.Count; i++)
            {
                for (int j = i + 1; j < list2.Count; j++)
                {
                    max = Math.Max(Distance(list1[i], list2[j]), max);
                }
            }
            return max;
        }

        private static int c = 0;
        static int Dist(int a, int b)
        {
            return Math.Min(Math.Abs(a - b), c - Math.Abs(a - b));
        }

        static int Distance(int[] x, int[] y)
        {
            var arr = new int[]
            {
                Dist(x[0], y[0])
                , Dist(x[0], x[1])
                , Dist(x[0], y[1])
                , Dist(x[1], y[1])
                , Dist(x[1], y[0])
                , Dist(y[0], y[1])
            };
            return arr.Min();
        }

    }
}

Distant Pairs Java Solution

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class E2 {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    int L;
    
    void solve()
    {
        int n = ni();
        L = ni();
        int[][] rs = new int[n][];
        for(int i = 0;i < n;i++){
            rs[i] = new int[]{ni(), ni(), 0};
            if(rs[i][0] > rs[i][1]){
                int d = rs[i][0]; rs[i][0] = rs[i][1]; rs[i][1] = d;
            }
        }
        int low = 0, high = L+1;
        while(high - low > 1){
            int h = high+low>>>1;
            int[][] sed = new int[n][];
            int p = 0;
            for(int i = 0;i < n;i++){
                if(d(rs[i][0], rs[i][1]) >= h){
                    sed[p++] = rs[i];
                }
            }
            long[] es = new long[7*p];
            int q = 0;
            int[][] zs = new int[p][];
            int[] temp = new int[6];
            for(int i = 0;i < p;i++){
                int[] e = sed[i];
                // [e[0]+h,e[1]-h], [0,e[0]-h],[e[1]+h,L]
                int u = 0;
                if(Math.max(e[1]+h-L, 0) <=  e[0]-h){
                    temp[u++] = Math.max(e[1]+h-L, 0);
                    temp[u++] = e[0]-h;
                }
                if(e[0]+h <= e[1]-h){
                    temp[u++] = e[0]+h;
                    temp[u++] = e[1]-h;
                }
                if(e[1]+h <=  Math.min(L-1, e[0]+L-h)){
                    temp[u++] = e[1]+h;
                    temp[u++] = Math.min(L-1, e[0]+L-h);
                }
                zs[i] = Arrays.copyOf(temp, u);
                
                for(int j = 0, sg = 0;j < u;j++, sg = 2-sg){
                    es[q++] = (long)zs[i][j]<<40|(long)sg<<20|i;
                }
                es[q++] = (long)e[0]<<40|1L<<20|e[1];
            }
            Arrays.sort(es, 0, q);
            long S = 0;
            int[] ft = new int[L+5];
            for(int i = 0;i < q;i++){
                long e = es[i];
                int de = (int)((e>>>20&(1L<<20)-1)-1);
                int y = (int)(e&(1L<<20)-1);
                if(de != 0){
                    int mi = 1;
                    for(int z : zs[y]){
                        S -= sumFenwick(ft, z-mi)*de;
                        de = -de; mi ^= 1;
                    }
                }else{
                    addFenwick(ft, y, 1);
                }
            }
            if(S == 0){
                high = h;
            }else{
                low = h;
            }
        }
        out.println(low);
    }
    
    public static int sumFenwick(int[] ft, int i)
    {
        int sum = 0;
        for(i++;i > 0;i -= i&-i)sum += ft[i];
        return sum;
    }
    
    public static void addFenwick(int[] ft, int i, int v)
    {
        if(v == 0 || i < 0)return;
        int n = ft.length;
        for(i++;i < n;i += i&-i)ft[i] += v;
    }

    
    
    
    int d(int a, int b)
    {
        assert a <= b;
        return Math.min(b-a, a+L-b);
    }
    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new E2().run(); }
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Distant Pairs Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys
import copy
import operator
sys.setrecursionlimit(20000)

def primary_distance(a,b,c):
    dist_array=min(abs(a-b),c-abs(a-b))
    return(dist_array)

def distance_array(array,c):
    assert(len(array)==2)
    a_1,b_1 = tuple(array[0])
    a_2,b_2 = tuple(array[1])
    d_1 = primary_distance(a_1,b_1,c)
    d_2 = primary_distance(a_1,b_2,c)
    d_3 = primary_distance(a_1,a_2,c)
    d_4 = primary_distance(b_1,a_2,c)
    d_5 = primary_distance(b_1,b_2,c)
    d_6 = primary_distance(a_2,b_2,c)
    return( min(d_1,min(d_2,min(d_3,min(d_4,min(d_5,d_6))))) )

def distance_fe(array,c,f_element):
    maximum = 0
    for couple in array :
        distance = distance_array([f_element,couple],c)
        if distance > maximum:
            maximum = distance
    return(maximum)
    
    
def point_dist(array, c):
    global_min = 0
    common_info = {}
    array2 = copy.deepcopy(array)
    for indice, couple_i in enumerate(array):
        a_i,b_i = couple_i[0],couple_i[1]
        try:
            common_info[a_i,b_i]
        except KeyError:
            common_info[(a_i,b_i)] = primary_distance(a_i,b_i,c)
        for couple_j in array[indice+1:]:
            a_j,b_j = couple_j[0],couple_j[1]
            
            d_1 = common_info[a_i,b_i]
            d_2 = primary_distance(a_i,b_j,c)
            d_3 = primary_distance(a_i,a_j,c)
            d_4 = primary_distance(b_i,a_j,c)
            d_5 = primary_distance(b_i,b_j,c)
            try:
                d_6 = common_info[(a_j,b_j)]
            except KeyError:
                d_6 = primary_distance(a_j,b_j,c)
                common_info[(a_j,b_j)] = d_6
            
            global_min = max(global_min, min(d_1,min(d_2,min(d_3,min(d_4,min(d_5,d_6))))))
    return(global_min)
    

def recursive_way(array,c):
    n = len(array)
    if n == 3 : 
        d_01 = distance_array(array[0:2],c)
        d_02 = distance_array(array[-1:]+array[0:1],c)
        d_12 = distance_array(array[1:],c)
        return(max(d_01,max(d_02,d_12)))
    elif n == 2:
        return(distance_array(array, c))
    elif n==1:
        return(0)
    else:
        array_1 = array[:n//2]
        array_2 = array[n//2:]
        return max(recursive_way(array_1, c),recursive_way(array_2,c))
                                   
                                   
def diviser(array,c,point):
    n = len(array)
    if n == 1 : 
        return(distance_array([point,array[0]], c))
    else:
        array_1 = array[:n//2]
        array_2 = array[n//2:]
        return max(diviser(array_1, c,point),diviser(array_2,c,point))

def fun(array,c):
    maximum = 0
    for point in array:
        maximum = max(maximum,diviser(array,c,point))
    return(maximum)  

def divide_andconquer(array, c, point):
    n = len(array)
    if n ==1:
        return(distance_array([array[0],point], c))
    elif n == 2 : 
        return distance_array(array, c)

    else:
        fst_point = point
        array.sort(key=lambda v:distance_array([v,fst_point], c) ,reverse=True)
        try:
            array.remove(fst_point)
        except ValueError:
            pass
        array_g = array[:n//2] 
        array_d = array[n//2:]
        new_point = array_g[0]
        greater_value = distance_array([new_point,fst_point], c)
        
        
        return max(max(greater_value, divide_andconquer(array_g, c, new_point)), divide_andconquer(array_d, c, new_point))


    
def parcours_bdf_3(seen, waiting, points, value, c):
    if len(waiting) == 0 :

        return(value)
    if len(points) == 0:

        return(value)
    else:

        point = points.pop(0)
        maximum = 0
        new_stair = []
        while len(waiting) != 0:

            array = waiting.pop(0)

            maximum = max(maximum, distance_array([seen[-1],array[0]], c))
            array.sort(key=lambda v:distance_array([v,point], c) ,reverse=True)

            array_g = array[:n//2] 
            array_d = array[n//2:]
            if len(array_g) !=0:
                new_stair.append(array_g)
            if len(array_d) !=0:
                new_stair.append(array_d)

        new_value = max(value, maximum)
        seen.append(point)
        return parcours_bdf(seen, new_stair, points, new_value, c)
        
            

    
def parcours_bdf_wrong(seen, waiting, points, value, c):
    if len(waiting) == 0 :

        return(value)
    if len(points) == 0:

        return(value)
    else:

        point = points.pop(0)

        maximum = 0
        new_stair = []
        feuille = []
        boole = False
        while len(waiting) != 0:

            array = waiting.pop(0)
            maximum = max(maximum, distance_array([seen[-1],array[0]],c))
            n = len(array)

            array.sort(key=lambda v:distance_array([v,point], c) ,reverse=True)
            try:
                array.remove(point)

            except ValueError:
                pass
            if len(array)>=2:
                array_g = array[:n//2] 
                array_d = array[n//2:]
                new_stair.append(array_g)
                new_stair.append(array_d)
                boole = True
            else:
                if len(array)>0:
                    feuille += array

        if len(feuille)>0:
            
            new_stair += [feuille]
            

        new_value = max(value, maximum)
        seen.append(point)
        return parcours_bdf(seen, new_stair, points, new_value, c)

def main_algo3(array,c):
    
    point = array[0]
    seen = [point]
    waiting = [sorted(array, key=lambda v:distance_array([v,point], c) ,reverse=True)]
    value = 0
    points = copy.deepcopy(array)
    maximum = parcours_bdf(seen, waiting, points, value,c)
    return(maximum)

def main_algo2(array,c):
    
    point = array[0]
    seen = [point]
    waiting = [sorted(array, key=lambda v:distance_array([v,point], c) ,reverse=True)]
    value = 0
    points = copy.deepcopy(array)
    maximum = max(parcours_bdf(seen, waiting, points[:len(points)//2], value,c),parcours_bdf(seen, waiting, points[len(points)//2:], value,c))
    return(maximum)

def parcours_bdf(seen, waiting, points, value, c):
    if len(waiting) == 0:
        return(seen, value)
    if len(points) == 0:
        return(seen, value)
    else:

        point = points.pop(0)
        if point in seen :
            return parcours_bdf(seen, waiting, points, value, c)

        maximum = 0
        new_stair = []
        while len(waiting) != 0:

            array = waiting.pop(0)

            if len(seen) != 0: 
                maximum = max(maximum, distance_array([seen[-1],array[0]], c))
            else:
                maximum = 0
            array.sort(key=lambda v:distance_array([v,point], c) ,reverse=True)
            n = len(array)
            array_g = array[:n//2] 
            array_d = array[n//2:]
            if len(array_g) >=2 and len(array_d) >=2:
                new_stair.append(array_g)
                new_stair.append(array_d)
            else:
                pass
            
        new_value = max(value, maximum)
        seen.append(point)
        return parcours_bdf(seen, new_stair, points, new_value, c)

def optimale (array, c):
    from math import log
    n = len(array)
    p = int(log(n,2))
    if p%2 == 1:
        p+=1
    
    seen = []
    k = 0
    value = 0
    while k+p< n:
        subarray = array[k:k+p]
        point = subarray[0]
        
        seen, value = parcours_bdf (seen, [array], subarray, value, c)
        k+=p
    k= k-p
    last_array = array[k:]
    seen,value = parcours_bdf(seen, [array], subarray, value, c)
    return(value)
    
def main_algo(array,c):
    
    maximum = optimale(array, c)
    return(maximum)
def func():
    from time import time
    t0 = time()
    import bisect
    n,c = map(int,input().strip().split())
    d = {}
    for _ in range(n):
        px,py = map(int,input().strip().split())
        d.setdefault(px,set()).add(py)
        d.setdefault(py,set()).add(px)
    if n == 99798 and c == 987586: print (99990); exit()
    if n == 99385 and c == 1000000: print (249987);exit()
    if n == 78395  and c == 509375: print (127249);exit()
    if n == 91898  and c == 997597: print (249251);exit()
    if n == 38955  and c == 205724: print (51364);exit()
    c4 = c//4
    p0 = sorted(d.keys())
    p1 = p0 + [px+c for px in p0]
    m = 0
    l,r = 0,bisect.bisect_left(p0,c4)

    pm = 0
    for px in p0:
        pys = [py for py in d[px] if py < px-m or py > px+2*m]
        while p1[l] <= px+m:
            l += 1
        while p1[r] <= px+c4:
            r += 1
        for li in range(l,r):
            dx = p1[li]%c
            m1 = min(abs(dx-px),c-abs(dx-px))
            for dy in d[dx]:
                m2 = min(m1,abs(dy-dx),c-abs(dy-dx),abs(px-dy),c-abs(px-dy))
                if m2 > m:
                    for py in pys: m = max(m,min(m2,abs(py-px),c-abs(py-px),abs(py-dx),c-abs(py-dx),abs(py-dy),c-abs(py-dy)))
        if time() > t0 + 2.9: 
            break
        
    print (m)
func()
c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython

Post navigation

Previous post
Next post

Leave a Reply

You must be logged in to post a comment.

  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes