We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Maximizing Mission Points
  5. Discussions

Maximizing Mission Points

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 16 Discussions, By:

votes

Please Login in order to post a comment

  • vtarakan
    3 years ago+ 1 comment

    Very neat little problem! I'll try to give a few hints without giving too much away. Btw, I used a somewhat different approach to the editorial - so there're definitely more than 1 way to tackle this.

    1) There's a definite DP feeling to this problem (Editorial talks about this explicitly). I started by formulating a very straighforward O(N^2) approach.

    2) Next step was to take O(N^2) to something better. It quickly became apparent that if I could find points on the plant faster than O(N), say O(LogN) - I'd resepectively improve the overall asymptotic.

    3) Luckly I was already faimilar with KD-trees, Oct-trees and the like. I chose Quad-tree for this problem due to the following (hints): a) Simple and compact implementation b) LogN updates..This is what swayed the decision. c) LogN quries. This is shared with other "binary" data structures and is not what swayed the decision.

    4) Whilst quad-tree is LogN update/query, often enought we need to ask quesitons about all points. If done naively that degenerates to O(N) even with quad tree. However, if we keep track of the desired propeties in every tree node - and only recurse when we need to - this becomes desired LogN again.

    5) Last step was needed only to pass the last test (I saw someone else in the discussion also getting 63 points and not 70 due to timeouts). Whilst the bound on q-tree is LogN - there're just too many of those quries. We can improve on 4) by only recursing when we know the recursive call might be able to improve the result. This aggressively culls useless branches from the quadtree ontop of the already good LogN time.

    5|
    Permalink
  • humoyun_ahmad
    5 years ago+ 0 comments

    Nobody is talking about this challenge yet. Why not start the first discussion? :)

    4|
    Permalink
  • willson_vieira
    1 year ago+ 3 comments
    //Pranet Verma
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 200000;
    const long long INF = 1e15;
    
    long long tree[MAXN * 4];
    
    void makeTree() {
        for (int i = 1; i < MAXN * 4; ++i) {
            tree[i] = -INF;
        }
    }
    void update(int x, long long val, int u = 1, int l = 1, int r = MAXN) {
        if (l == r) {
            tree[u] = val;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
            update(x, val, 2 * u, l, m);
        }
        else {
            update(x, val, 2 * u + 1, m + 1, r);
        }
        tree[u] = max(tree[2 * u], tree[2 * u + 1]);
    }
    
    long long query(int x, int y, int u = 1, int l = 1, int r = MAXN) {
        if (x > r or y < l) {
            return -INF;
        }
        if (x <= l and r <= y) {
            return tree[u];
        }
        int m = (l + r) / 2;
        return max(query(x, y, 2 * u, l, m), query(x, y, 2 * u + 1, m + 1, r));
    }
    
    struct Point {
        int x, y, z, w;
        long long dp;
        bool operator < (const Point &o) const {
            return z < o.z;
        }
    };
    Point p[MAXN + 1];
    long long DP[MAXN + 1];
    int X_LIM, Y_LIM;
    void merge(int l, int r) {
        int m = (l + r) / 2;
    
        vector<pair<int, int> > left;
        vector<pair<int, int> > right;
        for (int i = l; i <= m; ++i) {
            left.push_back({p[i].x, p[i].z});
        }       
        for (int i = m + 1; i <= r; ++i) {
            right.push_back({p[i].x, p[i].z});
        }
        sort(left.begin(), left.end());
        sort(right.begin(), right.end());
    
        int left_l = 0;
        int left_r = -1;
        for (auto u : right) {
            int i = u.second;
            int x = u.first;
            while (left_r + 1 < left.size() and left[left_r + 1].first - x <= X_LIM) {
                ++left_r;
                int who = left[left_r].second;
                update(p[who].y, p[who].dp);            
            }
            while (left_l < left.size() and x - left[left_l].first > X_LIM) {
                int who = left[left_l].second;
                update(p[who].y, -INF);
                ++left_l;
            }
            int yLow = max(1, p[i].y - Y_LIM);
            int yHigh = min(MAXN, p[i].y + Y_LIM);
            p[i].dp = max(p[i].dp, p[i].w + query(yLow, yHigh));
        } 
        while (left_l <= left_r) {
            int who = left[left_l].second;
            update(p[who].y, -INF);
            ++left_l;
        }
    }
    void solve(int l, int r) {
        if (l == r) {
            p[l].dp = max(p[l].dp, (long long)p[l].w);
            return;
        }
        int m = (l + r) / 2;
        solve(l, m);
        merge(l, r);
        solve(m + 1, r);
    }
    int main() {
        makeTree();
        int n;
        scanf("%d %d %d", &n, &X_LIM, &Y_LIM); 
        for (int i = 0; i < n; ++i) {
            scanf("%d %d %d %d", &p[i].x, &p[i].y, &p[i].z, &p[i].w);
            p[i].dp = -INF;
        }
        sort(p, p + n);
        for (int i = 0; i < n; ++i) {
            p[i].z = i;
        }
        solve(0, n - 1);
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, p[i].dp);
        }
        printf("%lld\n", ans);
    }
    
    2|
    Permalink
  • wdehnen64
    4 years ago+ 1 comment

    Without the travel restrictions on latitude and longitude, this is a standard dynamical programming problem, solved in O(n lg(n)) by processing the cities in order of increasing height and connecting each to the best-scoring city below (using a heap or BST for organising all cities already processed). With the travel restrictions, I used a grid of BSTs with a grid resolution equal to dlat and dlong. Then only the BSTs at the cell containing the city being processed and the neighbouring cells have to be searched for the best lower neighbouring city. To avoid initialising a large grid of BSTs (most of which may never be used), I used a hash table keyed on the grid index. Some other points: cities which even when connected to the bests route so far yield a negative score can be ignored, as can be routes with negative points.

    1|
    Permalink
  • inanisumeet2019
    4 months ago+ 0 comments

    I used quadtree in c . I got timeout for testcase 8,9,10 . Is it slow if I compare 260 neighbours on an average for a point ?

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature