Skip to content

Our solution for the 2020 hashcode qualification round problem with libraries and books

Notifications You must be signed in to change notification settings

Thanasis1101/Hashcode-2020-solution-Qualification-round

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Hashcode 2020 solution (Qualification round)

Our solution for the 2020 Google Hashcode qualification round problem with libraries and books.

Hashcode Logo

Results

File Score
a_example (input | output) 21
b_read_on (input | output) 5,822,900
c_incunabula (input | output) 5,645,747
d_tough_choices (input | output) 4,812,730
e_so_many_books (input | output) 5,019,670
f_libraries_of_the_world (input | output) 5,240,161
Total 26,541,229

The problem

You can find the pdf with the problem here.

Hashcode 2020 problem

Our solution

The code for the solution is in main.py. Our approach was a greedy algorithm.

The solution follows these steps:

  1. Read the input

  2. Calculate a heuristic score for each library with this formula:

    where library_books_score is calculated like this:

    1. Calculate available days for this library:

    1. Count how many books can be scanned in these days:

    1. Get the top k books according to their score and sum their scores. This is the library_books_score.
  3. Sort libraries according to their score

  4. For every library in sorted order:

    1. Count how many books from this library (k) can be scanned, like in steps 2i and 2ii, but now take into account the number of signup days from the previous libraries. So if the previous libraries have taken d total days for the signup, then the formula from the step 2i becomes:

    1. From the books of this library, except the books that have already been scanned from the previous libraries, get the top k books according to their score and scan them.
  5. Create the output

An improvement

You can find an improvement of this solution (total score: 26,922,702) in this repository:
https://github.com/tipavlos/Hashcode-2020-solution-Qualification-round

Our team