HackerRank Cloudy Day Problem Solution

In this post, we will solve HackerRank Cloudy Day Problem Solution.

Quibdó in Colombia is one among the cities that receive maximum rainfall in the world.

All year round, the city is covered in clouds. The city has many towns, located on a one-dimensional line. The positions and populations of each town on the number line are known to you. Every cloud covers all towns located at a certain distance from it. A town is said to be in darkness if there exists at least one cloud such that the town is within the cloud’s range. Otherwise, it is said to be sunny.

The city council has determined that they have enough money to remove exactly one cloud using their latest technology. Thus they want to remove the cloud such that the fewest number of people are left in darkness after the cloud is removed. What is the maximum number of people that will be in a sunny town after removing exactly one cloud?

Note: If a town is not covered by any clouds, then it is already considered to be sunny, and the population of this town must also be included in the final answer.

Complete the function maximumPeople which takes four arrays representing the populations of each town, locations of the towns, locations of the clouds, and the extents of coverage of the clouds respectively, and returns the maximum number of people that will be in a sunny town after removing exactly one cloud.

Input Format

The first line of input contains a single integer n, the number of towns.
The next line contains n space-separated integers p. The ith integer in this line denotes the population of the ¿th town.
The next line contains n space-separated integers, denoting the location of the ¿th town on the one-dimensional line.
The next line consists of a single integer m denoting the number of clouds covering the city.
The next line contains m space-separated integers y, the ¿th of which denotes the location of the ¿th cloud on the coordinate axis.
The next line consists of m space-separated integers r, denoting the range of the ¿th cloud. Note: The range of each cloud is computed according to its location, i.e., the ¿th cloud is located at position y, and it covers every town within a distance of r, from it. In other words, the ¿th cloud covers every town with location in the range [y; – ri, y₁ + ri].

Output Format

Print a single integer denoting the maximum number of people that will be in a sunny town by removing exactly one cloud.

Sample Input 0

Sample Output 0

Explanation 0

In the sample case, there is only one cloud which covers the first town. Our only choice is to remove this sole cloud which will make all towns sunny, and thus, all 110 people will live in a sunny town.

As you can see, the only cloud present, is at location 4 on the number line and has a range 1, so it covers towns located at 3, 4 and 5 on the number line. Hence, the first town is covered by this cloud and removing this cloud makes all towns sunny.

Cloudy Day C++ Solution

//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false); 
ll bit[512345],maxn=512345;

ll update(ll pos,ll val){
	while(pos<maxn){
		bit[pos]+=val;
		pos+=pos&(-pos);
	}
	return 0;
}
ll query(ll pos){
	ll ans=0;
	while(pos>0){
		ans+=bit[pos];
		pos-=pos&(-pos);
	}
	return ans;
}
map<ll,ll>mapi;
ll x[212345],p[212345],y[112345],r[112345],st[112345],en[123456];
ll valid[212345];
int main(){
    std::ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll i;
    rep(i,n){
    	cin>>p[i];
    }
    rep(i,n){
    	cin>>x[i];
    	mapi[x[i]]=0;
    }
    ll m;
    cin>>m;
    rep(i,m){
    	cin>>y[i];
    }
    rep(i,m){
    	cin>>r[i];
    	mapi[y[i]-r[i]]=0;
    	mapi[y[i]+r[i]]=0;

    }
    ll counter =1;
    map<ll,ll>::iterator it;
    for(it=mapi.begin();it!=mapi.end();it++){
    	it->ss=counter++;
    }
    rep(i,n){
    	x[i]=mapi[x[i]];
    }
    rep(i,m){
    	st[i]=mapi[y[i]-r[i]];
    	en[i]=mapi[y[i]+r[i]];
    	update(st[i],1);
    	update(en[i]+1,-1);
    }
    rep(i,n){
    	valid[i]=query(x[i]);
    }
    rep(i,maxn){
    	bit[i]=0;
    }
    ll ans=0;
    rep(i,n){
    	if(valid[i]==1)
    		update(x[i],p[i]);
    	if(!valid[i])
    		ans+=p[i];
    }
    ll maxi=0;
    rep(i,m){
    	maxi=max(maxi,query(en[i])-query(st[i]-1));
    }
    ans+=maxi;
    cout<<ans<<endl;


    return 0;  
    
}

