NO , i think i unable to clearify it,
it is O(N)
coz i find the max distance by generating the different dimension 2^d ,
i found in a problem from SPOJ named DISTANCE manhattan
I read it multiple times but after he mentions about mask I cannot understand the part after that
1 Like
i used this method. Just search for the delaunay triangulation method code and triangulate your graph. basically your edges will reduce from n*(n-1)//2 to 3*n, and then use any spanning tree algorithm
For my case i used Kruskal and obviously after the contest
also make sure to change the dist method in triangulation from euclidean to manhattan
(I didn;t do it and hence had a bug in my code)
cheers
yeah, but the caveat is that research is going for d>=3 for euclidean type distances. manhattan would be not affected i guess
considering the constraints for subtask 1, n=5000 which kruskals runs via kruskals in ElogV where E=n(n-1)/2 and that makes it nearly (n^2)logn which is fine for n=5000 but considering n=200000 we get way huge number of operations, than permitted by online compiler available, considering online compiler executes 10^8 oper./sec and since 3 second is alloted time, total operations needed = 310^8 but we get nearly ((210^5)^2)log(2*10^5) via kruskals/prims, therefore we have to neglect edges not in use, to reduce number of operations
1 Like
Yes of course, was specifically talking about Euclidean delaunay’s traingulation
But I don’t understand why the link to there uses fenwick tree in the implementation. Can you explain that?
1 Like
Can you share any solution link based on delaunay triangulation approach ?
In order to find the closest and the farthest nodes or points can i use distance from origin as a parameter??
If no why is it wrong?
Let us assume 3 points in a 2-D plane
A(4,7) B(5,7) C(6,6)
Now let us divide your algo in 2 parts
Your algo ( ALGO-1 ) will sort them on the basis of Euclidean Distance .
A(dist from origin = sqrt(65))
C(dist from origin = sqrt(72))
B(dist from origin = sqrt(74))
And now your algo ( ALGO-2 ) will connect the points which are farthest …
So the connections will be like this …
A-B-C edge weights = |4-5| + |7-7| + |5-6| + |7-6| = 3 ( Manhattan Distance )
But actual answer is 5 when the connections are as follows
A-C-B edge weights = |4-6| + |7-6| + |5-6| + |7-6| = 5 ( Manhattan Distance )
ALGO-1 of your solutions is based on Euclidean Distance
&
ALGO-2 of your solutions is based on Manhattan Distance
So, Euclidean Distance & Manhattan Distance are very different from each other. And cannot be used together.
Since this problem is based on Manhattan Distance ALGO-1 can’t be used to Sort the points.
Damm Dude You really inspired me today
1 Like
I didn’t get it too, I just used simple math instead. But i think it was to find the max and min of every set like every time they were making a segment tree or fenwick tree for array and using it to find max and min in log(n) time.
Found this link: Link
In all the above links instead of building an array and sorting it they are just making a fenwick tree, updating the sum in the tree and using it to find minimum.
It will take same time tho i guess: n queries and logn for each query.
Can anyone help me debug my code? 2/3 test cases of subtask-1 pass and 1/3 of subtask-2 pass.
import inspect
Infinity = float('inf')
def integer_array_input():
return MyList(map(int, input().split()))
def integer_input():
return int(input())
def test_case_count():
return range(integer_input())
class This:
def __init__(self):
self.max = self.min = self.sum = self.count = None
self.set = set()
self.map = dict()
self.reset()
def update_if_max(self, *values):
self.max = max(self.max, *values)
def update_if_min(self, *values):
self.min = min(self.min, *values)
def reset(self):
self.min = Infinity
self.max = -Infinity
self.sum = 0
self.count = 0
class MyList(list):
@property
def length(self):
return len(self)
@property
def is_empty(self):
return not self
@property
def first(self):
return self[0]
@property
def last(self):
return self[-1]
@property
def is_sorted(self, key=lambda x: x):
for i in range(len(self) - 1):
if key(self[i]) > key(self[i + 1]):
return False
return True
def push(self, element):
return self.append(element)
def for_each(self, callback):
if not callable(callback):
raise ValueError(f'Expected a function, got {callback} instead.')
arg_count = len(inspect.getfullargspec(callback).args)
for i, item in enumerate(self):
arguments = []
if arg_count >= 1:
arguments.append(item)
if arg_count >= 2:
arguments.append(i)
callback(*arguments)
def map(self, callback):
if not callable(callback):
raise ValueError(f'Expected a function, got {callback} instead.')
return MyList(map(callback, self))
# Initialize n-dimensional list with
# result of a lambda or just a value
@classmethod
def of(cls, size, value):
if not isinstance(size, list):
raise ValueError('Expected size to be a list of dimensions.')
if len(size) == 0:
raise ValueError('Size cannot be empty.')
invalid_sizes_type = list(filter(lambda x: not isinstance(x, int), size))
if len(invalid_sizes_type) > 0:
raise ValueError('Sizes should be integers.')
invalid_sizes_value = list(filter(lambda x: x <= 0, size))
if len(invalid_sizes_value) > 0:
raise ValueError('Sizes should be positive.')
return MyList._of(size[::-1], value)
@classmethod
def _of(cls, size, value):
if len(size) == 1:
try:
return MyList(value() for _ in range(size[0]))
except TypeError:
return MyList(value for _ in range(size[0]))
else:
count = size.pop()
return MyList(
MyList._of(size[:], value) for _ in range(count)
)
# overriding so that MyList is returned instead of list
def copy(self):
return MyList(list.copy(self))
# overriding so that MyList is returned instead of list
def __add__(self, other):
return MyList(list.__add__(self, other))
# overriding so that MyList is returned instead of list
def __mul__(self, other):
return MyList(list.__mul__(self, other))
class Edge:
def __init__(self, nodes, i1, i2):
self.i1 = i1
self.i2 = i2
self.weight = float('inf')
self.find_weight(nodes)
def find_weight(self, nodes):
node_1 = nodes[self.i1]
node_2 = nodes[self.i2]
weight = 0
for p1, p2 in zip(node_1, node_2):
weight += abs(p1 - p2)
self.weight = weight
def get_required_edges(d, points):
required_edges = MyList()
for i in range(pow(2, d - 1) + 1):
mask_edge_weights = MyList()
for index, point in enumerate(points):
mask = ('00000' + bin(i)[2:])[-5:]
this = This()
for bit, p in zip(mask, point):
if bit == '1':
this.sum += p
else:
this.sum -= p
mask_edge_weights.push((this.sum, index))
min_index = min(mask_edge_weights, key=lambda x: x[0])[1]
max_index = max(mask_edge_weights, key=lambda x: x[0])[1]
for index, point in enumerate(points):
edge_1 = Edge(points, min_index, index)
edge_2 = Edge(points, max_index, index)
required_edges.push(edge_1)
required_edges.push(edge_2)
return required_edges
def disjoint_set_union__get(index, parents):
if index == parents[index]:
return index
parents[index] = disjoint_set_union__get(parents[index], parents)
return parents[index]
def disjoint_set_union__union(i1, i2, parents):
p1 = disjoint_set_union__get(i1, parents)
p2 = disjoint_set_union__get(i2, parents)
if p1 == p2:
return False
parents[p2] = p1
return True
def kruskal_maximum_spanning_tree(points, edges):
edges.sort(reverse=True, key=lambda x: x.weight)
parents = MyList(range(len(points)))
total_weight = 0
for edge in edges:
if edge.i1 == edge.i2:
continue
if disjoint_set_union__union(edge.i1, edge.i2, parents):
total_weight += edge.weight
print(total_weight)
def solve(d, points):
required_edges = get_required_edges(d, points)
kruskal_maximum_spanning_tree(points, required_edges)
def main():
n, d = integer_array_input()
points = MyList()
for _ in range(n):
point = integer_array_input()
points.push(point)
solve(d, points)
main()
Hey guys I have figured out the concept of the logic and have applied the same after a lot of efforts.
- I found the edges and stored them into a priority queue.
- Then I am applying Kruskal’s Algorithm on my priority queue.
All is going good but the last and only test case is giving me TLE.
Link: My submission
I am not able to understand why. Only 1 case giving TLE and other time is low. It’s confusing me as hell. Please help. Any insight would be great. According to me the time complexity of the Kruskal, as I implemented, is O ( E l o g V ).
Can someone please take a little bit of time to make me understand this. I am noobie and as always thank you everyone for forming this amazing community.
3 Likes
I tried to study delaunay triangulation too, but it had many pre requisites and other concepts to be learnt, so I thought 10pts are enough now.
I struggled with this problem too, so take this with a grain of salt. When I looked at your code, your disjoint set (parent/findParent) looks strange. Specifically the two lines like parent[p1] += parent[p2]. Compare that to the Setter’s get and uni functions.
1 Like
trying to solve this problem from last 3 days but not able understand anything from this editorial.
can anyone explain in simple word of this editorial.
Sorry to say but this editorial is a complete piece of shit.
2 Likes
what to do bro how to solve this problem ?