Nilkhet

The value of $s$ will be in range $(0,100)$. We will do a binary search on the value of $s$.

Binary search works because for a particular value of $s$, if we have $loss>0$ then for all other $s'<s$, $loss>0$ will also hold.

Now, how do we calculate the loss for a particular value of $s$?

The judge solution uses a Minimum-cost-maximum-flow network.

The flow of the network represents the number of days successfully served, and the cost represents the total loss.

As we need to serve every day, the flow in our network should be equal to the number of days and the cost should be no more than $0$.

The network:

Let $0$ be the source of the network and $n+1$ be the sink.

Now for each day $i$,

• If this is the first time book of type $t_i$ occurred, We add an edge from source to $i$ with flow = $1$ and cost = $p_i$ and another edge from $i$ to sink with flow = $1$ and cost = $-(Rent+r_i)$. Here $Rent = p_i*s/100$. This means we must buy the book as we didn't buy that before and as we bought it we will sell it sometime.

• If this is not the first time book of type $t_i$ occurred, let’s say on the $j$'th day book $t_i$ occurred last time, We add an edge from source to $j$ with flow = $1$ and cost = $p_i-Rent$, another edge from $j$ to $i$ with flow = $1$ and cost $p_i-r_i$ and another edge from $i$ to sink with flow = $1$ and cost = $Rent - p_i$. This represents the situation that we decided to sell the book the last time we had and buy the book again.

Now for each $i$ in range $[1,n-1]$, we add an edge from node $i$ to node $i+1$ with flow = $m-1$ and cost = $0$. This handles storing previously bought books on the shelves. The flow value is $m-1$ here, because it can be shown there exist at least one optimal strategy where you buy no more than one book on any of the nights.