hash


Google Hash Code 2021 – Practice Problem 1

Even more pizza

Hash Code 2021, Practice Round - Problem (1822 downloads)

Hash Code 2021, Online Qualification Round – Problem (265 downloads)

Introduction

Isn’t it fun to share pizza with friends? But, sometimes you just don’t have enough time to choose what pizza to order. Wouldn’t it be nice if someone else chose for you?

In an imaginary world…

Problem description

Task

Help the imaginary pizzeria choose the pizzas to deliver to Hash Code teams. And since we want everyone to enjoy their food, let’s try to deliver to each team, as many different ingredients as we can.

Pizza

Expecting many hungry customers, the pizzeria has already prepared some pizzas with different ingredients. Each pizza can be delivered to at most one team. There can be multiple pizzas with the exact same set of ingredients.

For example , there are 5 pizzas available in the pizzeria:

Pizza 0: onion, pepper, olive
Pizza 1: mushroom, tomato, basil
Pizza 2: chicken, mushroom, pepper
Pizza 3: tomato, mushroom, basil
Pizza 4: chicken, basil

Note that Pizzas 1 and 3 have the same ingredients, even though they are mentioned in different order.

Teams

Teams of 2, 3, or 4 people all ordered pizzas. Each team ordered one pizza per team member, but did not specify what ingredients to put on the pizzas. The pizzeria might not deliver to a team (no pizzas are sent to that team). However, if the order is delivered, exactly one pizza should be available per person. For example, it is an error to send 3 pizzas to a 4-person team.

Goal

Given the description of the pizzas available, and the number of teams of 2, 3, or 4 people that have ordered, decide which pizzas to send to each of the teams. The goal is to maximize, per team, the number of different ingredients used in all their pizzas.

For example , if we deliver to a 3-person team Pizzas 0, 2 and 3, there will be 7 different ingredients (9 ingredients in total, but pepper and mushroom occur twice):

  • Pizza 0
    • onion
    • pepper
    • olive
  • Pizza 2:
    • chicken
    • mushroom
    • pepper (is already on Pizza 0)
  • Pizza 3:
    • tomato
    • mushroom (is already on Pizza 2)
    • basil

Input data set

The input data is provided as a data set file – a plain text file containing exclusively ASCII characters with lines terminated with a single ‘\n’ character (UNIX- style line endings).

File format

The first line of the input file contains the following integer numbers separated by single spaces:

  • M ( 1 ≤ M ≤ 100,000 ) – the number of pizzas available in the pizzeria
  • T2 ( 0 ≤ T2 ≤ 50,000 ) – the number of 2-person teams
  • T3 ( 0 ≤ T3 ≤ 50,000 ) – the number of 3-person teams
  • T4 ( 0 ≤ T4 ≤ 50,000 ) – the number of 4-person teams

The next M lines describe the pizzas available. Each line contains (space separated):

  • an integer I ( 1 ≤ I ≤ 10,000 ) – the number of ingredients,
  • followed by the list of I ingredients – Each ingredient consists of lowercase ASCII letters and dash (-) characters, and its length can be between 1 and 20 characters in total. Each ingredient in a pizza is different, but the same ingredient can appear on different pizzas.

Example

Input file
5 1 2 1
3 onion pepper olive
3 mushroom tomato basil
3 chicken mushroom pepper
3 tomato mushroom basil
2 chicken basil
Description
5 pizzas, 1 team of two, 2 teams of three, and 1 team of four
Pizza 0 has the given 3 ingredients
Pizza 1 has the given 3 ingredients
Pizza 2 has the given 3 ingredients
Pizza 3 has the given 3 ingredients
Pizza 2 has the given 2 ingredients

Submissions

File format

The first line of the submission file contains a number D ( 1 ≤ D ≤ T2 + T3 + T4 ), representing the number of pizza deliveries.

The following D lines contain descriptions of each delivery. Each line contains the following integer numbers separated by single spaces:

  • L ( 2 ≤ L ≤ 4 ) – the number of people in the team
  • followed by the list of pizzas, P1 … PL – the space separated indexes of the pizzas delivered to that team

Even though it’s nice to deliver pizzas to all teams, it is allowed to make fewer deliveries than the number of teams. However, making more deliveries than the number of teams is an error. It is also an error to make more deliveries to 2, 3 or 4-person teams than the corresponding number
of teams provided in the input file: the number of lines with L=N, should not be greater than TN.

Example

Submission file
2
2 1 4
3 0 2 3
Description
Pizzas are delivered to 2 teams
A 2-person team will receive Pizza 1 and Pizza 4
A 3-person team will receive Pizza 0, Pizza 2 and Pizza 3

Validation

In order for the submission to be accepted:

  • each pizza must be part of at most one order,
  • for all N-person teams, either nobody or everybody receives a pizza,
  • there are TN or less deliveries to teams of N people.

Scoring

For each delivery, the delivery score is the square of the total number of different ingredients of all the pizzas in the delivery. The total score is the sum of the scores for all deliveries.

For example , with the example input file and the example submission file above, there are

  • 4 ingredients delivered to the two-person team (mushroom, tomato, basil, chicken). The score for that team is 42 = 16
  • 7 ingredients delivered to the tree-person team. The score for that team is 72 = 49.
  • (The score is 0 for the two teams that didn’t have their order delivered)

The total score is 16 + 49 = 65 .

Note that there are multiple data sets representing separate instances of the problem. The final score for your team will be the sum of your best scores for the individual data sets.

Past editions

— From https://codingcompetitions.withgoogle.com/hashcode/archive

Hash Code started in 2014 with just 200 participants from France. In 2020, more than 100,000 participants from across Europe, the Middle East and Africa took part in the competition. You can take a look at the problems and winning teams from past editions of Hash Code below.

Past problem statements

Traffic Signaling

Hash Code 2021, Online Qualification Round
Hash Code 2021, Online Qualification Round – Problem (265 downloads)
Given the description of a city plan and planned paths for all cars in that city, optimize the schedule of traffic lights to minimize the total amount of time spent in traffic, and help as many cars as possible reach their destination before a given deadline.

Assembling smartphones

Hash Code 2020, Final Round
Hash Code 2020, Final Round - Problem (562 downloads)
In this problem statement, we will explore the idea of operating an automated assembly line for smart phones.
Building a smart phone is a complex process that involves assembling numerous components, including the screen, multiple cameras, microphones, speakers, a processing unit, and a storage unit.
In order to automate the building of a smart phone, we will be using robotic arms that can move around the assembly workspace performing all necessary tasks.

Book scanning

Hash Code 2020, Online Qualification Round
Hash Code 2020, Online Qualification Round - Problem (554 downloads)
Books allow us to discover fantasy worlds and better understand the world we live in. They enable us to learn about everything from photography to compilers… and of course a good book is a great way to relax!
Google Books is a project that embraces the value books bring to our daily lives. It aspires to bring the world’s books online and make them accessible to everyone. In the last 15 years, Google Books has collected digital copies of 40 million books in more than 400 languages , partly by scanning books from libraries and publishers all around the world.
In this competition problem, we will explore the challenges of setting up a scanning process for millions of books stored in libraries around the world and having them scanned at a scanning facility.

Compiling Google

Hash Code 2019, Final Round
Hash Code 2019, Final Round - Problem (464 downloads)
Google has a large codebase, containing billions of lines of code across millions of source files. From these source files, many more compiled files are produced, and some compiled files are then used to produce further compiled files, and so on.
Given then huge number of files, compiling them on a single server would take a long time. To speed it up, Google distributes the compilation steps across multiple servers.
In this problem, we will explore how to effectively use multiple compilation servers to optimize compilation time.

Photo slideshow

Hash Code 2019, Online Qualification Round
Hash Code 2019, Online Qualification Round - Problem (439 downloads)
As the saying goes, “a picture is worth a thousand words.” We agree – photos are an important part of contemporary digital and cultural life. Approximately 2.5 billion people around the world carry a camera – in the form of a smart phone – in their pocket every day. We tend to make good use of it, too, taking more photos than ever (back in 2017, Google Photos announced it was backing up more than 1.2 billion photos and videos per day).
The rise of digital photography creates an interesting challenge: what should we do with all of these photos? In this competition problem, we will explore the idea of composing a slideshow out of a photo collection.

City Plan

Hash Code 2018, Final Round
Hash Code 2018, Final Round - Problem (461 downloads)
The population of the world is growing and becoming increasingly concentrated in cities. According to the World Bank, global urbanization (the percentage of the world’s population that lives in cities) crossed 50% in 2008 and reached 54% in 2016.
The growth of urban areas creates interesting architectural challenges. How can city planners make efficient use of urban space? How should residential needs be balanced with access to public utilities, such as schools and parks?

Self-driving rides

Hash Code 2018, Online Qualification Round
Hash Code 2018, Online Qualification Round - Problem (432 downloads)
Millions of people commute by car every day; for example, to school or to their workplace.
Self-driving vehicles are an exciting development for transportation. They aim to make traveling by car safer and more available while also saving commuters time.
In this competition problem, we’ll be looking at how a fleet of self-driving vehicles can efficiently get commuters to their destinations in a simulated city.

Router placement

Hash Code 2017, Final Round
Hash Code 2017, Final Round - Problem (1399 downloads)
Who doesn’t love wireless Internet? Millions of people rely on it for productivity and fun in countless cafes, railway stations and public areas of all sorts. For many institutions, ensuring wireless Internet access is now almost as important a feature of building facilities as the access to water and electricity. Typically, buildings are connected to the Internet using a fiber backbone. In order to provide wireless Internet access, wireless routers are placed around the building and connected using fiber cables to the backbone. The larger and more complex the building, the harder it is to pick router locations and decide how to lay down the connecting cables.

Streaming videos

Hash Code 2017, Online Qualification Round
Hash Code 2017, Online Qualification Round - Problem (1379 downloads)
Have you ever wondered what happens behind the scenes when you watch a YouTube video? As more and more people watch online videos (and as the size of these videos increases), it is critical that video-serving infrastructure is optimized to handle requests reliably and quickly. This typically involves putting in place cache servers, which store copies of popular videos. When a user request for a particular video arrives, it can be handled by a cache server close to the user, rather than by a remote data center thousands of kilometers away. Given a description of cache servers, network endpoints and videos, along with predicted requests for individual videos, decide which videos to put in which cache server in order to minimize the average waiting time for all requests.

Schedule Satellite Operations

Hash Code 2016, Final Round
Hash Code 2016, Final Round - Problem (1046 downloads) A satellite equipped with a high-resolution camera can be an excellent source of geo imagery. While harder to deploy than a plane or a Street View car, a satellite — once launched — provides a continuous stream of fresh data. Terra Bella is a division within Google that deploys and manages high-resolution imaging satellites in order to capture rapidly-updated imagery and analyze them for commercial customers. With a growing constellation of satellites and a constant need for fresh imagery, distributing the work between the satellites is a major challenge. Given a set of imaging satellites and a list of image collections ordered by customers, schedule satellite operations so that the total value of delivered image collections is as high as possible.

Optimize Drone Deliveries

Hash Code 2016, Online Qualification Round
Hash Code 2016, Online Qualification Round - Problem (1164 downloads)
The Internet has profoundly changed the way we buy things, but the online shopping of today is likely not the end of that change; after each purchase we still need to wait multiple days for physical goods to be carried to our doorstep. Given a fleet of drones, a list of customer orders and availability of the individual products in warehouses, schedule the drone operations so that the orders are completed as soon as possible.

Route Loon Balloons

Hash Code 2015, Final Round
Hash Code 2015, Final Round - Problem (878 downloads)
Project Loon aims to bring universal Internet access using a fleet of high altitude balloons equipped with LTE transmitters. Circulating around the world, Loon balloons deliver Internet access in areas that lack conventional means of Internet connectivity. Given the wind data at different altitudes, plan altitude adjustments for a fleet of balloons to provide Internet coverage to select locations.

Optimize a Data Center

Hash Code 2015, Online Qualification Round
Hash Code 2015, Online Qualification Round - Problem (1181 downloads)
For over ten years, Google has been building data centers of its own design, deploying thousands of machines in locations around the globe. In each of these of locations, batteries of servers are at work around the clock, running services we use every day, from Google Search and YouTube to the Judge System of Hash Code. Given a schema of a data center and a list of available servers, your task is to optimize the layout of the data center to maximize its availability.

Street View Routing

Hash Code 2014, Final Round
Hash Code 2014, Final Round - Problem (1063 downloads)
The Street View imagery available in Google Maps is captured using specialized vehicles called Street View cars. These cars carry multiple cameras capturing pictures as the car moves around a city. Capturing the imagery of a city poses an optimization problem: the fleet of cars is available for a limited amount of time and we want to cover as much of the city streets as possible.


Practice Problem for Google Hash Code 2018

[2021] Click here for Google Hash Code 2021 – Practice Problem

Happy new year people!!

Google released a practice problem for Google Hash Code 2018!

Please do not forget to register!

Practice Problem for Google Hash Code 2018 - Problem Statement (2609 downloads)

Practice Problem for Google Hash Code 2018 - Data Sets (1087 downloads)

Submission deadline: Thursday, Mar 1, 19:00 Cyprus time (18:00 CET)

Pizza

Practice Problem for Hash Code

Introduction

Did you know that at any given time, someone is cutting pizza somewhere around the world? The decision about how to cut the pizza sometimes is easy, but sometimes it’s really hard: you want just the right amount of tomatoes and mushrooms on each slice. If only there was a way to solve this problem using technology…

Problem description

Pizza

The pizza is represented as a rectangular, 2-dimensional grid of R rows and C columns. The cells within the grid are referenced using a pair of 0-based coordinates [r, c] , denoting respectively the row and the column of the cell.

Each cell of the pizza contains either:

  • mushroom, represented in the input file as M ; or
  • tomato, represented in the input file as T

Slice

A slice of pizza is a rectangular section of the pizza delimited by two rows and two columns, without holes.
The slices we want to cut out must contain at least L cells of each ingredient (that is, at least L cells of mushroom and at least L cells of tomato) and at most H cells of any kind in total – surprising as it is, there is such a thing as too much pizza in one slice.

The slices being cut out cannot overlap. The slices being cut do not need to cover the entire pizza.

Goal

The goal is to cut correct slices out of the pizza maximizing the total number of cells in all slices.

Input data set

The input data is provided as a data set file – a plain text file containing exclusively ASCII characters with lines terminated with a single \n character at the end of each line (UNIX- style line endings).

File format

The file consists of:

  • one line containing the following natural numbers separated by single spaces:
    • R (1 ≤ R ≤ 1000) is the number of rows,
    • C (1 ≤ C ≤ 1000) is the number of columns,
    • L (1 ≤ L ≤ 1000) is the minimum number of each ingredient cells in a slice,
    • H (1 ≤ H ≤ 1000) is the maximum total number of cells of a slice
  • R lines describing the rows of the pizza (one after another). Each of these lines contains C
    characters describing the ingredients in the cells of the row (one cell after another). Each character is either M (for mushroom) or T (for tomato).

Example Input File

3 5 1 6
TTTTT
TMMMT
TTTTT

3 rows, 5 columns, min 1 ingredient per slice, max 6 cells per slice

Submissions

File format

The file must consist of:

  • one line containing a single natural number S (0 ≤ S ≤ R × C) , representing the total number of slices to be cut,
  • U lines describing the slices. Each of these lines must contain the following natural numbers
    separated by single spaces:

    • r1 , c1 , r2 , c2 (0 ≤ r1, r2 < R, 0 ≤ c1, c2 < C)  describe a slice of pizza delimited by the rows r1 and r2 and the columns c1 and c2 , including the cells of the delimiting rows and columns. The rows ( r1 and r2 ) can be given in any order. The columns ( c1 and c2 ) can be given in any order too.

Example

3
0 0 2 1
0 2 2 2
0 3 2 4

Example description

3 slices.
First slice between rows (0,2) and columns (0,1).
Second slice between rows (0,2) and columns (2,2).
Third slice between rows (0,2) and columns (3,4).

Slices described in the example submission file marked in green, orange and purple.

Validation

For the solution to be accepted:

  • the format of the file must match the description above,
  • each cell of the pizza must be included in at most one slice,
  • each slice must contain at least L cells of mushroom,
  • each slice must contain at least L cells of tomato,
  • total area of each slice must be at most H

Scoring

The submission gets a score equal to the total number of cells in all slices.

Note that there are multiple data sets representing separate instances of the problem. The final
score for your team is the sum of your best scores on the individual data sets.

Scoring example

The example submission file given above cuts the slices of 6, 3 and 6 cells, earning 6 + 3 + 6 = 15 points.

Past editions

— From https://hashcode.withgoogle.com/past_editions.html

Hash Code started in 2014 with just 200 participants from France. In 2017, more than 26,000 participants from across Europe, the Middle East and Africa took part in the competition. You can take a look at the problems and winning teams from past editions of Hash Code below.

Past problem statements

Router placement

Hash Code 2017, Final Round
Hash Code 2017, Final Round - Problem (1399 downloads)
Who doesn’t love wireless Internet? Millions of people rely on it for productivity and fun in countless cafes, railway stations and public areas of all sorts. For many institutions, ensuring wireless Internet access is now almost as important a feature of building facilities as the access to water and electricity. Typically, buildings are connected to the Internet using a fiber backbone. In order to provide wireless Internet access, wireless routers are placed around the building and connected using fiber cables to the backbone. The larger and more complex the building, the harder it is to pick router locations and decide how to lay down the connecting cables.

Streaming videos

Hash Code 2017, Online Qualification Round
Hash Code 2017, Online Qualification Round - Problem (1379 downloads)
Have you ever wondered what happens behind the scenes when you watch a YouTube video? As more and more people watch online videos (and as the size of these videos increases), it is critical that video-serving infrastructure is optimized to handle requests reliably and quickly. This typically involves putting in place cache servers, which store copies of popular videos. When a user request for a particular video arrives, it can be handled by a cache server close to the user, rather than by a remote data center thousands of kilometers away. Given a description of cache servers, network endpoints and videos, along with predicted requests for individual videos, decide which videos to put in which cache server in order to minimize the average waiting time for all requests.

Schedule Satellite Operations

Hash Code 2016, Final Round
Hash Code 2016, Final Round - Problem (1046 downloads)
A satellite equipped with a high-resolution camera can be an excellent source of geo imagery. While harder to deploy than a plane or a Street View car, a satellite — once launched — provides a continuous stream of fresh data. Terra Bella is a division within Google that deploys and manages high-resolution imaging satellites in order to capture rapidly-updated imagery and analyze them for commercial customers. With a growing constellation of satellites and a constant need for fresh imagery, distributing the work between the satellites is a major challenge. Given a set of imaging satellites and a list of image collections ordered by customers, schedule satellite operations so that the total value of delivered image collections is as high as possible.

Optimize Drone Deliveries

Hash Code 2016, Online Qualification Round
Hash Code 2016, Online Qualification Round - Problem (1164 downloads)
The Internet has profoundly changed the way we buy things, but the online shopping of today is likely not the end of that change; after each purchase we still need to wait multiple days for physical goods to be carried to our doorstep. Given a fleet of drones, a list of customer orders and availability of the individual products in warehouses, schedule the drone operations so that the orders are completed as soon as possible.

Route Loon Balloons

Hash Code 2015, Final Round
Hash Code 2015, Final Round - Problem (878 downloads)
Project Loon aims to bring universal Internet access using a fleet of high altitude balloons equipped with LTE transmitters. Circulating around the world, Loon balloons deliver Internet access in areas that lack conventional means of Internet connectivity. Given the wind data at different altitudes, plan altitude adjustments for a fleet of balloons to provide Internet coverage to select locations.

Optimize a Data Center

Hash Code 2015, Online Qualification Round
Hash Code 2015, Online Qualification Round - Problem (1181 downloads)
For over ten years, Google has been building data centers of its own design, deploying thousands of machines in locations around the globe. In each of these of locations, batteries of servers are at work around the clock, running services we use every day, from Google Search and YouTube to the Judge System of Hash Code. Given a schema of a data center and a list of available servers, your task is to optimize the layout of the data center to maximize its availability.

Street View Routing

