INVSACK - Editorial

PROBLEM LINK:

Practice

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

1 Like