Description
Prof. Blocki plans to help Theory students by donating some of his books. He decides to put those books in the LWSN commons, and arranges them in a row. You notice the books and immediately jump towards them with your backpack. You are very excited to see all the books, however, unfortunately you also see Jane standing close to you with her backpack, equally excited to grab those books. There is no other person around the books area, so you both come up with few rules to pick the books. Before we discuss the rules, here are few things to keep in mind:
1. There are “n” number of books and you can assume that $n$ is even.
2. Each book “i” has a value “v_i” and a space “s_i” (positive integer) associated with it.
3. The total space of your backpack is “S” (positive integer). Unfortunately for you, Jane brought a “magical” Austen backpack, which doesn’t have any space constraint.
4. Jane aced 381 last semester, so you can assume that she will play optimally.
Here are the rules for picking the books:
1. The objective for both of you is to maximize the value of books you pick, given the ones you choose fit in your backpack.
2. Both of you will be alternating turns to choose to pick a book.
3. By some luck, you get to start first.
4. A book can only be picked from either ends of the row.
5. In the situation where you lack sufficient space to fit the book at either end into your backpack, the remaining books are given to Jane.
For this problem,
A. Describe an efficient algorithm that determines the maximum total value of the books that you can achieve with optimal play. Analyze the time and space complexity of your algorithm (You may assume that $S leq n^2$). \
Hint 1: Notice that this is a zero-sum game since Jane gets to keep every book that you don’t take.
Hint 2: It may be helpful to review the “cakes in a line” problem from PSO. Can you find a way to extend the core ideas by adding more sub-problems? How will you incorporate information about remaining space?
B. Consider a modification of the problem such that the players are allowed to skip their turn as long as we never have two skips in a row (i.e., if you skip a turn then Jane must select a book and vice versa). If you must select a book but lack space then all remaining books are given to Jane. How would you modify your algorithm to accommodate this? Analyze the time and space complexity of your newly modified algorithm.