Hash Code 2014, Final Round
Hash Code 2014, Final Round - Problem (1063 downloads)
The Street View imagery available in Google Maps is captured using specialized vehicles called Street View cars. These cars carry multiple cameras capturing pictures as the car moves around a city. Capturing the imagery of a city poses an optimization problem: the fleet of cars is available for a limited amount of time and we want to cover as much of the city streets as possible.

[2021] Click here for Google Hash Code 2021 – Practice Problem


Google Hash Code 2018 Limassol Cyprus – Call for participation

We’ll be hosting a hub at the Cyprus University of Technology for the Online Qualification Round of Hash Code, a team-based programming competition created by Google for university students and industry professionals. The Online Qualification Round takes place on the 1st of March at 19:30 EET and registered teams from Cyprus are invited to participate from our hub, which will be at the Labs of the University. Top scoring teams from the Online Qualification Round will then be invited to Google’s Paris office to compete in the Final Round of the competition on the 1st of April.

If you’re interested in joining our hub, find a team (two to four people) and register at g.co/hashcode. Make sure to select Cyprus University of Technology from the list of hubs in the Judge System.

For more information about this and other hubs in Cyprus (including the twin event in Nicosia) visit https://goo.gl/uuRspx

Hash Code 2018 Limassol Cyprus – Facebook Event

Thanks!

Address:

Cyprus University of Technology
Room: ΚΧΕ 1 - Computer Lab
Polyxeni Loizia and Eleni Autonomou Building (Old Cadastre)
Athinon Street
Limassol

Τεχνολογικό Πανεπιστήμιο Κύπρου
Δωμάτιο: ΚΧΕ 1 -  Εργαστήριο Ηλεκτρονικών Υπολογιστών
Κτήριο Πολυξένη Λοϊζία και Ελένη Αυτονόμου (Παλιό Κτηματολόγιο)
Οδός Αθηνών
Λεμεσός

Date and Time:

1st March 2018
From: 19:30 EET
To: 23:30 EET

Free Amenities Offered

High speed Internet access
Wi-Fi access to the Internet for your mobile devices (personal computers and smart phones)
Lab computers will be available for use by the participants
Food in the form of snacks and beverages will be available outside the labs

Google Hash Code 2018 – Online Qualification Round Schedule

18:30 EET:

  • The hub will open to the public
  • People can view the live stream on the video projector
  • Teams can set themselves up with the help of the volunteers

19:30 EET:

  • Live stream starts

19:45 EET:

  • Task will be made available, competition starts
  • Scoreboard will be displayed on the video projector
  • Participating teams will be confirmed in the Judge System

23:30 EET:

  • End of the competition
  • Announcement of the score for the local teams

00:00 EET:

  • The hub will close

Google Hash Code 2018 Nicosia Cyprus – Call for participation

We’ll be hosting a hub at the University of Cyprus for the Online Qualification Round of Hash Code, a team-based programming competition created by Google for university students and industry professionals. The Online Qualification Round takes place on the 1st of March at 19:30 EET and registered teams from Cyprus are invited to participate from our hub, which will take place at the Computer Science Department. Top scoring teams from the Online Qualification Round will then be invited to Google’s Paris office to compete in the Final Round of the competition in April.

If you’re interested in joining our hub, find a team (two to four people) and register at g.co/hashcode. Make sure to select University of Cyprus from the list of hubs in the Judge System.

For more information about this and other hubs in Cyprus (including the twin event in Limassol) visit https://goo.gl/uuRspx

Hash Code 2018 Nicosia Cyprus – Facebook Event

Thanks!

Address:

Rooms: 101, 102, 103
Department of Computer Science,
Pure and Applied Sciences (FST-01)
University of Cyprus
1 University Avenue
2109 Aglantzia, CYPRUS

Date and Time:

1st March 2018
From: 19:30 EET
To: 23:30 EET

Free Amenities Offered

High speed Internet access
Wi-Fi access to the Internet for your mobile devices (personal computers and smart phones)
Lab computers will be available for use by the participants
Food in the form of snacks and beverages will be available outside the labs

Google Hash Code 2018 – Online Qualification Round Schedule

18:30 EET:

  • The hub will open to the public
  • People can view the live stream on the video projector
  • Teams can set themselves up with the help of the volunteers

