Contest Duration: - (local time) (100 minutes) Back to Home
Official

C - Manga Editorial by en_translator

Observation on the operations

The problem statement defines the operation by buying one book instead of two, but we can assume that we can defer determining which book to buy when selling.
First, we can sell all but one books with the same volume. Also, Takahashi initially has $$N$$ books, which decreases by the operations. Therefore, he can never read a book of Volume $$N$$ or greater, so he can sell such a book too.
We can assume that he buys a book with the minimum Volume that he doesn’t have. Also, it is not good to sell a book of the volume he is going to read and buy it again. Therefore, it is optimal to perform as follows:

1. Sell the books with duplicating volumes or of Volumes $$N$$ or greater
2. If he can buy a book, sell a book with the minimum volume.
3. If he cannot buy a book, sell the book that he will never read. The first candidate to sell is the one with the largest Volume. However, if he would read the maximum volume if he quits performing the operations at this point, quit the operations.

Simulation and optimization

Let $$vol_i$$ be the array expressing whether he currently has a book of Volume $$i$$. Since the maximum number of volumes that he can read is $$N$$, $$N$$ is a sufficient length of the array. (Alternatively, you may similarly manage the books with Volume greater than $$N$$ using a balanced binary tree.)
Now that we can determine the minimum Volume that he doesn’t have and the maximum Volume that he has, we can find the answer by simulating the strategy above by managing the number of books sold so far (and not used for buying a new one), but if we spend $$\mathrm{O}(N)$$ time each to find a book with say the minimum Volume, it costs a total of $$\mathrm{O}(N^2)$$ time, which does not fit in the execution time limit of this problem.
Let $$L$$ be the minimum Volume of book that he doesn’t have, and $$R$$ be the maximum that he has. Selling a book decreases $$R$$ and buying increases $$L$$. When finding a book with the minimum volume that he has, we can inspect $$L, L+1,L+2,\ldots$$ instead of $$1,2,\ldots$$. This way, the total number of steps equals the sum of the number of operations and the number of times that $$L$$ increased. Same applies for $$R$$, so the total time complexity is $$\mathrm{O}(N)$$, which is fast enough.

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {

int N;
cin>>N;

vector<bool> vol(N+2,false);
vector<int> a(N);

int sold = 0;
for(int i=0;i<N;i++){
cin>>a[i];
if(a[i]>=vol.size())sold++;
else if(vol[a[i]])sold++;
else vol[a[i]] = true;
}

int L = 1;
int R = N+1;
while(true){
while(vol[L])L++;
while(R!=0&&!vol[R])R--;
if(sold>=2){
sold-=2;
vol[L] = true;
}
else{
if(L>=R)break;
vol[R] = false;
sold++;
}
}

cout<<L-1<<endl;

return 0;
}


posted:
last update: