This article contains a short description of the problem “Book Scanning” proposed for the Google Hash Code Online Qualification process on Feb 20th, 2020. The full description of this problem is available in the archive section of the Google Hash Code website.
Book Scanning: task description
Google provided a list of L libraries and B books. The task is to plan which books to scan from which library to maximize the total score of all scanned books, taking into account that each library needs to be signed up before it can ship books.
Each book B[k] has a certain score S[k], where S[k] belongs to the range [0, 1’000]. The maximum size of list of books is 100’000, i.e., the index k belongs to the range [0, 99’999].
Each library L[k] has three parameters:
- the set of books in the library (a “list” of the indexes of the books).
- the time – measured as number of days – that it takes to sign the library up for scanning. The maximum time required to sign up is 100’000 days.
- the maximum number of books that can be scanned each day, after the library has signed up
The maximum number of libraries is 100’000, i.e., the index k belongs to the range [0, 99’999].
The maximum time of the simulation is D – 1. All books scanned after this time do not provide any score. All libraries signed up after this time are ignored. The value of the parameter D belongs to the range [1; 100’000].
Implicitly, both books and libraries are identified by a numerical index.
How the score is calculated?
The score is the sum of the scores of all books that are scanned withing D days. Each book can provide its score only once.
A solution can contain multiple instances of the same book even if they do not increase its score.
A solution can contain books being scanned after D-1 (they will be ignored).
A solution can contain libraries being signed up after D-1 (they will be ignored).
Algorithm description and code
Are you interested to check how I solved this problem? The description of the algorithm used in the Online Qualification challenge will be published in a new article soon.