19:30 EET:

  • Live stream starts

19:45 EET:

  • Task will be made available, competition starts
  • Scoreboard will be displayed on the video projector
  • Participating teams will be confirmed in the Judge System

23:30 EET:

  • End of the competition
  • Announcement of the score for the local teams

00:00 EET:

  • The hub will close

Online Qualification Round Problem for Google Hash Code 2017

Online Qualification Round Problem for Google Hash Code 2017 - Problem Statement (363 downloads)

Online Qualification Round Problem for Google Hash Code 2017 - Data Sets (342 downloads)

Streaming videos

Problem statement for Online Qualification Round, Hash Code 2017

Introduction

Have you ever wondered what happens behind the scenes when you watch a YouTube video? As more and more people watch online videos (and as the size of these videos increases), it is critical that video-serving infrastructure is optimized to handle requests reliably and quickly.

This typically involves putting in place cache servers, which store copies of popular videos. When a user request for a particular video arrives, it can be handled by a cache server close to the user, rather than by a remote data center thousands of kilometers away.

But how should you decide which videos to put in which cache servers?

Task

Given a description of cache servers, network endpoints and videos, along with predicted requests for individual videos, decide which videos to put in which cache server in order to minimize the average waiting time for all requests.

Problem description

The picture below represents the video serving network.

Videos

Each video has a size given in megabytes (MB). The data center stores ​ all videos​ . Additionally, each video can be put in 0, 1, or more cache servers​. Each cache server has a maximum capacity given in megabytes.

Endpoints

Each endpoint represents a group of users connecting to the Internet in the same geographical area (for example, a neighborhood in a city). Every endpoint is connected to the data center. Additionally, each endpoint may (but doesn’t have to) be connected to 1 or more cache servers​ .

Each endpoint is characterized by the latency of its connection to the data center (how long it takes to serve a video from the data center to a user in this endpoint), and by the latencies to each cache server that the endpoint is connected to (how long it takes to serve a video stored in the given cache server to a user in this endpoint).

Requests

The predicted requests provide data on how many times a particular video is requested from a particular endpoint.

Input data set

The input data is provided as a data set file – a plain text file containing exclusively ASCII characters with a single \n character at the end of each line (UNIX-​ style line endings).

Videos, endpoints and cache servers are referenced by integer IDs. There are V videos numbered from 0 to V − 1 , E endpoints numbered from 0 to E − 1 and C cache servers numbered from 0 to C − 1 .

File format

All numbers mentioned in the specification are natural numbers that fit within the indicated ranges. When multiple numbers appear in a single line, they are separated by a single space.

The first line of the input contains the following numbers:

  • V ( 1 ≤ V ≤ 10000) – the number of videos
  • E ( 1 ≤ E ≤ 1000) – the number of endpoints
  • R ( 1 ≤ R ≤ 1000000) – the number of request descriptions
  • C ( 1 ≤ C ≤ 1000) – the number of cache servers
  • X ( 1 ≤ X ≤ 500000) – the capacity of each cache server in megabytes

The next line contains ​V numbers describing the sizes of individual videos in megabytes: S0, S1, … SV-1. Si is the size of video i​ in megabytes ( 1 ≤ Si ≤ 1000).

