*As soon as you read a hint that you had not thought about yet, go back to solving the problem.*

Hint 1

Sort all the fish by their lengths. Let's assign each combination of gems to the largest fish that can have it. For each fish, we have to count the number of combinations assigned to it.

Hint 2

Fish i is of type F[i] if the gem initially swallowed by i is F[i]. Observe that the number of combinations assigned to a fish will be zero if it is not the largest fish of its type.

Hint 3

A combination assigned to the fish i cannot have any gems of type j if there is a fish of type F[j] whose length is larger than L[i]*2. What about other fishes which are larger than L[i] but not larger than L[i]*2?

Hint 4

Suppose a combination assigned to fish i has a gem of type j such that the largest fish of type F[j] is smaller than L[i]*2 but larger than L[i]. Let's call that fish k. Fish k can eat all the fishes i can eat, but it cannot eat i.

Hint 5

The number of fish of type F[i] in that combination has to be larger than the maximum number of fish of type F[i] k can eat, which also has to be the maximum number of fish of type F[i] i can eat. So, we need to find the largest k >= i such that the number of fish of type F[i] that k can eat is equal to the number of fish of type F[i] that i can eat. Now there are two possibilities for a combination assigned to fish i :

Read more… (355 words)