# Super Maximum Cost Queries

# Super Maximum Cost Queries

nikhil_gupta3591 + 0 comments For first time, i got hint from categroy, problem was posted for.

Kartik1607 + 0 comments The editorials are bad at its best. It explains the solution and not the path to discovery. Here is my take on the solution.

So, we are given a weighted graph, and we are asked to print the number of paths in the graph having cost C.

*Cost of path*= C which is maximum weight of any edge in the path.Suppose I have a graph with N nodes, then

`Total number of edges = (N*(N-1))/2`

Value of C

**can be too big**so I cannot memoize for*all*values of C. But there are**atmost**`10^5`

different value of C, which**can be memoized**Idea : If I can get a graph whose each edge weight

*X or less than X*, then I can calculate number of edges in graph which is answer of cost X.Ah, hah. I can build a graph step by step considering cost of edges in increasing order. ie . First graph would have all edges with cost <= 1, then the graph would be updated for cost <= 2 and so on.

So,

**Step 1: Sort the input by cost**struct Q { int x; int y; long long cost; }; bool compareByCost(const Q &a, const Q &b) { return a.cost < b.cost; } sort(queries.begin(), queries.end(), compareByCost);

Now, I need to process the input, which is nothing but connecting node x with node y.

**Step 2: Creating the graph**for(auto q: queries) { int c = q.cost; join(q.x, q.y, c); }

Here, the join function

*finds the root of x, and root of y*and makes a union of the different tree.I can

**also update the answer**for cost c as well.// Returns root of node X and performs path compression. int getroot(int x) { if (root[x] == x) return x; root[x] = getroot(root[x]); return root[x]; } void join(int a, int b, long long c) { // Getting root of both a and b tress. int roota = getroot(a); int rootb = getroot(b); if(roota == rootb) return; // No need to do anything. They both belong to same tree already root[rootb] = roota; // Different trees, join them long long totalToRemove = 0; long long n = rcount[roota] ; // Number of nodes in tree A totalToRemove += (n*(n-1))/2; n = rcount[rootb] ; totalToRemove += (n*(n-1))/2; // Number of nodes in tree B rcount[roota] += rcount[rootb]; // Tree A now also contains all nodes of tree B. Update the count n = rcount[roota] ; long long totalToAdd = (n*(n-1))/2; // Number of nodes in updated Tree. costCounts[c] += (totalToAdd - totalToRemove); }

So, now my map contains answer for all the given cost. There are

*Q*queries, and at most*N*costs.*Q x N*will cause a Timeout. I now need to find a way to calculate sum for [L,R] fast.Currently my cost map returns returns cost of X, what if my cost map returned cost for all x <= X. A prefix sum!

**Step 3: Optimize cost counts prefix sum**long long maxC = 0; for(auto it: costCounts) { sum += it.second; costSum[it.first] = sum; maxC = max(maxC, it.first); }

Now, i can easily find out answer by binary searching :)

**Step 4: Spit answers**while(q--) { long long l,r; cin>>l>>r; r = min(r, maxC); long long lA = 0, rA; auto left = costSum.lower_bound(l); if (left != costSum.begin()){ --left; lA = left->second; } auto right = costSum.lower_bound(r); if (right->first > r) --right; rA = right->second; long long ans = rA - lA; cout<<ans<<"\n"; }

Any you get a good green Accepted Solution. :)

tpcemail + 0 comments fist i sort the edges,then i caculate the number of paths whos weight not bigger than a value,and put them into a table. last i look up in the table to get answer.it took me so long bu finally i pass all the case!

#include<iostream> #include<vector> using namespace std; //edge struct Edge { int dot1, dot2, weight; }; //for qsort int compare(const void *a, const void *b) { Edge* e1 = (Edge*)a; Edge* e2 = (Edge*)b; return e1->weight - e2->weight; } //number of paths whos weight is no bigger than weight. struct WeightPaths { long long weight, paths; }; //disjoint set's find int find_root(vector<int> &v, int x) { if (v[x] == x) return x; else { v[x] = find_root(v, v[x]); return v[x]; } } //binary search long long search(vector<WeightPaths> &weightPaths, int n) { int min = 0, max = weightPaths.size() - 1; long long result = 0; while (true) { if (max - min <= 1) break; int mean = (min + max) / 2; if (weightPaths[mean].weight > n) max = mean; else min = mean; } if (weightPaths[max].weight <= n) result = weightPaths[max].paths; else result = weightPaths[min].paths; return result; } int main() { int n, q; cin >> n >> q; Edge * Edges = new Edge[n - 1]; for (int i = 0;i < n - 1;i++) cin >> Edges[i].dot1 >> Edges[i].dot2 >> Edges[i].weight; qsort(Edges, n - 1, sizeof(Edge), compare); //sort vector<WeightPaths> weightPaths; WeightPaths wp; wp.weight = 0; wp.paths = 0; weightPaths.push_back(wp); vector<int> root(n + 1), count(n + 1); //disjoint set for (int i = 1;i < n + 1;i++) { root[i] = i; count[i] = 1; } int k = 0; while (k<n-1) { wp.weight = Edges[k].weight; while (k<n - 1 && Edges[k].weight == wp.weight) { int dot1 = Edges[k].dot1; int dot2 = Edges[k].dot2; int r1, r2; r1 = find_root(root, dot1); r2 = find_root(root, dot2); if (r1 != r2) { wp.paths += (long long)count[r2] * count[r1]; // caculate new paths root[r2] = r1; count[r1] += count[r2]; count[r2] = 0; } k++; } weightPaths.push_back(wp); } while (q--) { int l, r; cin >> l >> r; long long ln, rn, p; ln = search(weightPaths, l - 1); rn = search(weightPaths, r); p = rn - ln; cout << p << endl; } return 0; }