Cloudy Day C Sharp Solution

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Iroha
{
    public Iroha() { }
    public static int Main()
    {
        new Iroha().calc();
        return 0;
    }

    Scanner cin;

    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();

        long BASE = (long)1e9;

        long[] p = cin.ArrayLong(N);
        long[] x = cin.ArrayLong(N, BASE);

        int M = cin.nextInt();
        int[] y = cin.ArrayInt(M);
        int[] r = cin.ArrayInt(M);

        
        long[] s = new long[M];
        long[] g = new long[M];
        for (int i = 0; i < M; i++)
        {
            s[i] = BASE + y[i] - r[i];
            g[i] = BASE + y[i] + r[i];
        }
        long ans = 0;

        long[] add = new long[M];
        Heap<long> h = new Heap<long>();
        for (int i = 0; i < N; i++)
        {
            h.push((x[i] << 30) + p[i] + M);
        }
        for (int i = 0; i < M; i++)
        {
            h.push((s[i] << 30) + i);
            h.push((g[i] << 30) + 0x3FFFFFFF - i);
        }

        int num = 0;
        long last = 0;

        while(h.top != null)
        {
            long now = h.pop();
            long id = now & 0x3FFFFFFF;
            if(id < M)
            {
                num++;
                last += id;
                //Console.WriteLine("find " + id);
            }
            else if(id > 0x3FFFFFFF - M)
            {
                long dec = 0x3FFFFFFF - id;
                last -= dec;
                num--;
                //Console.WriteLine("exit " + dec);
            }
            else
            {
                long pp = (id - M);
                //Console.WriteLine("pp " + pp);
                if (num == 0)
                {
                    ans += pp;
                }
                else if(num == 1)
                {
                    add[(int)last] += pp;
                }
            }
        }

        long best = 0;
        for (int i = 0; i < M; i++)
        {
            best = Math.Max(best, add[i]);
        }
        //Console.WriteLine(best);
        ans += best;
        Console.WriteLine(ans);
    }
}

class Heap<T> where T : IComparable
{
    public HeapNode<T> top;

    public Heap() { }

    public void push(T val)
    {
        top = HeapNode<T>.meld(top, new HeapNode<T>(val));
    }

    public T pop()
    {
        T ret = top.val;
        top = HeapNode<T>.meld(top.r, top.l);
        return ret;
    }

    public void merge(Heap<T> h2)
    {
        top = HeapNode<T>.meld(top, h2.top);
    }

    public class HeapNode<NT> where NT : IComparable
    {
        public HeapNode<NT> l, r;
        public NT val;

        public HeapNode(NT _val)
        {
            val = _val;
        }

        public static HeapNode<NT> meld(HeapNode<NT> a, HeapNode<NT> b)
        {
            if (a == null) return b;
            if (b == null) return a;
            if (a.val.CompareTo(b.val) > 0)
            {
                HeapNode<NT> temp = a;
                a = b;
                b = temp;
            }
            a.r = meld(a.r, b);
            HeapNode<NT> temph = a.l;
            a.l = a.r;
            a.r = temph;
            return a;
        }
    }
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

Cloudy Day Java Solution

import java.io.*;
import java.util.*;

public class Solution {
	static final StdIn in = new StdIn();
	static final PrintWriter out = new PrintWriter(System.out);
	
	public static void main(String[] args) {
		int n=in.nextInt();
		long[] p = in.readLongArray(n);
		int[] x = in.readIntArray(n);
		TreeMap<Integer, Long> map = new TreeMap<Integer, Long>();
		for(int i=0; i<n; ++i) {
			if(!map.containsKey(x[i]))
				map.put(x[i], 0L);
			map.put(x[i], map.get(x[i])+p[i]);
		}
		int m=in.nextInt();
		int[] y = in.readIntArray(m);
		int[] r = in.readIntArray(m);
		Pair[] ranges1 = new Pair[m];
		for(int i=0; i<m; ++i)
			ranges1[i] = new Pair(y[i]-r[i], y[i]+r[i]);
		Arrays.sort(ranges1, new Comparator<Pair>() {
			public int compare(Pair a, Pair b) {
				return a.a==a.b?-(a.b-b.b):a.a-b.a;
			}
		});
		TreeSet<Integer> uncovered = new TreeSet<Integer>();
		for(int i=0; i<n; ++i)
			uncovered.add(x[i]);
		List<Pair> ranges2 = new ArrayList<Pair>(), posAns = new ArrayList<Pair>();
		for(int i=0, lastEnd=0; i<m; ++i) {
			if(ranges1[i].b<=lastEnd) {
				while(true) {
					Integer a=map.ceilingKey(ranges1[i].a);
					if(a==null||a>ranges1[i].b)
						break;
					map.remove(a);
				}
			} else {
				while(true) {
					Integer a=uncovered.ceiling(ranges1[i].a);
					if(a==null||a>ranges1[i].b)
						break;
					uncovered.remove(a);
				}
				ranges2.add(ranges1[i]);
			}
			lastEnd=Math.max(ranges1[i].b, lastEnd);
		}
		for(int i=0; i<ranges2.size(); ++i) {
			int lb=Math.max(i==0?Integer.MIN_VALUE:ranges2.get(i-1).b+1, ranges2.get(i).a);
			int rb=Math.min(i==ranges2.size()-1?Integer.MAX_VALUE:ranges2.get(i+1).a-1, ranges2.get(i).b);
			Pair ans = new Pair(0, 0);
			Integer a=map.lowerKey(lb);
			ans.a=a==null?Integer.MIN_VALUE:a;
			a=map.floorKey(rb);
			ans.b=a==null?Integer.MIN_VALUE:a;
			posAns.add(ans);
		}
		long max=0, pref=0;
		Map<Integer, Long> pmap = new HashMap<Integer, Long>();
		for(Map.Entry<Integer, Long> entry : map.entrySet()) {
			pref+=entry.getValue();
			pmap.put(entry.getKey(), pref);
		}
		for(Pair pi : posAns)
			max=Math.max(pmap.getOrDefault(pi.b, 0L)-pmap.getOrDefault(pi.a, 0L), max);
		for(int i : uncovered)
			max+=map.get(i);
		out.println(max);
		out.close();
	}
	
