TechGig CG 2018: Bob the Bear

Solution to semi final problem 1 Bob the bear

Problem Statement

Bob is a grizzy bear and just like all grizzlies he loves hunting salmon fish. Bob has a 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 = 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 a non-positive x-coordinates.
You are given the information about N salmons in the 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 (origin). 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 the time Bob can catch all the salmons whose any part of body(between head and tail, both inclusive) is at origin.
Bob wants to catch salmons no more than twice. What is the maximum number of salmons Bob can catch?

Input format.

1st line - N- number of salmon
2nd line - contains N separated integers representing the contents of array len.
3rd line - contains N separated integers representing the contents of array time.

Output format

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

Example

Input

5
2 4 4 2 4
1 4 1 6 4

Output

5

Explanation

at time=1 and time=6 bob can get 5 salmons

Solution

Approach : Well, I would suggest going for Dynamic programming. You can easily check that “the best time” to go catch salmon is time when some salmon tail lies (the point where tail lies). In our example it would be 3,5 and 8. Then what we want to do is calculate the best possible scenario of taking 2 from it. You can keep taken times in set to avoid duplicates of salmon and after you have finished your 2-steps just check its size and the biggest one is the solution.

Implementation

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

#print("end_set",end_set)
#print("interval",interval)

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

#print("end_dict",end_dict)

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)