lingbo19_tang + 2 comments I'm confused, for example, query [1,2] of the graph should be {3,4} and {1,4}, not {1,3} because 1 -> 3 has a cost 3, am I missing something?

jabbarthejack + 0 comments aao kabi haveli pey samjatha

LittleFox + 0 comments Path cost is MAX of edges cost on the path and not SUM of edges cost.

noushadamir08 + 0 comments A TV is a daily entertainment package, but sometimes due to specific reasons, you may face an issue. Get Your LED LCD TV Repair & Service by Certified Experts. TV Repair Services Dubai team has years of experience in delivering top-notch solutions when it comes to TV repair. Instant support as per your requirement, Reasonable Service charges, Assured problem solutions, On-time delivery

kumaramitynr1997 + 0 comments Tv Repair Services Over the course of the next few (actually many) days, I will be posting the solutions to previous Hacker Rank challenges. The page is a good start for people to solve these problems as the time constraints are rather forgiving. I have most solutions in C++, but I will be trying to post them in Python. The language is more readable. Recently I started adding Rust code as well.

nahidrana00786 + 0 comments TV Repair Dubai If you are looking for Tv repair we provide best Tv repair service with customer satisfaction .We have a good team of Experience technician. Our main objective is to provide good technical support and quality service as per our commitment. We also provide services in Dubai as well.For more Details you can visit our website.

noushadamir08 + 0 comments Problem are very easy and quick solve by UAE Technician . very good and supportive technical team .for best and quality solution related Microsoft support service visit ms support service

shushil1kumar2 + 0 comments Thanks for this information,its a really nice post. But are you satisfied your website logo if not visit Logo Design Services in Australia and get attractive professional logo.

OrcaKnowsBest + 0 comments Tried this. But it is very slow because of its terrible complexity and it times out for all large inputs:

`static int[] solve(int[][] tree, int[][] queries) { int low = 0, high = 0; ArrayList<Integer> maxPathCostArray = new ArrayList<Integer>(); maxPathCostArray = getMaxPathCostArray(tree); int[] result = new int[queries.length]; for(int i = 0; i < queries.length; i++){ low = queries[i][0]; high = queries[i][1]; for(int k = 0; k < maxPathCostArray.size(); k++){ if(maxPathCostArray.get(k) >= low && maxPathCostArray.get(k) <= high) result[i]++; } } return result; } static ArrayList<Integer> getMaxPathCostArray(int[][] tree){ int n = tree.length + 1; //number of nodes int maxPathCost = 0; int from = 0; int to = 0; ArrayList<Integer> maxPathCostArray = new ArrayList<Integer>(); //Loop through all nodes for(int i = 1; i <= n - 1; i++){ from = i; for(int j = i + 1; j <= n; j++) { to = j; maxPathCostArray.add(getMaxCostForPath(from, to, tree)); } } return maxPathCostArray; } static int getMaxCostForPath(int from, int to, int[][] tree){ ArrayList<Integer> visited = new ArrayList<Integer>(); Stack<Integer> stack = new Stack<Integer>(); stack.push(from); visited.add(from); int maxCost = 0; boolean pathFound = false; int newNode = 0; int x = 0, y = 0; while(stack.peek() != to){ for(int i = 0; i < tree.length; i++){ if(stack.peek() == tree[i][0] && !visited.contains(tree[i][1])){ newNode = tree[i][1]; pathFound = true; } if(stack.peek() == tree[i][1] && !visited.contains(tree[i][0])){ newNode = tree[i][0]; pathFound = true; } } if(stack.peek() != to && pathFound == false) stack.pop(); else { stack.push(newNode); visited.add(newNode); pathFound = false; } } while(stack.peek() != from){ x = stack.pop(); y = stack.peek(); for(int i = 0; i < tree.length; i++){ if((tree[i][0] == x && tree[i][1] == y) || (tree[i][0] == y && tree[i][1] == x)) if(tree[i][2] > maxCost) maxCost = tree[i][2]; } } return maxCost; }`

Sort 21 Discussions, By:

Please Login in order to post a comment