# Google Hash Code 2020: How we Took 98.5% of the Best Score

### How we came in 53rd in Ukraine and 530th in the world

(Photo by Mitchell Luo on Unsplash)
Since we didn』t get a chance to participate in this year』s Google Hash Code, we decided to try our best in the extended round. Here』s the result: 530th in the world ranking and 53rd in Ukraine.

## What is Google Hash Code?

Google has been organizing a competition for programmers since 2016 called Hash Code. Teams of two to four people can participate in the competition, where they have to solve an optimization problem. Every year it attracts thousands of people from all over the world.

It has two rounds: main and extended. The main round continues only for four hours, while the extended one can go on for up to two weeks. Of course, the extended round does not count on the scoreboard, but it』s still a good chance to check your knowledge and skills.

As we mentioned, we didn』t have a chance to participate in the main round, but maybe our solution will be interesting for you. Or perhaps it will push you to try to implement your own solution.

This year the participants were given the problem of scanning books from different libraries.

You have to choose books with the biggest score, from libraries which first have to sign up. This must be done within the given deadline. The same books can be available in more than one library, but you can get a score for each book only once. Furthermore, each library can provide different numbers of books per day.

This is the initial data that we have:
• Only one library can be signing up at one moment.
• Only a signed up library can provide you with books for scanning.
• You have a total deadline.
• Your goal is to get the highest possible score of all provided books.

It may sound a little complicated, at least in our words! Hopefully, this image will help you to get to the bottom of the situation:
If you haven』t solved this issue yet, we suggest you postpone reading the rest of this piece and try to do it on your own first.

## Our Solution

Analyzing the task description, we came to the conclusion that there』s basically only one issue that we needed to solve: Each time the sign-up process is empty, we have to find the most suitable library that we will pass to sign up.

In order to find this library we decided to evaluate them by the following criteria: two positive — the score of library books and the number of books we can scan per day; and one negative — how many days are required to sign up for a library.

The first algorithm that we stopped at is pretty straightforward. It basically calculates how much score the library will produce if we start the sign up at this moment.

• Сalculate how many days will remain after the sign up is finished.
• Multiply by the number of books scanned per day.
• Sort books by their score and get top books.
• The cumulative score of scanned books is the library value.
After that, we just select the library with the highest value. If there』s more than one library with the max value, we select the one with the lowest sign-up duration.

Here are the results:
This solution was pretty good but still far from perfect. So we kept trying.

After further brainstorming, we figured out that the negative criterion (days count to sign up a library) is not represented properly in our equation.

Among many ways to introduce this criterion in our formula (define some coefficients for criteria, etc.), we selected the following one — divide the calculated value by the number of days to sign up. This way we get the ratio between the good input and the bad one.

The results that we received were pretty astonishing and they turned out to be just 1.5% less than the best results at that moment.

Here』s our source code (do not judge us, we did it in a hurry!):

## What We Learned From This Experience

• Think algorithmically
• Find the root of the problem — even if the task looks complicated at first glance, the real issue may be pretty easy.
• Consider all variables of the equation.
• Don』t stop improving results — if something works, it doesn』t mean it can』t work better.
• Use TypeScript instead of JavaScript. We spent a lot of time debugging JavaScript issues that could have been prevented by using TypeScript.