The next section describes each of the endpoints one after another, from endpoint 0 to endpoint E − 1 . The description of each endpoint consists of the following lines:

  • a line containing two numbers:
    • LD ( 2 ≤ LD ≤ 4000) – the latency of serving a video request from the data center to this endpoint, in milliseconds
    • K ( 0 ≤ K ≤ C ) – the number of cache servers that this endpoint is connected to
  • K lines describing the connections from the endpoint to each of the K connected cache servers.
    Each line contains the following numbers:

    • c ( 0 ≤ c < C ) – the ID of the cache server
    • Lc ( 1 ≤ Lc ≤ 500) – the latency of serving a video request from this cache server to this endpoint, in milliseconds. You can assume that latency from the cache is strictly lower than latency from the data center ( 1 ≤ Lc < LD

Finally, the last section contains R request descriptions in separate lines. Each line contains the following numbers:

  • Rv ( 0 ≤ Rv < V ) – the ID of the requested video
  • Re ( 0 ≤ Re < E ) – the ID of the endpoint from which the requests are coming from
  • Rn ( 0 < Rn ≤ 10000) – the number of requests

Example

5 2 4 3 100
50 50 80 30 110
1000 3
0 100
2 200
1 300
500 0
3 0 1500
0 1 1000
4 0 500
1 0 1000

Example input file explanation.

5 videos, 2 endpoints, 4 request descriptions, 3 caches 100MB each.
Videos 0, 1, 2, 3, 4 have sizes 50MB, 50MB, 80MB, 30MB, 110MB.
Endpoint 0 has 1000ms datacenter latency and is connected to 3 caches:
The latency (of endpoint 0) to cache 0 is 100ms.
The latency (of endpoint 0) to cache 2 is 200ms.
The latency (of endpoint 0) to cache 1 is 200ms.
Endpoint 1 has 500ms datacenter latency and is not connected to a cache.
1500 requests for video 3 coming from endpoint 0.
1000 requests for video 0 coming from endpoint 1.
500 requests for video 4 coming from endpoint 0.
1000 requests for video 1 coming from endpoint 0.

Connections and latencies between the endpoints and caches of example input.

Submissions

File format

Your submission should start with a line containing a single number N ( 0 ≤ N ≤ C ) – the number of cache server descriptions to follow.

Each of the subsequent N lines should describe the videos cached in a single cache server. It should contain the following numbers:

  • c ( 0 ≤ c < C ) – the ID of the cache server being described,
  • the IDs of the videos stored in this cache server: v0, …, vn ( 0 ≤ vi < V) (at least 0 and at most V numbers), given in any order without repetitions

Each cache server should be described in at most one line. It is not necessary to describe all cache servers: if a cache does not occur in the submission, this cache server will be considered as empty. Cache servers can be described in any order.

Example

3
0 2
1 3 1
2 0 1

Example submission file explanation.

We are using  all 3 cache servers.
Cache server 0 contains only video 2.
Cache server 1 contains videos 3 and 1.
Cache server 2 contains videos 0 and 1.

Validation

The output file is valid if it meets the following criteria:

  • the format matches the description above
  • the total size of videos stored in each cache server does not exceed the maximum cache server capacity

Scoring

The score is the average time saved per request, in microseconds. (Note that the latencies in the input file are given in milliseconds. The score is given in microseconds to provide a better resolution of results.)
For each request description ( Rv, Re, Rn) in the input file, we choose the best way to stream the video Rv to the endpoint Re. We pick the lowest possible latency L = min(LD, L0, … , Lk−1) , where L​D is the latency of serving a video to the endpoint Re from the data center, and L0, … , Lk−1 are latencies of serving a video to the endpoint Re from each cache server that:

  • is connected to the endpoint Re, and
  • contains the video Rv

The time that was saved for each request is LD

As each request description describes Rn requests, the time saved for the entire request description is Rn × ( LD − L ) .

To compute the total score for the data set, we sum the time saved for individual request descriptions in milliseconds, multiply by 1000 and divide it by the total number of requests in all request descriptions, rounding down.

A schematic representation of the example submission file above​ .

In the example​ above, there are three request descriptions for the endpoint 0

  • 1500 requests for video 3, streamed from cache 1 with 300ms of latency, saving 1000ms − 300ms = 700ms per request
  • 500 requests for video 4, streamed from the data center, saving 0ms per request
  • 1000 requests for video 1, streamed from cache 2 with 200ms of latency saving 800ms per request

There is also one request description for the endpoint 1:

  • 1000 requests for video 0, streamed from the data center, saving 0ms per request

The average time saved is:

( 1500x700 + 500x0 + 1000x800 + 1000x0 )/(1500 + 500 + 1000 + 1000)

which equals 462.5ms. Multiplied by 1000, this gives the score of 462 500​.

Note that there are multiple data sets representing separate instances of the problem. The final score for your team will be the sum of your best scores on the individual data sets.

Online Qualification Round Problem for Google Hash Code 2017 - Problem Statement (363 downloads)

Online Qualification Round Problem for Google Hash Code 2017 - Data Sets (342 downloads)