	static class Pair {
		int a, b;
		Pair(int a, int b) {
			this.a=a;
			this.b=b;
		}
	}
    
    interface Input {
    	public String next();
    	public String nextLine();
    	public int nextInt();
    	public long nextLong();
    	public double nextDouble();
    }
    static class StdIn implements Input {
    	final private int BUFFER_SIZE = 1 << 16;
    	private DataInputStream din;
    	private byte[] buffer;
    	private int bufferPointer, bytesRead;
    	public StdIn() {
    		din = new DataInputStream(System.in);
    		buffer = new byte[BUFFER_SIZE];
    		bufferPointer = bytesRead = 0;
    	}
    	public StdIn(InputStream in) {
    		try{
    			din = new DataInputStream(in);
    		} catch(Exception e) {
    			throw new RuntimeException();
    		}
    		buffer = new byte[BUFFER_SIZE];
    		bufferPointer = bytesRead = 0;
    	}
    	public String next() {
    		int c;
    		while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
    		StringBuilder s = new StringBuilder();
    		while (c != -1)
    		{
    			if (c == ' ' || c == '\n'||c=='\r')
    				break;
    			s.append((char)c);
    			c=read();
    		}
    		return s.toString();
    	}
    	public String nextLine() {
    		int c;
    		while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
    		StringBuilder s = new StringBuilder();
    		while (c != -1)
    		{
    			if (c == '\n'||c=='\r')
    				break;
    			s.append((char)c);
    			c = read();
    		}
    		return s.toString();
    	}
    	public int nextInt() {
    		int ret = 0;
    		byte c = read();
    		while (c <= ' ')
    			c = read();
    		boolean neg = (c == '-');
    		if (neg)
    			c = read();
    		do
    			ret = ret * 10 + c - '0';
    		while ((c = read()) >= '0' && c <= '9');

    		if (neg)
    			return -ret;
    		return ret;
    	}
    	public int[] readIntArray(int n) {
    		int[] ar = new int[n];
    		for(int i=0; i<n; ++i)
    			ar[i]=nextInt();
    		return ar;
    	}
    	public long nextLong() {
    		long ret = 0;
    		byte c = read();
    		while (c <= ' ')
    			c = read();
    		boolean neg = (c == '-');
    		if (neg)
    			c = read();
    		do
    			ret = ret * 10 + c - '0';
    		while ((c = read()) >= '0' && c <= '9');
    		if (neg)
    			return -ret;
    		return ret;
    	}
    	public long[] readLongArray(int n) {
    		long[] ar = new long[n];
    		for(int i=0; i<n; ++i)
    			ar[i]=nextLong();
    		return ar;
    	}
    	public double nextDouble() {
    		double ret = 0, div = 1;
    		byte c = read();
    		while (c <= ' ')
    			c = read();
    		boolean neg = (c == '-');
    		if (neg)
    			c = read();
    		do
    			ret = ret * 10 + c - '0';
    		while ((c = read()) >= '0' && c <= '9');
    		if (c == '.')
    			while ((c = read()) >= '0' && c <= '9')
    				ret += (c - '0') / (div *= 10);
    		if (neg)
    			return -ret;
    		return ret;
    	}
    	private void fillBuffer() throws IOException {
    		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
    		if (bytesRead == -1)
    			buffer[0] = -1;
    	}
    	private byte read() {
    		try{
    			if (bufferPointer == bytesRead)
    				fillBuffer();
    			return buffer[bufferPointer++];
    		} catch(IOException e) {
    			throw new RuntimeException();
    		}
    	}
    	public void close() throws IOException {
    		if (din == null)
    			return;
    		din.close();
    	}
    }
}

Cloudy Day Python Solution

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()

"""
2
10 100
5 100
1
20
1
"""

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python