Header Ad

HackerEarth Minimum radius problem solution

In this HackerEarth Minimum radius problem solution, You are given two arrays X and Y of N elements denoting N points on the 2D plane. You are given another array A of N elements denoting the values associated with each point.

You have to find the minimum integer value radius r of a circle with the center (0,0) such that the sum of all the values of nodes within the circle or on the circle is greater than or equal to an integer p.

If any such r does not exist, print -1.


HackerEarth Minimum radius problem solution


HackerEarth Minimum radius problem solution.

#include<bits/stdc++.h>
using namespace std;

int minRadius (int N, int p, vector<int> x, vector<int> y, vector<int> val) {
// Write your code here
int s = 0, e = 1e9, ans = -1;
while(s <= e)
{
int mid = (s+e)/2;
int i;
long long sum = 0;
for(i = 0; i < N ; i++)
if(x[i]*1ll*x[i] + y[i]*1ll*y[i] <= mid*1ll*mid)
sum = sum + val[i];
if(sum >= p)
ans = mid, e = mid-1;
else
s = mid+1;
}
return ans;
}

int main() {

ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
assert(1 <= T && T <= 10);
for(int t_i = 0; t_i < T; t_i++)
{
int N;
cin >> N;
assert(1 <= N && N <= 1e5);
int p;
cin >> p;
assert(0 <= p && p <= 1e9);
vector<int> x(N);
for(int i_x = 0; i_x < N; i_x++)
{
cin >> x[i_x];
assert(-1e8 <= x[i_x] && x[i_x] <= 1e8);
}
vector<int> y(N);
for(int i_y = 0; i_y < N; i_y++)
{
cin >> y[i_y];
assert(-1e8 <= y[i_y] && y[i_y] <= 1e8);
}
vector<int> val(N);
for(int i_val = 0; i_val < N; i_val++)
{
cin >> val[i_val];
assert(0 <= val[i_val] && val[i_val] <= 1e4);
}

int out_;
out_ = minRadius(N, p, x, y, val);
cout << out_;
cout << "\n";
}
}

Second solution

import os
import sys
from io import BytesIO, IOBase

_str = str
str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

BUFSIZE = 8192


class FastIO(IOBase):
newlines = 0

def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None

def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()

def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()

def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

tc = int(input())
while tc > 0:
tc -= 1
n, p = map(int, input().split())
points = list(
zip(list(map(int, input().split())), list(map(int, input().split())), list(map(int, input().split()))))


def calc(r):
return sum(val for x, y, val in points if x ** 2 + y ** 2 <= r ** 2)


lo, hi = -1, int(2e8)
while hi - lo > 1:
mid = (lo + hi) // 2
if calc(mid) >= p:
hi = mid
else:
lo = mid
print(hi if hi < 2e8 else -1)


Post a Comment

0 Comments