ProposalOptimization
SRM 790 · 2020-09-09 · by misof
Problem Statement
The time limit for this problem is 4 seconds.
Bob has been dating Alice for a long time now and feels this is the right time to propose her. The city where they live is represented as a grid of size R x C. Bob lives in top-left cell (0, 0), while Alice lives in the bottom-right cell (R-1, C-1). All the other cells in the grid are owned by various florists.
Bob is planning a surprise visit to her place and greeting her with a bouquet of flowers. He is going to walk from his home to Alice's home along one of the shortest paths. I.e., in each step he will either move one row down or one column to the right.
The florist in cell (i, j) has exactly roses[i*C+j] roses and tulips[i*C+j] tulips. The florist is only willing to sell all the flowers together, for a combined price of costs[i*C+j]. Bob is going to purchase all the flowers from all florists he encounters on his path.
Bob's bouquet will be formed by all the flowers he bought along the way. He knows that Alice loves roses much more than she likes tulips, so he would like to maximize the ratio of roses to tulips in the bouquet. Bob also knows that Alice does not like wasting money, so he would like to give her a bouquet with a total cost at most K.
Help Bob maximize his chances with Alice: Compute and return the largest possible ratio between the number of roses and the number of tulips in a bouquet that is cheap enough. If he cannot give Alice any bouquet that would cost K or less, return -1 instead.
Notes
- Your answer will be accepted if it has an absolute or a relative error at most 1e-9.
- While the actual city is a 2D grid, the arrays roses, tulips and costs that describe it are 1D arrays. You may note that the order of elements in these arrays corresponds to listing all the cells in the city in row major order.
Constraints
- R and C will be positive.
- R*C will be between 4 and 300, inclusive.
- K will be between 1 and 10^9, inclusive.
- roses, tulips and costs will each have R*C elements.
- The first and the last element of roses, tulips and costs will be 0.
- Each other element of roses, tulips and costs will be between 1 and 10^6, inclusive.
2
2
100
{0, 2, 3, 0}
{0, 3, 5, 0}
{0, 70, 80, 0}
Returns: 0.6666666666666667
Bob has two possible paths: He can go right, purchase 2 roses and 3 tulips for 70, and then go down to Alice's house. He can go down, purchase 3 roses and 5 tulips for 80, and then go right to Alice's house. In the first option Bob will give Alice a bouquet in which the ratio of roses to tulips is 2/3 = 0.66666. In the second option Bob will give Alice a bouquet in which the ratio of roses to tulips is 3/5 = 0.6. The first option is better.
2
2
100
{0, 2, 3, 0}
{0, 3, 5, 0}
{0, 170, 100, 0}
Returns: 0.6
The first bouquet is now too expensive. Bob has to go with the second option.
3
3
98
{0, 1, 1, 1, 1, 1, 1, 1, 0}
{0, 1, 1, 1, 1, 1, 1, 1, 0}
{0, 33, 33, 33, 33, 33, 33, 33, 0}
Returns: -1.0
All possible ways produce bouquets that cost 99, so all possible bouquets are too expensive.
5
9
622
{0, 2, 12, 1, 6, 10, 10, 24, 3, 1, 7, 4, 4, 1, 37, 4, 6, 8, 2, 20, 5, 20, 6, 7, 22, 3, 2, 8, 31, 18, 5, 28, 11, 1, 34, 1, 4, 2, 6, 1, 6, 9, 5, 7, 0}
{0, 4, 37, 22, 3, 14, 10, 6, 5, 6, 5, 17, 4, 7, 12, 3, 1, 3, 3, 1, 5, 1, 11, 37, 6, 24, 6, 3, 21, 1, 2, 27, 7, 1, 8, 1, 8, 1, 26, 20, 6, 6, 6, 7, 0}
{0, 19, 70, 79, 18, 43, 49, 65, 16, 38, 61, 69, 43, 12, 62, 11, 44, 35, 7, 62, 40, 88, 60, 57, 65, 38, 46, 18, 69, 87, 28, 80, 47, 5, 64, 1, 15, 3, 86, 41, 86, 21, 56, 28, 0}
Returns: 2.161290322580645
3
3
100
{0, 10, 1000, 222, 1, 10, 223, 224, 0}
{0, 1, 2000, 333, 1000000, 1, 334, 332, 0}
{0, 1, 1, 33, 1, 1, 33, 33, 0}
Returns: 0.6696696696696696
2
3
15
{0, 1, 3, 1, 1, 0}
{0, 1, 2, 6, 1, 0}
{0, 1, 18, 9, 1, 0}
Returns: 1.0
Bob has three possible paths: He can go right, right, down. On this path, he would get 4 roses and 3 tulips for cost 19 but his budget is only 15 so he cannot take this path. He can go right, down, right. On this path, he would get 2 roses and 2 tulips for cost 2. He can go down, right, right. On this path, he would get 2 roses and 7 tulips for cost 10. The last two options are only feasible and while he gets 2 roses in both the paths, it's better to go right, down, right since the number of tulips acquired is lesser so, better the ratio. Hence, the answer is 2/2 = 1.0 .
Submissions are judged against all 85 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ProposalOptimization with a public method double bestPath(int R, int C, int K, vector<int> roses, vector<int> tulips, vector<int> costs) · 85 test cases · 2 s / 256 MB per case