Techgig

Grizzly Hunting Salmons | Solution

Bob is a grizzly bear and just like all grizzlies he loves hunting salmon fishes. Bob has a special strategy for catching salmons. He stands at the edge of the river and waits for the fishes to cross him. Whenever a fish comes in the same line as that of Bob, he catches it.




For the sake of the problem assume the river is flowing from left to right and Bob is currently sitting at x-coordinate x = 0 (origin). All the fishes are swimming with the river's flow at a uniform speed of 1 from left to right. The x-coordinates increases as we move rightwards in the river and decreases as we move leftwards. Initially all the fishes has non-positive x-coordinates.


You are given the information about N salmons in two arrays len[ ] and time[ ], where len[i] = length of the ith salmon and time[i] = time at which the head of the ith salmon reaches the x-coordinate = 0. So, at any time T, the ith salmon has its head at x-coordinate = T - time[i] and tail at x-coordinate = T - time[i] - len[i].


At any point of time Bob can catch all the salmons whose any part of body (between head and tail, both inclusive) is at x-coordinate = 0.


Bob wants to catch salmons no more than twice. Can you tell the maximum number of salmons Bob can catch.



Input Format

First line of input contains an integer N representing the number of salmons.

Second line of input contains N space separated integers representing the contents of array len[ ].

Third line of input contains N space separated integers representing the contents of array time[ ].

The last line of input is blank.



Constraints

1 <= N <= 1000

1 <= len[i] <= 1000, 000, 000

0 <= time[i] <= 1000, 000, 000



Output Format

An integer representing the maximum number of salmons Bob can catch.



Sample TestCase 1
Input
5
2 4 4 2 4
1 4 1 6 4
Output
5

JAVA


import java.util.*;

public class CandidateCode {

static List<Map<Long, Long>> combinations = new ArrayList<>();

public static void main(String args[]) throws Exception {

Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Set<Long> endSet = new HashSet<>();
Map<Long, List<Long>> endDict = new HashMap<>();
List<Map<Long, Long>> interval = new ArrayList<>();
Set<Long> fishSet = new HashSet<>();

int ans = 0;

Long[] length = new Long[n];
for (int i = 0; i < n; i++) {
length[i] = (long) scan.nextInt();
}

for (int i = 0; i < n; i++) {
Long x = scan.nextLong();
endSet.add(x + length[i]);
interval.add(Collections.singletonMap(x, x + length[i]));
}

for (Long e : endSet) {
Long i = 0L;
List<Long> list = new ArrayList<>();
for (Map<Long, Long> m : interval) {
for (Map.Entry<Long, Long> entry : m.entrySet()) {
if (entry.getKey() <= e && e <= entry.getValue()) {
list.add(i);
}
}
if (list.size() > 0) {
endDict.put(e, list);
}
i++;
}
}
CombinationRepetition(endSet.toArray(new Long[0]), endSet.size(), 2);

for (Map<Long, Long> combination : combinations) {
fishSet.clear();
for (Map.Entry<Long, Long> entry : combination.entrySet()) {
fishSet.addAll(endDict.get(entry.getKey()));
fishSet.addAll(endDict.get(entry.getValue()));
}
if (fishSet.size() > ans) ans = fishSet.size();
}

System.out.println(ans);
}

static void CombinationRepetitionUtil(int chosen[], Long arr[], int index, int r, int start, int end) {
if (index == r) {
combinations.add(Collections.singletonMap(arr[chosen[0]], arr[chosen[1]]));
return;
}
for (int i = start; i <= end; i++) {
chosen[index] = i;
CombinationRepetitionUtil(chosen, arr, index + 1, r, i, end);
}
}

static void CombinationRepetition(Long[] arr, int n, int r) {
int chosen[] = new int[r + 1];
CombinationRepetitionUtil(chosen, arr, 0, r, 0, n - 1);
}
}


PYTHON

import collections
import itertools

n = int(input())

l = [int(x) for x in input().split(' ')]

end_set = set()
interval = []
end_dict = collections.defaultdict(list)
i =0
fish_set = set()
maxf = 0

for x in input().split(' '):
end_set.add(int(x)+l[i])
interval.append((int(x), int(x)+l[i]))
i += 1


for e in end_set:
for i, r in enumerate(interval):
if r[0] <= e <= r[1]:
end_dict[e].append(i)

x = itertools.combinations_with_replacement(end_set, 2)
for t in itertools.combinations_with_replacement(end_set, 2):
fish_set.clear()
fish_set.update(end_dict[t[0]])
fish_set.update(end_dict[t[1]])
if len(fish_set) > maxf:
maxf = len(fish_set)

print(maxf)