PROBLEM LINK:
Author: Sidhant Bansal
Tester: tncks0121
DIFFICULTY:
Simple
PREREQUISITES:
Interactive, Dynamic Programming
PROBLEM:
There is a weights array W and a profit array P, both of length n \leq 100. The weights are also \leq 100. Both of these arrays are hidden. You can ask queries of the form i, j, and receive a result dp[i][j], where dp[i][j] is the maximum sum of profits of some subset of the first i elements with total weight \leq j.
The task is to recover arrays W and P using \leq 1500 queries.
EXPLANATION:
Say we have found the first i - 1 elements of W and P. Now, we need to find P_i and W_i.
First, query dp[i][10^4], say this value is T. Here, j = 10^4 is large enough to choose all the elements. Therefore T = \displaystyle \sum_{r=1}^{i} P_r. Since we already know P_1, P_2, \ldots P_{i-1}, we can directly find P_i using the value of T.
Now, let t be the minimum value of j for which dp[i][j] = T. Clearly, as dp[i][.] is monotonous, this value t can be found by binary search in about \log(100 n) queries.
Also, note that T is achieved only if we can select all of the first i elements, so t must be \displaystyle \sum_{r=1}^{i} W_r. Since we already know W_1, W_2, \ldots W_{i-1}, the value of t can be used to recover W_i.
The total number of queries asked \approx n \log(100 n) \leq 1500 .
AUTHOR’S and TESTER’S codes:
The author’s code can be found here
The tester’s code can be found here