i used the same as setters code for all dsu part but i am still getting tle in last tc, i even used rank compression but it still gives tle. I am writing in java could it possibly be due to that? it would be great if anyone helps, here’s my submission
Instead of n(2^d) edges, can we alternatively just find the mask which has the furthest 2 points across all such combinations, and then add edges of that combination only?
I optimised your code. Here is your code: Code
The optimisations were:
- You don’t have to iterate over all the 2^d edges but rather (2^d)/2 edges. Draw binary you’ll get that.
- You are sorting the list of elements again and again for every dimention. That won’t work. It’s too much wasting resources. Do that thing in O(1) instead.
Good luck.
1 Like
Posting in case anyone else is failing the last test case in C++ because I just spent an unhealthy amount of time looking for this.
For my case, I filtered for the minimal number of possible edges and was applying Kruskal’s algorithm with Union Find for cycle checking. However, my datatype for storing the edges was vector<vector<int>> which is unnecessary and very expensive. I overlooked the fact that the editorial was using vector<pair<int, pair<int, int>>>, but it turned out to be a critical error for me.
I generally code in Python, but my submission in Python is still getting TLE on the last test case, despite using the exact same logic I applied in my AC C++ submission. Are there any Python-specific optimizations I can try that aren’t too far off from the editorial solution? Pretty much all the AC Python submissions I’ve seen only get 10 points.
1 Like
gawd!!!
1 Like
@gainullinildar @supersri_pro
What will be the change if I want to find the Minimum Spanning Tree Weight for this problem.
I dont thing just increasing sort will work because you
int s = min_element(e.begin(), e.end())->second;
int t = max_element(e.begin(), e.end())->second;
for (int x = 0; x < n; x++) {
add_edge(s, x);
add_edge(t, x);
}
did this for finding maximum.
What should i do for minimum.
Thanks in advance.
I use 2^d method in editorial to solve Manhattan question and solve problem by Prim-based method. Keep visited set A and unvisited set B, and maintain Amax_mask as the max value for every mask in visit points A, and B[mask] is a set to keep all point info(value, id) of unvisit points B.
In each iteration, from all masks, find max of Amax_mask - B[mask].begin, and get the id of the unvisited point, remove all mask info of this point in B[mask], and update Amax_mask, and update answer by adding the distance. Loop n - 1 times, and get the maximum spanning tree weight.
I’m confused my result is different with setter’s, and I try some small cases, like 1-demention of 5 points: 0 2 4 7 8, my program get answer 25, but setter’s get just 0.
Cound anyone help me with my logic? Here is my code: pastebin
What will be the change if I want to find the Minimum Spanning Tree Weight for this problem.
I don’t thing just increasing sort will work because in the Setter’s solution he
int s = min_element(e.begin(), e.end())->second;
int t = max_element(e.begin(), e.end())->second;
for (int x = 0; x < n; x++) {
add_edge(s, x);
add_edge(t, x);
}
did this for finding maximum.
What should i do for minimum.
Please , all Expert Coder’s help me finding the correct solution.
Thanks in advance.
Guys this problem just doesnt work in python… i wrote the same soln both in python (python3, pypy3) and in cpp … in python 3 its very fast enough for 2nd last subtask but for some reason it timesout for last subtask… i have tried all sorts of optimizations to bring down the runtime in python but still TLE on last one… even tried fastIO but no use…
My AC solns:
[100pts] C++
[10 pts] Same Soln Pypy3/Python3
Complexity is same as editorial O( (2^(d-1)* n* d) + (2^(d-1)* n* Log(2^(d-1)*n) ) )
Due to sorting of 2^(d-1) * n edges ( 2nd part)
I even found a weird behaviour in one of my python submissions,
These solns,
1st subtask timingout in Pypy3 while the 2nd last subtask in fast enough lol
Exactly same soln 10 pts in Python3
It’s not even that i have some infinite while loop or something which is failing on some edge case… just one recursive function on union and find… even if it happens to be an infinite recursion i would have been getting a runtime error instead (Max recursion depth exceeded) but no its TLE.
My question is only very very few people have got full AC in python although some approaches were same as given in editorials … Is there any other optimizations required in python? am i missing something ? or for questions like this (tight constraints) do we always need to switch to cpp/ java?
To find the maximum we are finding an edge between min and max as you have shared above. To find Minimum we have to get min edge that will be abs(current value - (value just greater than it)) or
abs(current value - (value just smaller than it)), To do this you can just find the lower bound of the value, And also instead of 2^(d-1) you will have to check 2^d times or you can just check 2^(d-1) times and make the values negative once and once positive.
You can check this for better understanding:
Min Spanning tree 2D
1 Like
@sameer_bamanha
actually i think then for each combination we will connect all the node in linear order like after taking a1+a2+a3 we will sort it and then Nth will be connected with N+1 bcz that’s the sortest distance. this approach is right or wrong ???
If there are other approaches that manage to pass in Python, then it is not mandatory to switch to cpp or java in this problem. Anyway I would recommend you to do that for competitive programming
1 Like
Thanks for replying and trying out my code, I appreciate the efforts! Yeah I understand but this problem is kinda an exception I have encountered for the first time. I just now saw that someone modified my code and got an 100 AC but when I tried submitting the same exact code I’m getting only 10pts. I feel that the few people who got AC could be because of this anomalous behaviour in python submissions.
Solns
100 AC Code
10pts (Same exact code)
Here’s a link to diffchecker to verify its the same exact code
Anyways, it was a very nice learning experience this long and Yes I’m surely gonna be switching to C++ for competitive programming !
Maybe we’ll find it on unacademy 
.
Why can’t we just sort the points with the origin and connect first and last node then check one by one node if it has more distance to first node connect it with first otherwise connect with last. Please help me understand where this logic fails ?
sorting will increase time complexity.
Same here