Sort by

recency

|

53 Discussions

|

  • + 1 comment
    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    #
    # Complete the 'maximumPeople' function below.
    #
    # The function is expected to return a LONG_INTEGER.
    # The function accepts following parameters:
    #  1. LONG_INTEGER_ARRAY p
    #  2. LONG_INTEGER_ARRAY x
    #  3. LONG_INTEGER_ARRAY y
    #  4. LONG_INTEGER_ARRAY r
    #
    
    def maximumPeople(p, x, y, r):
        townsCount = len(x)
        cloudsCount = len(y)
        
        townPopulation = p
        townLocations = x
        cloudLocations = y
        cloudRanges = r
        
        sunnyPeople = 0
        
        # get every cloud effective range
        clouds = []
        for i in range(cloudsCount):
            x = [cloudLocations[i]]
            for j in range(cloudRanges[i]):
                x.append(cloudLocations[i] - 1)
                x.append(cloudLocations[i] + 1)
            clouds.append(x)
        
        # get towns exposed to sun and append its population to sunnyPeople
        # and clouded towns population to clouded
        clouded = []
        for townLocation in townLocations:
            for index, sublist in enumerate(clouds):
                if townLocation in sublist:
                    clouded.append(townPopulation[townLocations.index(townLocation)])
                else:
                    sunnyPeople += townPopulation[townLocations.index(townLocation)]
        
        # return sunnyPeople and the max population exposed to sun
        return sunnyPeople + max(clouded)
            
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        n = int(input().strip())
    
        p = list(map(int, input().rstrip().split()))
    
        x = list(map(int, input().rstrip().split()))
    
        m = int(input().strip())
    
        y = list(map(int, input().rstrip().split()))
    
        r = list(map(int, input().rstrip().split()))
    
        result = maximumPeople(p, x, y, r)
    
        fptr.write(str(result) + '\n')
    
        fptr.close()
    
  • + 0 comments

    For something different, here's a parallelizable solution in Java 22, using a Skip List. In theory 𝚯(1) runtime given N processors. (In practice the overhead likely subsumes any gains.)

    /**
     * Return the maximum population in a sunny town after
     * removing exactly one cloud.
     * https://www.hackerrank.com/challenges/cloudy-day/
     *
     * Fairly simple implementation problem.
     *
     * 1) Represent each town's location in a Skiplist.
     *  If towns share a location, simply treat them as combined.
     * 2) For each cloud, assign towns within range to it.
     * Important: remove any towns already covered by this cloud. This keeps
     * the algorithm runtime linear.
     * 3) Now for each town, group their populations by the cloud covering them.
     *
     * 4) Find the largest group, then add the uncovered towns ("NONE")
     *
     * 𝚯(M + N log N) runtime for M clouds and N towns.
     * 𝚯(M + N) space complexity 
     */
    public static long maximumPeople(List<Long> p, List<Long> x, List<Long> y, List<Long> r) {
        final Cloud NONE = new Cloud(0, 0, -1L);
        // 1) Town -> Cloud
        ConcurrentSkipListMap<Long, Cloud> cover = rangeOf(x.size())
                .parallel()
                .collect(Collectors.toMap(x::get, a -> NONE, (a, b) -> a, ConcurrentSkipListMap::new));
    
        // 2) for each cloud, assign any virgin towns to it. Remove any others.
        rangeOf(y.size()).map(i -> new Cloud(y.get(i), r.get(i), i))
                .parallel()
                .forEach(c ->
                    cover.subMap(c.start(), c.end()).forEach((a, b) -> {
                        if (b == NONE) cover.put(a, c);
                        else cover.remove(a);
                    }));
    
        // Sum the populations for each cloud.
        Map<Long, Long> popByLocation = rangeOf(x.size()).collect(Collectors.toMap(x::get, p::get, Long::sum));
        Map<Cloud, Long> popByCloud = cover.entrySet().stream()
                .parallel()
                .collect(Collectors.groupingByConcurrent(
                    Map.Entry::getValue,
                    Collectors.summingLong(e -> popByLocation.get(e.getKey())))
                );
    
        // 3) Now find the cloud with the largest population
        long largest = popByCloud.values().stream().max(Comparator.comparingLong(e -> e)).orElse(0L);
    
        // 4) Sum it with uncovered towns, if any
        Long uncovered = popByCloud.remove(NONE);
        if(uncovered != null)
            largest += uncovered;
        return largest;
    }
    private record Cloud(long location, long range, long name) {
        long start() { return location - range; }
        long end() { return location + range + 1; } // exclusive
    }
    // helper function for a parallel stream
    private static Stream<Integer> rangeOf(int n) {
        return IntStream.range(0, n).boxed();
    }
    
  • + 0 comments
    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    # Complete the maximumPeople function below.
    from collections import defaultdict
    
    
    def maximumPeople(towns, cloud_start, cloud_end):
        towns = sorted(towns)
        cloud_start = sorted(cloud_start)
        cloud_end = sorted(cloud_end)
    
        cloud_start_i = 0
        cloud_end_i = 0
        clouds = set()
    
        d = defaultdict(int)
        free = 0
        for town_i in range(len(towns)):
            town_x = towns[town_i][0]
            while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
                clouds.add(cloud_start[cloud_start_i][1])
                cloud_start_i += 1
            while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
                clouds.remove(cloud_end[cloud_end_i][1])
                cloud_end_i += 1
            if len(clouds) == 1:
                towns[town_i][2] = list(clouds)[0]
                d[list(clouds)[0]] += towns[town_i][1]
            elif len(clouds) == 0:
                free += towns[town_i][1]
    
        return max(d.values(), default=0) + free
    
    
    def main():
        n = int(input().strip())
        p = [int(x) for x in input().strip().split()]
        x = [int(x) for x in input().strip().split()]
        towns = [[xi, pi, -1] for xi, pi in zip(x, p)]
        m = int(input().strip())
        y = [int(x) for x in input().strip().split()]
        r = [int(x) for x in input().strip().split()]
        cloud_start = [[y[i]-r[i], i] for i in range(m)]
        cloud_end = [[y[i]+r[i], i] for i in range(m)]
        result = maximumPeople(towns, cloud_start, cloud_end)
        print(result)
    
    if __name__ == "__main__":
        main()
    
  • + 0 comments

    Python:

    def maximumPeople(p, x, y, r): # Return the maximum number of people that will be in a sunny town after removing exactly one cloud.

    cities = [[i[0], i[1]] for i in zip(x, p)]  # cities or towns
    cities = sorted(cities, key=lambda x: (x[0]))
    
    clouds = [[max(1, i[0]-i[1]), i[0]+i[1]] for idx, i in enumerate(zip(y, r))]
    clouds = sorted(clouds, key=lambda x: (x[0]))
    
    len_cloud = len(clouds)
    idx = 0
    start = 0
    sum_sunny = 0
    cloud_city = [0 for _ in range(len_cloud)]
    for j in cities:
        count = []
        check = True
        idx = start
    
        while idx < len_cloud:
            i = clouds[idx]
            if check and i[1] < j[0]:
                start = idx+1
                idx += 1
                continue
    
            if i[1] >= j[0]:
                check = False
    
            if i[0] <= j[0] and j[0] <= i[1]:
                count.append(idx)
    
            if len(count) > 1:
                break
    
            if i[0] > j[0]:
                break
    
            idx += 1
    
        if len(count) == 0:
            sum_sunny += j[1]
        if len(count) == 1:
            cloud_city[count[0]] += j[1]
    
    
    sum_cloud = max(cloud_city)
    # print(cities, selected_clouds)
    # print(sum_sunny, sum_cloud)
    return sum_sunny + sum_cloud
    
  • + 0 comments
    inline constexpr long START=1, TOWN=2, END=3;
    
    struct Event {
        long position{0};
        long type{1};
        long population{0};
        size_t cloud_idx{0};
        Event(long p, long t, long popn, size_t idx=0) : position(p), type(t), population{popn}, cloud_idx{idx} {}
        bool operator<(const Event& other)
        {
            return std::tie(position, type) < std::tie(other.position, other.type);
        }
    };
    
    long maximumPeople(vector<long>& p,vector<long>& x, vector<long>& y, vector<long>& r) {
        // Return the maximum number of people that will be in a sunny town after removing exactly one cloud.
        std::vector<Event> all_events;
        std::transform(
            p.begin(), p.end(),
            x.begin(),
            std::back_inserter(all_events),
            [](long popn, long pos)
            {
                return Event(pos, TOWN, popn);
            }
        );
        std::inner_product(
            y.begin(), y.end(),
            r.begin(),
            std::reference_wrapper(all_events),
            [idx=0ll](auto&& v, const auto& pair) mutable {
                const auto& [pos, rad] = pair;
                v.get().emplace_back(pos-rad, START, -1, idx);
                v.get().emplace_back(pos+rad, END, -1, idx);
                ++idx;
                return std::move(v);
            },
            [](long pos, long rad)
            {
                return std::make_pair(
                    pos, rad
                );
            }
        );
        // cout << all_events.size() << endl;
        std::sort(all_events.begin(), all_events.end());
        std::unordered_set<long> active_cloud;
        std::unordered_map<size_t, long> cloud_to_popn;
        long always_sunny = 0;
        for (const auto& event : all_events)
        {
            switch (event.type)
            {
                case START:
                    active_cloud.emplace(event.cloud_idx);
                    break;
                case TOWN:
                    if (active_cloud.size() == 1)
                    {
                        cloud_to_popn[*active_cloud.begin()] += event.population;
                    }
                    else if (active_cloud.size() == 0)
                    {
                        always_sunny += event.population;
                    }
                    break;
                case END:
                    active_cloud.erase(event.cloud_idx);
                    break;
                default:
                    break;
            }
        }
        auto max_elem = std::max_element(
            cloud_to_popn.begin(),
            cloud_to_popn.end(),
            [](const auto& p1, const auto& p2){ return p1.second < p2.second;}
        );
        long ret = always_sunny + (max_elem != cloud_to_popn.end() ? max_elem->second : 0ll);
        return ret;
    }