Sort by

recency

|

33 Discussions

|

  • + 0 comments

    Here is my very simple solution in c++;

    #include <bits/stdc++.h>
    using namespace std;
    long maximumPeople(vector<long> p, vector<long> x, vector<long> y, vector<long> r) {
        vector<pair<long,long>> cl;
        vector<pair<long,long>> pl;
        int cn=y.size();
        int tn=x.size();
        for(int i=0;i<cn;i++) cl.push_back({y[i]-r[i],y[i]+r[i]});
        for(int i=0;i<tn;i++) pl.push_back({x[i],p[i]});
        sort(cl.begin(),cl.end());
        sort(pl.begin(),pl.end());
        vector<long> surrounded(cn,0);
        long already=0;
        long must=0;
        int nc=0;
        for(int town=0;town<tn;town++){
            while(nc<cn && cl[nc].second<pl[town].first) nc++;
            
            if(nc>=cn) already+=pl[town].second;
            else if(cl[nc].first>pl[town].first) already+=pl[town].second;
            else{
                int justnext=nc+1;
                while(justnext<cn && cl[justnext].second<pl[town].first) justnext++;
                
                if(justnext>=cn) surrounded[nc]+=pl[town].second;
                else if(cl[justnext].first>pl[town].first) surrounded[nc]+=pl[town].second;
            }
        }
        for(auto e:surrounded) must=max(must,e);
        
        return must+already;
    }
    int main()
    {
        int n,m;
        cin >> n;
        vector<long> p(n),x(n);
        for (int i = 0; i < n; i++)cin >> p[i];
        for (int i = 0; i < n; i++)cin >> x[i];
        cin >> m;
        vector<long>y(m),r(m);
        for (int i = 0; i < m; i++)cin >> y[i];
        for (int i = 0; i < m; i++)cin >> r[i] ;
        long result = maximumPeople(p, x, y, r);
        cout << result;
    }
    
  • + 0 comments

    if any one have correct code in c please send me...

  • + 0 comments

    Array Manipulation can be solved using a similar technique as the one you probably used to solve this problem.

    The problem my initial solution had was not imposing any order in which I deal with each event type. At each location on the line, you should first deal with clouds starting (suddenly being under a cloud). Then you should deal with any towns at that location. And finally deal with clouds ending.

    I think the best way to implement this ordering is to make sure the events are sorted in that order. For example, my events were tuples of the form (location, event type, id). event type is either 0, 1, or 2 with 0 representing cloud ending, 1 representing cloud start, and 2 representing town. This works in Python because tuples are ordered lexicographically. So if events have the same location, they will then be ordered based on their event type (and if they have the same event type, they are ordered by id but by that point, it won't matter which order those events are sorted in.)

    Another implementation idea that can be combined with the one above is to move the "cloud ending" event from location (y + r) to location (y + r + 1). This can avoid the confusion of having to hold in your head the conflicting ideas of "this cloud is still in effect" and "this cloud needs to go."

    This implementation detail doesn't matter as much in this problem since imposing the order in which we deal with each event type means we can just deal with each event as they come up. However it does seem to be a good practice as you might see if you attempt Array Manipulation.

  • + 0 comments

    is the sample input given for this question incomplete?

  • + 0 comments

    I get just one testcase wrong, any help appreciated ! https://www.hackerrank.com/contests/hourrank-26/challenges/cloudy-day/submissions/code/1306767298