The Way Through The Forest

USACO 2018 Open Talent Show In Short Given N objects with value Vi and weight Wi, a collection of elements is said to have total value-to-weight ratio as (the sum of their value) divided by (the sum of their weight). Find the best possible value-to-weight ratio of these X objects, given the restraint that the collection must have total weight at least W. Return that ratio multiplied by 1000 and floored. Analysis It would be very difficult to calculate this optimal ratio - we'd have to either try all possible collections - O(2^n), where n is at most 250, about 10 to the power of 75 calculations, OR use a greedy heuristic - get the objects with the best ratio until it satisfies the weight limit. Neither of those are too to our liking, so how about searching for it? The search space is linear and not infinite - it asks for the ratio to the closest thousandths. The search space is sorted as well - if ratio X is achievable, then ratio Y < X is also achievable, if...

LA 2678: Sub-sequence Problem Statement Analysis     We are asked to find the length of the shortest sub-sequence such that the sum of all elements in it is at least S. In other words, given the array A_0 ~ A_N-1, find the smallest possible X such that there exists a i which satisfies ∑A_j ≥ S, where j = i ~ i + X - 1.     For example, when A = [1, 2, 3, 4, 5], N = 5, and S = 11, the smallest possible X is 3 and the i is 2. This is sample test case 2. Algorithm: O(N^3)     The most naive method is to permute through all possible sub-sequence beginnings and ends. There are N beginnings and N/2 ends on average, making just permuting through possible sub-sequences O(N^2). Multiplying by the cost of finding the sum of that sub-sequence, O(N), gives us a total O(N^3) algorithm. Clearly that will not work! Algorithm: O(N^2)     However, we can use a prefix sum to improve on the cost of finding the sum of that sub-sequence....