Algorithms and Data Structures


When working with collections of elements, like a list of strings, or a list of tuples, it becomes computationally very expensive to search for elements in the collection or answer queries like “Is item X present in our collection?”. Yet, comparing numbers is very fast, and our computers are specialized in comparing numbers very efficiently (unlike strings, or tuples). So, if we can map the data at hand to a numeric value, it would make some operations like finding it, or checking if it’s present in the collection quicker.
The technique of mapping data of arbitrary size to fixed-size data is called hashing. The resulting number (hash) serves as a unique identifier for the original data. We are usually given a hash function that can map the initial data to fixed-sized data (like a number).
Python, for instance, has a built-in hash function that can map any immutable object to a number, which is usually in the range . Note that it can only map immutable objects. So, trying to hash a list or a dictionary (which are mutable and can be changed by adding or removing elements) would result in an error:
print(hash(123))               # 123
print(hash('Anna'))            # 2573300035916889866
print(hash('Bob'))             # -2781086332262035333
print(hash((2, 'Simon')))      # -6551767300073204554
print(hash([1, 2]))            # TypeError: unhashable type: 'list'

Challenge: Hash a pair of integers

Let’s implement a custom hash function h. It will receive a pair of integers and should return the hashed value. The function h is defined as:
This would ensure that the hash value is always in the range [0; 5077).


The only line of the input contains two numbers a and b ( ≤ a, b ≤ ).


The program should print the hash of the pair (a, b).


4 5
23452 5432


Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue